A nonmonotone filter method for nonlinear optimization

We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method.     

最优化两个拓广的SQP和SSLE算法模型及其超线性和二次收敛性

给出一般约束最优化的序列二次规划（SQP）和序列线性方程组（SSLE）算法两个拓广的模型,详细分析和论证两个模型的局部超线性收敛性及二次收敛性条件,其中并不需要严格互补条件,拓广的模型及其收敛速度结果具有更广泛的适用性,为SQP和SSLE算法收敛速度的研究提供了更为完善和便利的理论基础。     

关于不等式约束的信赖域算法

对于具有不等式约束的非线性优化问题，本文给出一个依赖域算法，由于算法中依赖区域约束采用向量的∞范数约束的形式，从而使子问题变二次规划，同时使算法变得更实用。在通常假设条件下，证明了算法的整体收敛性和超线性收敛性。     

Stabilized SQP revisited

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve superlinear convergence in situations when the Lagrange multipliers associated to a solution are not unique. Within the framework of Fischer (Math Program 94:91–124, 2002), the key to local superlinear convergence of sSQP are the following two properties: upper Lipschitzian behavior of solutions of the Karush-Kuhn-Tucker (KKT) system under canonical perturbations and local solvability of sSQP subproblems with the associated primal-dual step being of the order of the distance from the current iterate to the solution set of the unperturbed KKT system. According to Fernández and Solodov (Math Program 125:47–73, 2010), both of these properties are ensured by the second-order sufficient optimality condition (SOSC) without any constraint qualification assumptions. In this paper, we state precise relationships between the upper Lipschitzian property of solutions of KKT systems, error bounds for KKT systems, the notion of critical Lagrange multipliers (a subclass of multipliers that violate SOSC in a very special way), the second-order necessary condition for optimality, and solvability of sSQP subproblems. Moreover, for the problem with equality constraints only, we prove superlinear convergence of sSQP under the assumption that the dual starting point is close to a noncritical multiplier. Since noncritical multipliers include all those satisfying SOSC but are not limited to them, we believe this gives the first superlinear convergence result for any Newtonian method for constrained optimization under assumptions that do not include any constraint qualifications and are weaker than SOSC. In the general case when inequality constraints are present, we show that such a relaxation of assumptions is not possible. We also consider applying sSQP to the problem where inequality constraints are reformulated into equalities using slack variables, and discuss the assumptions needed for convergence in this approach. We conclude with consequences for local regularization methods proposed in (Izmailov and Solodov SIAM J Optim 16:210–228, 2004; Wright SIAM J. Optim. 15:673–676, 2005). In particular, we show that these methods are still locally superlinearly convergent under the noncritical multiplier assumption, weaker than SOSC employed originally.     

Erratum to: An abstract model for branching and its application to mixed integer programming

Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic programming subproblem at each iteration. It is shown that the method has superlinear local convergence under assumptions that are no stronger than those required by conventional stabilized SQP methods. The fast local convergence is obtained by allowing a small relaxation of the optimality conditions for the quadratic programming subproblem in the neighborhood of a solution. In the limit, the line search selects the unit step length, which implies that the method does not suffer from the Maratos effect. The analysis indicates that the method has the same strong first- and second-order global convergence properties that have been established for augmented Lagrangian methods, yet is able to transition seamlessly to sSQP with fast local convergence in the neighborhood of a solution. Numerical results on some degenerate problems are reported.     

A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints

In this paper, we present a dual algorithm for minimizing a convex quadratic function with two quadratic constraints. Such a minimization problem is a subproblem that appears in some trust region algorithms for general nonlinear programming. Some theoretical properties of the dual problem are given. Global convergence of the algorithm is proved and a local superlinear convergence result is presented. Numerical examples are also provided.     

Interior point stabilization for column generation

Interior point stabilization is an acceleration method for column generation algorithms. It addresses degeneracy and convergence difficulties by selecting a dual solution inside the optimal space rather than retrieving an extreme point. The method is applied to the case of the vehicle routing problem with time windows.     

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.     

On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers

It has been previously demonstrated that in the case when a Lagrange multiplier associated to a given solution is not unique, Newton iterations [e.g., those of sequential quadratic programming (SQP)] have a tendency to converge to special multipliers, called critical multipliers (when such critical multipliers exist). This fact is of importance because critical multipliers violate the second-order sufficient optimality conditions, and this was shown to be the reason for slow convergence typically observed for problems with degenerate constraints (convergence to noncritical multipliers results in superlinear rate despite degeneracy). Some theoretical and numerical validation of this phenomenon can be found in Izmailov and Solodov (Comput Optim Appl 42:231–264, 2009; Math Program 117:271–304, 2009). However, previous studies concerned the basic forms of Newton iterations. The question remained whether the attraction phenomenon still persists for relevant modifications, as well as in professional implementations. In this paper, we answer this question in the affirmative by presenting numerical results for the well known MINOS and SNOPT software packages applied to a collection of degenerate problems. We also extend previous theoretical considerations to the linearly constrained Lagrangian methods and to the quasi-Newton SQP, on which MINOS and SNOPT are based. Experiments also show that in the stabilized version of SQP the attraction phenomenon still exists but appears less persistent.     

A Modified SQP Method with Nonmonotone Linesearch Technique

