Line search termination criteria for collinear scaling algorithms for minimizing a class of convex functions

Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence. Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important special case where the function being minimized belongs to a certain class of convex functions. Received February 1, 1997 / Revised version received September 8, 1997     

A new subspace minimization conjugate gradient method with nonmonotone line search for unconstrained optimization

A new subspace minimization conjugate gradient algorithm with a nonmonotone Wolfe line search is proposed and analyzed. In the scheme, we propose two choices of the search direction by minimizing a quadratic approximation of the objective function in special subspaces, and state criterions on how to choose the direction. Under given conditions, we obtain the significant conclusion that each choice of the direction satisfies the sufficient descent property. Based on the idea on how the function is close to a quadratic function, a new strategy for choosing the initial stepsize is presented for the line search. With the used nonmonotone Wolfe line search, we prove the global convergence of the proposed method for general nonlinear functions under mild assumptions. Numerical comparisons are given with well-known CGOPT and CG_DESCENT and show that the proposed algorithm is very promising.     

有界约束半光滑方程组的非单调投影信赖域方法

投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率.     

A New Nonmonotone Linesearch SQP Algorithm for Unconstrained Minimax Problem

In this article, unconstrained minimax problems are discussed, and a sequential quadratic programming (SQP) algorithm with a new nonmonotone linesearch is presented. At each iteration, a search direction of descent is obtained by solving a quadratic programming (QP). To circumvent the Maratos effect, a high-order correction direction is achieved by solving another QP and a new nonmonotone linesearch is performed. Under reasonable conditions, the global convergence and the rate of superlinear convergence are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

A robust implementation of a sequential quadratic programming algorithm with successive error restoration

We consider sequential quadratic programming methods for solving constrained nonlinear programming problems. It is generally believed that these methods are sensitive to the accuracy by which partial derivatives are provided. One reason is that differences of gradients of the Lagrangian function are used for updating a quasi-Newton matrix, e.g., by the BFGS formula. The purpose of this paper is to show by numerical experimentation that the method can be stabilized substantially. The algorithm applies non-monotone line search and internal and external restarts in case of errors due to inaccurate derivatives while computing the search direction. Even in case of large random errors leading to partial derivatives with at most one correct digit, termination subject to an accuracy of 10⁻⁷ can be achieved in 90% of 306 problems of a standard test suite. On the other hand, the original version with monotone line search and without restarts solves only 30% of these problems under the same test environment. In addition, we show how initial and periodic scaled restarts improve the efficiency in situations with slow convergence.     

Subspace Search Method for Quadratic Programming With Box Constraints

