一类广义拟牛顿算法的收敛性

本文提出一类广义拟牛顿算法,新类算法降低了关于目标函数的假设条件,将线搜索扩展 到一般形式,它概括了若干种常用的非精确线搜索技术.此外,算法对迭代校正公式中的参数Φk的 选取范围做了较大扩展(可以取负值).     

On the Superlinear Convergence of the Successive Approximations Method

The Ostrowski theorem is a classical result which ensures the attraction of all the successive approximations x _k+1 = G(x _k ) near a fixed point x*. Different conditions [ultimately on the magnitude of G(x*)] provide lower bounds for the convergence order of the process as a whole. In this paper, we consider only one such sequence and we characterize its high convergence orders in terms of some spectral elements of G(x*); we obtain that the set of trajectories with high convergence orders is restricted to some affine subspaces, regardless of the nonlinearity of G. We analyze also the stability of the successive approximations under perturbation assumptions.     

无约束最优化锥模型拟牛顿信赖域方法的收敛性(英)

本文研究无约束最优化雄模型拟牛顿信赖域方法的全局收敛性．文章给出了确保这类方法全局收敛的条件．文章还证明了，当用拆线法来求这类算法中锥模型信赖域子问题的近似解时，确保全局收敛的条件得到满足     

On the Superlinear Convergence Order of the Logarithmic Barrier Algorithm

Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter r_k +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if r_k+1=r _k with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods.     

Global Convergence of the Broyden‘’s Class of Quasi—Newton Methods with Nonmonotone Linesearch

In this paper,the Broyden class of quasi-Newton methods for unconstrained optimization is inves-tigated.Non-monotone linesearch procedure is introduced,which is combined with the Broyden‘s class.Under the convexity assumption on objective function,the global convergence of the Broyden‘s class is proved.     

一类不精确拟牛顿型算法的局部收敛性分析

为了求解Hilbert空间中算子方程或minimax问题,构造了一类无穷维空间中的不精确拟牛顿算法,并考虑了其线性收敛性和超线性收敛性,是对有限维空间中不精确拟牛顿法的推广.当迭代算子由Broyden修正给出时,在一定的假设条件下,得到了不精确Broyden方法的线性收敛性和超线性收敛性.这为使用不精确拟牛顿法结合投影法求解算子方程做好了准备.     

Convergence of Projected Hessian Approximations in Quasi-Newton Methods for the Nonlinear Programming Problem

Two recently proposed algorithms for the problem of minimizationsubject to nonlinear equality constraints are examined. Bothmaintain quasi-Newton approximations to the projection of theHessian of the Lagrangian, onto the (linearized) manifold ofactive constraints at each iteration. We show that both algorithmscan be used with a more general quasi-Newton updating rule,and, using the analysis of Stoer (1984), that the sequence ofprojected Hessian approximations is convergent.     

A Survey of Quasi-Newton Equations and Quasi-Newton Methods for Optimization

Quasi-Newton equations play a central role in quasi-Newton methods for optimization and various quasi-Newton equations are available. This paper gives a survey on these quasi-Newton equations and studies properties of quasi-Newton methods with updates satisfying different quasi-Newton equations. These include single-step quasi-Newton equations that use only gradient information and that use both gradient and function value information in one step, and multi-step quasi-Newton equations that use the gradient information in last m steps. Main properties of quasi-Newton methods with updates satisfying different quasi-Newton equations are studied. These properties include the finite termination property, invariance, heredity of positive definite updates, consistency of search directions, global convergence and local superlinear convergence properties.     

一个新的SQP方法及其超线性收敛性

由Ｗｉｌｓｏｎ,Ｈａｎ,Ｐｏｗｅｌｌ发展的ＳＱＰ技术是解非线性规划的最有效的方法之一,但是,如果其中的二次子规划问题无可行解或者其搜索方向向量无界,该方法ａｎ和Ｂｕｒｋｅ「３」,周广路「２」分别对二次规划问题作了修正,克服了上述矛盾,本文在「２」的基础上,进上步修正,证明在Ａｒｍｉｊｏ搜索下算法具有全局收敛性,并通过解一辅助线性方程组,利用弧式搜索,得出该方法具有超线性收敛性。     

