Long-step primal-dual target-following algorithms for linear programming

In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.This work is completed with the support of a research grant from SHELL.The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.     

Trefftz,collocation, and other boundary methods—A comparison

In this article we survey the Trefftz method (TM), the collocation method (CM), and the collocation Trefftz method (CTM). We also review the coupling techniques for the interzonal conditions, which include the indirect Trefftz method, the original Trefftz method, the penalty plus hybrid Trefftz method, and the direct Trefftz method. Other boundary methods are also briefly described. Key issues in these algorithms, including the error analysis, are addressed. New numerical results are reported. Comparisons among TMs and other numerical methods are made. It is concluded that the CTM is the simplest algorithm and provides the most accurate solution with the best numerical stability. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Volume preserving RK methods for linear systems

1. IntroductionIn recent yearss there has been a great interest in constructing numerical integrationschemes for ODEs in such a way that some qualitative geometrical properties of the solutionof the ODEs are exactly preserved. R.th[ll and Feng Kang[2'31 has proposed symplectic algorithms for Hamiltollian systems, and since then st ruct ure s- preserving me t ho ds fordynamical systems have been systematically developed[4--7]. The symplectic algorithms forHamiltonian systems, the volume-pre…     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

s个几乎相等的素数的k次方和(Ⅰ)

假定pθ‖k,当p=2,2|k时，γ=θ 2；其它情况时，γ=θ 1。而R＝П(p-1)|kp^γ。本文在GRH（广义Riemann假设下），证明了当s=2^k 1,1≤k≤11时，任何足够大的整N≡s(modR)都可以表示为s个几乎相等的素数的k次方程。     

A note on the biasing of Newton's direction

This note deals with the geometric interpretation of the Levenberg-Marquardt search direction when the augmented Hessian is not positive definite.     

投入产出技术在计划平衡中的理论与应用

在用投入产出技术作计划平衡时，目前一般采用最终产品法、总产品法及国民收入法等．本文从理论上研究了这些方法的可行性问题，并在此基础上提出一个较理想的综合法．最后附有实例并说明综合法的现实意义．     

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

A comparison of some ODE solvers which require Jacobian evaluations

A variety of third-order ODE solvers which have a minimum configuration (i.e. minimum work per step) have been numerically tested and the results compared. They include implicit and explicit processes, and share the property that a Jacobian matrix must be evaluated at least once during the integration. Some of these processes have not been previously described in the literature.     

On the Convergence of Descent Algorithms

It is proved that any cluster point of a sequence defined by a steepest descent algorithm in a general normed vector space is a critical point. The function is just assumed to be continuously differentiable. The class of algorithms we consider encompasses several choices such as the Cauchy steplength and the Curry steplength.     

The Tikhonov regularization method in elastoplasticity

The numerical simulation of the mechanical behavior of industrial materials is widely used for viability verification, improvement and optimization of designs. Elastoplastic models have been used to forecast the mechanical behavior of different materials. The numerical solution of most elastoplastic models comes across problems of ill-condition matrices. A complete representation of the nonlinear behavior of such structures involves the nonlinear equilibrium path of the body and handling of singular (limit) points and/or bifurcation points. Several techniques to solve numerical problems associated to these points have been disposed in the specialized literature. Two examples are the load-controlled Newton–Raphson method and displacement controlled techniques. However, most of these methods fail due to convergence problems (ill-conditioning) in the neighborhood of limit points, specially when the structure presents snap-through or snap-back equilibrium paths. This study presents the main ideas and formalities of the Tikhonov regularization method and shows how this method can be used in the analysis of dynamic elastoplasticity problems. The study presents a rigorous mathematical demonstration of existence and uniqueness of the solution of well-posed dynamic elastoplasticity problems. The numerical solution of dynamic elastoplasticity problems using Tikhonov regularization is presented in this paper. The Galerkin method is used in this formulation. Effectiveness of Tikhonov’s approach in the regularization of the solution of elastoplasticity problems is demonstrated by means of some simple numerical examples.     

一种求解鞍点问题的广义对称超松弛迭代法

本文研究了鞍点问题的迭代算法.利用新的待定参数加速迭代格式并结合SSOR分裂的方法,获得了有两个参数的广义对称超松弛迭代法及其收敛性条件.数值例子表明选择适当的参数值可以提高算法的收敛效率,推广和改进了SOR-like迭代法.     

Stabilization of algebraic multilevel iteration methods; additive methods

There exist two main versions of preconditioners of algebraic multilevel type, the additive and the multiplicative methods. They correspond to preconditioners in block diagonal and block matrix factorized form, respectively. Both can be defined and analysed as recursive two-by-two block methods. Although the analytical framework for such methods is simple, for many finite element approximations it still permits the derivation of the strongest results, such as optimal, or nearly optimal, rate of convergence and optimal, or nearly optimal order of computational complexity, when proper recursive global orderings of node points have been used or when they are applied for hierarchical basis function finite element methods for elliptic self-adjoint equations and stabilized in a certain way. This holds for general elliptic problems of second order, independent of the regularity of the problem, including independence of discontinuities of coefficients between elements and of anisotropy. Important ingredients in the methods are a proper balance of the size of the coarse mesh to the finest mesh and a proper solver on the coarse mesh. This paper presents in a survey form the basic results of such methods and considers in particular additive methods. This method has excellent parallelization properties. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of the Fictitious Domain Method with an L 2-Penalty for Elliptic Problems

The L ²-penalty fictitious domain method is based on a reformulation of the original problem in a larger simple-shaped domain by introducing a discontinuous reaction term with a penalty parameter ε > 0. We first derive regularity results and some a priori estimates and then prove several error estimates. We also give several error estimates for discretization problems by the finite element and finite volume methods.     

Convergence of Rothe's Method in Hölder Spaces

The convergence of Rothe's method in Hölder spaces is discussed. The obtained results are based on uniform boundedness of Rothe's approximate solutions in Hölder spaces recently achieved by the first author. The convergence and its rate are derived inside a parabolic cylinder assuming an additional compatibility conditions.     

Mixed finite volume methods on nonstaggered quadrilateral grids for elliptic problems

We construct and analyze a mixed finite volume method on quadrilateral grids for elliptic problems written as a system of two first order PDEs in the state variable (e.g., pressure) and its flux (e.g., Darcy velocity). An important point is that no staggered grids or covolumes are used to stabilize the system. Only a single primary grid system is adopted, and the degrees of freedom are imposed on the interfaces. The approximate flux is sought in the lowest-order Raviart-Thomas space and the pressure field in the rotated- nonconforming space. Furthermore, we demonstrate that the present finite volume method can be interpreted as a rotated- nonconforming finite element method for the pressure with a simple local recovery of flux. Numerical results are presented for a variety of problems which confirm the usefulness and effectiveness of the method.

     

On the Equivalence of the Simplex Methods and a Multiplier-Alike Method for Linear Programming

In linear programming, the simplex method has been viewed for a long time as an efficient tool. Interior methods have attracted a lot of attention since they were proposed recently. It seems plausible intuitively that there is no reason why a good linear programming algorithm should not be allowed to cross the boundary of the feasible region when necessary. However, such an algorithm is seldom studied. In this paper, we will develop first a framework of a multiplier-alike algorithm for linear programming which allows its trajectory to move across the boundary of the feasible region. Second, we illustrate that such a framework has the potential to perform as well as the simplex method by showing that these methods are equivalent in a well-defined sense, even though they look so different.     

A comparison between the variational iteration method and the successive approximations method

In this paper we investigate and compare the variational iteration method and the successive approximations method for solving a class of nonlinear differential equations. We prove that these two methods are equivalent for solving these types of equations.     

一种特殊规划的分块超松驰组合牛顿——乘子算法

本文给出了分块的超松驰组合牛顿－乘子（ＢＳＯＲ－Ｎ－Ｍ）方法，来求解一类约束函数可分块的规划问题，证明了其收敛性，进一步给出与理论相应的数值结果。     

A projection technique for incompressible flow in the meshless finite volume particle method

The finite volume particle method is a meshless discretization technique, which generalizes the classical finite volume method by using smooth, overlapping and moving test functions applied in the weak formulation of the conservation law. The method was originally developed for hyperbolic conservation laws so that the compressible Euler equations particularly apply. In the present work we analyze the discretization error and enforce consistency by a new set of geometrical quantities. Furthermore, we introduce a discrete Laplace operator for the scheme in order to extend the method to second order partial differential equations. Finally, we transfer Chorins projection technique to the finite volume particle method in order to obtain a meshless scheme for incompressible flow. AMS subject classification 65M99, 68U20, 76B99, 76M12, 76M25, 76M28