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.     

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 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.     

Sparse quadratic programming in chemical process optimization

The quadratic programming aspects of a full space successive quadratic programming (SQP) method are described. In particular, fill-in, matrix factor and active set updating, numerical stability, and indefiniteness of the Hessian matrix are discussed in conjunction with a sparse modification of Bunch and Parlett factorization of symmetric indefinite (Kuhn-Tucker) matrices of the type often encountered in optimization. A new pivoting strategy, called constrained pivoting, is proposed to reduce fill-in and compared with complete, partial and threshold pivoting. It is shown that constrained pivoting often significantly reduces fill-in and thus the iterative computational burdens associated with the factorization and solution of Kuhn-Tucker conditions within the QP subproblem. A numerical algorithm for updating the lower triangular and diagonal factors is presented and shown to be very fast, usually requiring only about 5% of the cost of refactorization. Two active set strategies are also presented. These include the options of adding inequalities either one or several at a time. In either case, the effects on matrix factor updating is shown to be small. Finally, a simple test is used to maintain iterative descent directions in the quadratic program. Our sparse symmetric indefinite QP algorithm is tested in the context of a family of SQP algorithms that include a full space Newton method with analytical derivatives, a full space BFGS method and a Range and Null space Decomposition (RND) method in which the projected Hessian is calculated from either analytical second derivatives or the BFGS update. Several chemical process optimization problems, with small and large degrees of freedom, are used as test problems. These include minimum work calculations for multistage isothermal compression, minimum area targeting for heat exchanger networks, and distillation optimizations involving some azeotropic and extractive distillations. Numerical results show uniformly that both the proposed QP and SQP algorithms, particularly the full space Newton method, are reliable and efficient. No failures were experienced at either level.     

Global convergence of a robust filter SQP algorithm

We present a robust filter SQP algorithm for solving constrained optimization problems. This algorithm is based on the modified quadratic programming proposed by Burke to avoid the infeasibility of the quadratic programming subproblem at each iteration. Compared with other filter SQP algorithms, our algorithm does not require any restoration phase procedure which may spend a large amount of computation. The main advantage of our algorithm is that it is globally convergent without requiring strong constraint qualifications, such as Mangasarian–Fromovitz constraint qualification (MFCQ) and the constant rank constraint qualification (CRCQ). Furthermore, the feasible limit points of the sequence generated by our algorithm are proven to be the KKT points if some weaker conditions are satisfied. Numerical results are also presented to show the efficiency of the algorithm.     

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

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

基于并行计算的多方向强次可行模松弛SQP算法

本文研究求解非线性约束优化问题.利用多方向并行方法,提出了一个新的强次可行模松弛序列二次规划(SQP)算法.数值试验表明,迭代次数和计算时间少于只取单一参数的传统算法.     

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.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

Adaptive Algorithm for Constrained Least-Squares Problems

This paper is concerned with the implementation and testing of an algorithm for solving constrained least-squares problems. The algorithm is an adaptation to the least-squares case of sequential quadratic programming (SQP) trust-region methods for solving general constrained optimization problems. At each iteration, our local quadratic subproblem includes the use of the Gauss–Newton approximation but also encompasses a structured secant approximation along with tests of when to use this approximation. This method has been tested on a selection of standard problems. The results indicate that, for least-squares problems, the approach taken here is a viable alternative to standard general optimization methods such as the Byrd–Omojokun trust-region method and the Powell damped BFGS line search method.     

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 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.     

Solving nonlinear programming problems with very many constraints

For solving the smooth constrained nonlinear programming problem, sequential quadratic programming (SQP) methods are considered to be the standard tool, as long as they are applicable. However one possible situation preventing the successful solution by a standard SQP-technique, arises if problems with a very large number of constraints are to be solved. Typical applications are semi-infinite or min-max optimization, optimal control or mechanical structural optimization. The proposed technique proceeds from a user defined number of linearized constraints, that is to be used internally to determine the size of the quadratic programming subproblem. Significant constraints are then selected automatically by the algorithm. Details of the numerical implementation and some experimental results are presented     

A working set SQCQP algorithm with simple nonmonotone penalty parameters

In this paper, we present a new sequential quadratically constrained quadratic programming (SQCQP) algorithm, in which a simple updating strategy of the penalty parameter is adopted. This strategy generates nonmonotone penalty parameters at early iterations and only uses the multiplier corresponding to the bound constraint of the quadratically constrained quadratic programming (QCQP) subproblem instead of the multipliers of the quadratic constraints, which will bring some numerical advantages. Furthermore, by using the working set technique, we remove the constraints of the QCQP subproblem that are locally irrelevant, and thus the computational cost could be reduced. Without assuming the convexity of the objective function or the constraints, the algorithm is proved to be globally, superlinearly and quadratically convergent. Preliminary numerical results show that the proposed algorithm is very promising when compared with the tested SQP algorithms.     

A working set SQCQP algorithm with simple nonmonotone penalty parameters

In this paper, we present a new sequential quadratically constrained quadratic programming (SQCQP) algorithm, in which a simple updating strategy of the penalty parameter is adopted. This strategy generates nonmonotone penalty parameters at early iterations and only uses the multiplier corresponding to the bound constraint of the quadratically constrained quadratic programming (QCQP) subproblem instead of the multipliers of the quadratic constraints, which will bring some numerical advantages. Furthermore, by using the working set technique, we remove the constraints of the QCQP subproblem that are locally irrelevant, and thus the computational cost could be reduced. Without assuming the convexity of the objective function or the constraints, the algorithm is proved to be globally, superlinearly and quadratically convergent. Preliminary numerical results show that the proposed algorithm is very promising when compared with the tested SQP algorithms.     

A ROBUST SQP METHOD FOR OPTIMIZATION WITH INEQUALITY CONSTRAINTS

A new algorithm for inequality constrained optimization is presented, which solves a linear programming subproblem and a quadratic subproblem at each iteration. The algorithm can circumvent the difficulties associated with the possible inconsistency of QP subproblem of the original SQP method. Moreover, the algorithm can converge to a point which satisfies a certain first-order necessary condition even if the original problem is itself infeasible. Under certain condition, some global convergence results are proved and local superlinear convergence results are also obtained. Preliminary numerical results are reported.     

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 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 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.