1.IntroductionInthispaper,weconsidertheproblemofminimizingaquadraticconvexprogrammingwithboxconstrainedvariables:Minf(x)s.t.x6fi(1'1)1,wherefi={xER":15xSu},f(x)=AX"Hx bTx,andHisannbynsymmetric.2positivedefinitematrix,andb,l,uaregivenconstantvectorsin...     

Simple Sequential Quadratically Constrained Quadratic Programming Feasible Algorithm with Active Identification Sets for Constrained Minimax Problems

In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported.     

Nongradient minimization methods for parallel processing computers,part 2

This paper analyzes the mathematical behavior of nongradient parallel minimization algorithms. The convergence of parallel synchronous iterative procedures corresponding to linearly independent direction methods and to mutually conjugate direction methods is discussed. For the latter, convergence with finite termination on quadratic objective functions and convergence on sufficiently smooth nonquadratic objective functions is proved.     

一个具有 n 步二次收敛性的直接法算法

在非线性最优化的直接法算法中,Powell 算法具有一定的代表性,但我们已知Powell 算法对正定二次函数一般不具有二次终结性,为此围绕着改善 Powell 算法的算法特性,出现了一系列 Powell 算法的改进型.其中俞文(鱼此)教授提出了一个新的方法——PY 算法,其基本思想基于,对正定二次的目标函数算法迭代过程中每一轮迭代     

An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point

For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence. To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above. Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China.     

A Trust Region Algorithm with Conjugate Gradient Technique for Optimization Problems

By means of a conjugate gradient strategy, we propose a trust region method for unconstrained optimization problems. The search direction is an adequate combination of the conjugate gradient direction and the trust-region direction. The global convergence and the quadratic convergence of this method are established under suitable conditions. Numerical results show that the presented method is competitive to the trust region method and the conjugate gradient method.     

Superlinearly Convergent Norm-Relaxed SQP Method Based on Active Set Identification and New Line Search for Constrained Minimax Problems

In this paper, the minimax problems with inequality constraints are discussed, and an alternative fast convergent method for the discussed problems is proposed. Compared with the previous work, the proposed method has the following main characteristics. First, the active set identification which can reduce the scale and the computational cost is adopted to construct the direction finding subproblems. Second, the master direction and high-order correction direction are computed by solving a new type of norm-relaxed quadratic programming subproblem and a system of linear equations, respectively. Third, the step size is yielded by a new line search which combines the method of strongly sub-feasible direction with the penalty method. Fourth, under mild assumptions without any strict complementarity, both the global convergence and rate of superlinear convergence can be obtained. Finally, some numerical results are reported.     

Numerical study of some feasible direction methods in mathematical programming

Some feasible direction methods for the minimization of a linearly constrained convex function are studied. Special emphasis is placed on the analysis of the procedures which find the search direction, by developing active set methods which use orthogonal or Gauss-Jordan-like transformations.Numerical experiments are performed on a class of quadratic problems depending on two parameters, related to the conditioning of the matrix associated with the quadratic form and the matrix of active constraints at the optimal point. Results are given for the rate of convergence and the average iteration time.This research was partially supported by the Progetto Finalizzato Informatica, CNR, Rome, Italy.     

有界约束非线性系统的结合Lanczos分解技术不精确Newton法

提出了结合Lanczos分解技术不精确Newton法求解有界变量约束非线性系统．通过Lanczos分解技术解一个仿射二次模型获得迭代方向．利用内点回代线搜索技术,沿着这个方向得到一个可接受的步长．在合理的假设条件下,证明了算法的整体收敛性与局部超线性收敛速率．此外,数值结果表明了算法的有效性．     

A SPARSE SUBSPACE TRUNCATED NEWTON METHOD FOR LARGE-SCALE BOUND CONSTRAINED NONLINEAR OPTIMIZATION

In this paper we report a sparse truncated Newton algorithm for handling large-scale simple bound nonlinear constrained minimixation problem. The truncated Newton method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. At each iterative level, the search direction consists of three parts, one of which is a subspace truncated Newton direction, the other two are subspace gradient and modified gradient directions. The subspace truncated Newton direction is obtained by solving a sparse system of linear equations. The global convergence and quadratic convergence rate of the algorithm are proved and some numerical tests are given.     

A generalized subgradient method with relaxation step

We study conditions for convergence of a generalized subgradient algorithm in which a relaxation step is taken in a direction, which is a convex combination of possibly all previously generated subgradients. A simple condition for convergence is given and conditions that guarantee a linear convergence rate are also presented. We show that choosing the steplength parameter and convex combination of subgradients in a certain sense optimally is equivalent to solving a minimum norm quadratic programming problem. It is also shown that if the direction is restricted to be a convex combination of the current subgradient and the previous direction, then an optimal choice of stepsize and direction is equivalent to the Camerini—Fratta—Maffioli modification of the subgradient method.Research supported by the Swedish Research Council for Engineering Sciences (TFR).     

On the uniqueness of search directions in variable-metric algorithms

Generalized variable-metric algorithms presented in Ref. 1 produce a unique search direction independently of parameters in the algorithms under several conditions. They generate a unique sequence of minimizing points for the given initial conditions if the objective function is quadratic.     

有界约束非线性优化问题的仿射共轭梯度路径法

本文提出仿射内点离散共轭梯度路径法解有界约束的非线性优化问题,通过构造预条件离散的共轭梯度路径解二次模型获得预选迭代方向,结合内点回代线搜索获得下一步的迭代,在合理的假设条件下,证明了算法的整体收敛性与局部超线性收敛速率,最后,数值结果表明了算法的有效性.     

A Theoretical and Numerical Comparison of Some Semismooth Algorithms for Complementarity Problems

In this paper we introduce a general line search scheme which easily allows us to define and analyze known and new semismooth algorithms for the solution of nonlinear complementarity problems. We enucleate the basic assumptions that a search direction to be used in the general scheme has to enjoy in order to guarantee global convergence, local superlinear/quadratic convergence or finite convergence. We examine in detail several different semismooth algorithms and compare their theoretical features and their practical behavior on a set of large-scale problems.     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.