非凸无约束优化问题的广义拟牛顿法的全局收敛性

本文对无约束优化问题提出一类新的广义拟牛顿法,并采用一类非精确线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性.     

On the Superlinear Convergence Rate of the Preconditioned CGM for Some Nonsymmetric Elliptic Problems

Earlier estimates on the superlinear convergence of the preconditioned conjugate gradient method are completed using singular values of compact operators. Suitable domain independence and an explicit estimate of the magnitude of superlinear convergence are derived.     

On Superlinear Convergence of Infeasible Interior-Point Algorithms for Linearly Constrained Convex Programs

This note derives bounds on the length of the primal-dual affinescaling directions associated with a linearly constrained convexprogram satisfying the following conditions: 1) the problem has asolution satisfying strict complementarity, 2) the Hessian of theobjective function satisfies a certain invariance property. Weillustrate the usefulness of these bounds by establishing thesuperlinear convergence of the algorithm presented in Wright andRalph [22] for solving the optimality conditions associatedwith a linearly constrained convex program satisfying the aboveconditions.     

Superlinear Convergence of the GMRES for PDE-Constrained Optimization Problems

Optimal control problems for PDEs arise in many important applications. A main step in the solution process is the solution of the arising linear system, where the crucial point is usually finding a proper preconditioner. We propose both proper block diagonal and more involved preconditioners, and derive mesh independent superlinear convergence of the preconditioned GMRES iterations based on a compact perturbation property of the underlying operators.     

On the Convergence of Broyden-Like Methods

The author provides a finer local as well as semilocM convergence analysis of a certain class of Broyden-like methods for solving equations containing a nondifferentiable term on the m-dimensional Euclidean space （m ≥ 1 a natural number）.     

Superlinear Convergence ofthe Preconvex Part ofNon-Quasi-Newton's Family

Weconsidertheunconstrainedoptimizationproblem:minf(x),xC∈Rn,(1)SupportedbyBeijingEducati0nC0mmittee.wheretheobjectivefunctionfistwicecontinuouslydmerentiable.Quasi-Newt0nmethodsforsolving(1)areveryfamousmethodsbecauseofitssuperlinearconvergence.Atk-thiteration0fthemeth0d,xk 1isgeneratedbythefollowingformulaxk l=xk akdk,dh=-B*-'g*,k21,(2)wheregk=Vf(xk)isthegradientoffatxk,thescalarahisastepelengthparameter,andnxnmatrixUkisselectedsuchthattheaPproximateHessianBhsatisfiesquasi-NeWtoneqllat…     

A Classification of Quasi-Newton Methods

In this paper, we consider quasi-Newton methods of the form x _k+1=x _k + _k f(x _k ), k=0,1,. . ., for the solution of the system of nonlinear equations f(x)=0. We present a classification of such methods based on different structures for the matrix _k and various criteria for its computation, issued from three different formulae. Many known methods can be put into this framework and new methods are also obtained.     

广义投影型的超线性收敛算法

该文利用矩阵分解与广义投影等技巧，给出了求解线性约束的非线性规划的一个广义投影型的超线性收敛算法，不需要δ－主动约束与每一步反复计算投影矩阵，避免了计算的数值不稳定性，利用矩阵求逆的递推公式，计算简便，由于采用了非精确搜索，算法实用可行，文中证明了算法具有收敛性及超线性的收敛速度．     

Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming

We prove the superlinear convergence of the primal-dual infeasible interior-point path-following algorithm proposed recently by Kojima, Shida, and Shindoh and by the present authors, under two conditions: (i) the semidefinite programming problem has a strictly complementary solution; (ii) the size of the central path neighborhood approaches zero. The nondegeneracy condition suggested by Kojima, Shida, and Shindoh is not used in our analysis. Our result implies that the modified algorithm of Kojima, Shida, and Shindoh, which enforces condition (ii) by using additional corrector steps, has superlinear convergence under the standard assumption of strict complementarity. Finally, we point out that condition (ii) can be made weaker and show the superlinear convergence under the strict complementarity assumption and a weaker condition than (ii).