In this paper, a modified SQP method with nonmonotone line search technique is presented based on the modified quadratic subproblem proposed in Zhou (1997) and the nonmonotone line search technique. This algorithm starts from an arbitrary initial point, adjusts penalty parameter automatically and can overcome the Maratos effect. What is more, the subproblem is feasible at each iterate point. The global and local superlinear convergence properties are obtained under certain conditions.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

A Riemannian subspace limited-memory SR1 trust region method

In this paper, we present a new trust region algorithm on any compact Riemannian manifolds using subspace techniques. The global convergence of the method is proved and local \(d+1\)-step superlinear convergence of the algorithm is presented, where d is the dimension of the Riemannian manifold. Our numerical results show that the proposed subspace algorithm is competitive to some recent developed methods, such as the LRTR-SR1 method, the LRTR-BFGS method, the Riemannian CG method.     

On the attraction of Newton’s method to critical lagrange multipliers

The attraction of dual trajectories of Newton’s method for the Lagrange system to critical Lagrange multipliers is analyzed. This stable effect, which has been confirmed by numerical practice, leads to the Newton-Lagrange method losing its superlinear convergence when applied to problems with irregular constraints. At the same time, available theoretical results are of “negative” character; i.e., they show that convergence to a noncritical multiplier is not possible or unlikely. In the case of a purely quadratic problem with a single constraint, a “positive” result is proved for the first time demonstrating that the critical multipliers are attractors for the dual trajectories. Additionally, the influence exerted by the attraction to critical multipliers on the convergence rate of direct and dual trajectories is characterized.     

求解一般约束优化问题的一个全局收敛的混合不精确SQP算法

对于一般约束优化问题,本文通过一种特殊的耦合策略,把一个局邵超线性收敛的不精确SQP算法与广义梯度投影法相结合,从而给出了一个混合算法.该算法无需计算拉格朗日函数的海色矩阵,并且在适当的假设下,算法具有全局和局部超线性收敛性.     

Convergence of a generalized Newton and an inexact generalized Newton algorithms for solving nonlinear equations with nondifferentiable terms

In this paper, we consider two versions of the Newton-type method for solving a nonlinear equations with nondifferentiable terms, which uses as iteration matrices, any matrix from B-differential of semismooth terms. Local and global convergence theorems for the generalized Newton and inexact generalized Newton method are proved. Linear convergence of the algorithms is obtained under very mild assumptions. The superlinear convergence holds under some conditions imposed on both terms of equation. Some numerical results indicate that both algorithms works quite well in practice.      

A sequential equality constrained quadratic programming algorithm for inequality constrained optimization

In this paper, the feasible type SQP method is improved. A new SQP algorithm is presented to solve the nonlinear inequality constrained optimization. As compared with the existing SQP methods, per single iteration, in order to obtain the search direction, it is only necessary to solve equality constrained quadratic programming subproblems and systems of linear equations. Under some suitable conditions, the global and superlinear convergence can be induced.     

不等式约束优化一个新的SQP算法

本文提出了一个处理不等式约束优化问题的新的SQP算法．和传统的SQP算法相比，该算法每步只需求解一个仅含等式约束的子二次规划，从而减少了算法的计算工作量．在适当的条件下，证明算法是全局收敛的且具有超线性收敛速度．数值实验表明算法是有效的．     

一个新的共轭投影梯度算法及其超线性收敛性

利用共轭投影梯度技巧，结合SQP算法的思想，建立了一个具有显示搜索方向的新算法，在适当的条件下，证明算法是全局收敛和强收敛的，且具有超线性收敛性，最后数值实验表明算法是有效的。     

CONVERGENCE PROPERTIES OF MULTI-DIRECTIONAL PARALLEL ALGORITHMS FOR UNCONSTRAINED MINIMIZATION

Convergence properties of a class of multi-directional parallel quasi-Newton algorithmsfor the solution of unconstrained minimization problems are studied in this paper.At eachiteration these algorithms generate several different quasi-Newton directions,and thenapply line searches to determine step lengths along each direction,simultaneously.Thenext iterate is obtained among these trail points by choosing the lowest point in the sense offunction reductions.Different quasi-Newton updating formulas from the Broyden familyare used to generate a main sequence of Hessian matrix approximations.Based on theBFGS and the modified BFGS updating formulas,the global and superlinear convergenceresults are proved.It is observed that all the quasi-Newton directions asymptoticallyapproach the Newton direction in both direction and length when the iterate sequenceconverges to a local minimum of the objective function,and hence the result of superlinearconvergence follows.     

Rational approximation to trigonometric operators

We consider the approximation of trigonometric operator functions that arise in the numerical solution of wave equations by trigonometric integrators. It is well known that Krylov subspace methods for matrix functions without exponential decay show superlinear convergence behavior if the number of steps is larger than the norm of the operator. Thus, Krylov approximations may fail to converge for unbounded operators. In this paper, we propose and analyze a rational Krylov subspace method which converges not only for finite element or finite difference approximations to differential operators but even for abstract, unbounded operators. In contrast to standard Krylov methods, the convergence will be independent of the norm of the operator and thus of its spatial discretization. We will discuss efficient implementations for finite element discretizations and illustrate our analysis with numerical experiments. AMS subject classification (2000)  65F10, 65L60, 65M60, 65N22