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.     

A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

A line search filter algorithm with inexact step computations for equality constrained optimization

In this paper, a new line search filter algorithm for equality constrained optimization is presented. The approach belongs to the class of inexact Newton-like methods. It can also be regarded as an inexact version of generic sequential quadratic programming (SQP) methods. The trial step is obtained by truncatedly solving the primal-dual system based on any robust and efficient linear system solver. Practical termination tests for the linear system solver are established to ensure global convergence. Preliminary numerical results demonstrate the approach is potentially useful.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Sequential quadratic programming with a flexible step acceptance strategy

A new sequential quadratic programming (SQP) method for nonlinear inequality constrained optimization is proposed. The aim of this paper is to promote global convergence for SQP methods using a flexible step acceptance strategy which combines merit functions and filter techniques. Global convergence is proved under some reasonable assumptions and preliminary numerical results are reported.     

A superlinearly convergent method of quasi-strongly sub-feasible directions with active set identifying for constrained optimization

Combining the norm-relaxed sequential quadratic programming (SQP) method and the idea of method of quasi-strongly sub-feasible directions (MQSSFD) with active set identification technique, a new SQP algorithm for solving nonlinear inequality constrained optimization is proposed. Unlike the previous work, at each iteration of the proposed algorithm, the norm-relaxed quadratic programming (QP) subproblem only consists of the constraints corresponding to an active identification set. Moreover, the high-order correction direction (used to avoid the Maratos effect) is yielded by solving a system of linear equations (SLE) which also includes only the constraints and their gradients corresponding to the active identification set, therefore, the scale and the computation cost of the high-order correction directions are further decreased. The arc search in our algorithm can effectively combine the initialization processes with the optimization processes, and the iteration points can get into the feasible set after a finite number of iterations. Furthermore, the arc search conditions are weaker than the previous work, and the computation cost is further reduced. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ). If the strong second-order sufficient conditions are satisfied, then the active constraints are exactly identified by the identification set. Without the strict complementarity, superlinear convergence can be obtained. Finally, some elementary numerical results are reported.     

On the Global Convergence of a Projective Trust Region Algorithm for Nonlinear Equality Constrained Optimization

A trust-region sequential quadratic programming (SQP) method is developed and analyzed for the solution of smooth equality constrained optimization problems. The trust-region SQP algorithm is based on filter line search technique and a composite-step approach, which decomposes the overall step as sum of a vertical step and a horizontal step. The algorithm includes critical modifications of horizontal step computation. One orthogonal projective matrix of the Jacobian of constraint functions is employed in trust-region subproblems. The orthogonal projection gives the null space of the transposition of the Jacobian of the constraint function. Theoretical analysis shows that the new algorithm retains the global convergence to the first-order critical points under rather general conditions. The preliminary numerical results are reported.     

A feasible SQP method for nonlinear programming

In this paper, a new SQP algorithm is presented to solve the general nonlinear programs with mixed equality and inequality constraints. Quoted from P. Spellucci (see [9]), this method maybe be named sequential equality constrained quadratic programming (SECQP) algorithm. Per single iteration, based on an active set strategy ( see [9]), this SECQP algorithm requires only to solve equality constrained quadratic programming subproblems or system of linear equations. The theoretical analysis shows that global and superlinear convergence can be induced under some suitable conditions.     

A sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function

Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.     

A Strongly and Superlinearly Convergent SQP Algorithm for Optimization Problems with Linear Complementarity Constraints

This paper discusses a kind of optimization problem with linear complementarity constraints, and presents a sequential quadratic programming (SQP) algorithm for solving a stationary point of the problem. The algorithm is a modification of the SQP algorithm proposed by Fukushima et al. [Computational Optimization and Applications, 10 (1998), 5-34], and is based on a reformulation of complementarity condition as a system of linear equations. At each iteration, one quadratic programming and one system of equations needs to be solved, and a curve search is used to yield the step size. Under some appropriate assumptions, including the lower-level strict complementarity, but without the upper-level strict complementarity for the inequality constraints, the algorithm is proved to possess strong convergence and superlinear convergence. Some preliminary numerical results are reported.     

A nonmonotone filter trust region method for the system of nonlinear equations

In this paper, we present a nonmonotone filter trust region method to attack the system of nonlinear equations. The system of nonlinear equations is transformed into a constrained nonlinear programming problem at each step: some equations are treated as constraints while the others act as objective functions. Compared with the traditional filter strategies, our algorithm is flexible to accept trail steps by means of the nonmonotone filter technique. Moreover, the restoration phase is not needed so that the scale of the calculation is decreased in a certain degree. Global convergence is proven under some suitable conditions. Numerical experiments also show the efficiency of the algorithm.     

A modified SQP algorithm for minimax problems

In this paper, a modified nonmonotone line search SQP algorithm for nonlinear minimax problems is presented. During each iteration of the proposed algorithm, a main search direction is obtained by solving a reduced quadratic program (QP). In order to avoid the Maratos effect, a correction direction is generated by solving the reduced system of linear equations. Under mild conditions, the global and superlinear convergence can be achieved. Finally, some preliminary numerical results are reported.     

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.     

An algorithm for solving linearly constrained minimax problems

In this study, we propose an algorithm for solving a minimax problem over a polyhedral set defined in terms of a system of linear inequalities. At each iteration a direction is found by solving a quadratic programming problem and then a suitable step size along that direction is taken through an extension of Armijo's approximate line search technique. We show that each accumulation point is a Kuhn-Tucker solution and give a condition that guarantees convergence of the whole sequence of iterations. Through the use of an exact penalty function, the algorithm can be used for solving constrained nonlinear programming. In this case, our algorithm resembles that of Han, but differs from it both in the direction-finding and the line search steps.     

解非线性互补问题的非单调可行SQP方法

非线性互补问题可以转化成非线性约束优化问题. 提出一种非单调线搜索的可行SQP方法. 利用QP子问题的K-T点得到一个可行下降方向,通过引入一个高阶校正步以克服Maratos效应. 同时,算法采用非单调线搜索技巧获得搜索步长. 证明全局收敛性时不需要严格互补条件, 最后给出数值试验.     

一类求解线性约束非线性规划问题的可行方向法

Wilson,Han和Powell提出的序列二次规划方法(简称SQP方法)是求解非线性规划问题的一个著名方法,这种方法每次迭代的搜索方向是通过求解一个二次规划子问题得到的,本文受[1]启发,得到二次规划子问题的一个近似解,进而给出了一类求解线性约束非线性规划问题的可行方向法,在约束集合满足正则性的条件下,证明了该算法对五种常用线性搜索方法具有全局收敛性。     

线性约束两分块非凸优化的ADMM-SQP算法

基于乘子交替方向法(ADMM)和序列二次规划(SQP)方法思想, 致力于研究线 性约束两分块非凸优化的新型高效算法. 首先, 以SQP思想为主线, 在其二次规划(QP)子问题的求解中引入ADMM思想, 将QP分解为两个相互独立的小规模QP求解. 其次, 借助增广拉格朗日函数和Armijo线搜索产生原始变量新迭代点. 最后, 以显式解析式更新对偶变量. 因此, 构建了一个新型ADMM-SQP算法. 在较弱条件下, 分析了算法通常意义下的全局收敛性, 并对算法进行了初步的数值试验.     

解非线性规划问题的不精确线性搜索SQP滤子方法

本文用序列二次规划方法(SQP)结合Wolfe-Powell不精确线性搜索准则求解非线性规划问题.Wolfe-Powell准则是一种能够使目标函数获得充分下降而运行时间较省的确定步长方法.不精确线性搜索滤子方法比较其它结合精确线性搜索和信赖域方法求解问题的滤子方法更灵活更易实现.如果目标函数的预测下降量为负,我们的工作将主要利用可行恢复项改善可行性.一般条件下,本文提出的算法较易实现,且具有全局收敛性.数值试验显示了算法的有效性.     

A new inexact SQP algorithm for nonlinear systems of mixed equalities and inequalities

Traditional inexact SQP algorithm can only solve equality constrained optimization (Byrd et al. Math. Program. 122, 273–299 2010). In this paper, we propose a new inexact SQP algorithm with affine scaling technique for nonlinear systems of mixed equalities and inequalities, which arise in complementarity and variational inequalities. The nonlinear systems are transformed into a special nonlinear optimization with equality and bound constraints, and then we give a new inexact SQP algorithm for solving it. The new algorithm equipped with affine scaling technique does not require a quadratic programming subproblem with inequality constraints. The search direction is computed by solving one linear system approximately using iterative linear algebra techniques. Under mild assumptions, we discuss the global convergence. The preliminary numerical results show the effectiveness of the proposed algorithm.     

A new smoothing Newton method for solving constrained nonlinear equations

In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well.