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.     

A Globally and Superlinearly Convergent SQP Algorithm for Nonlinear Constrained Optimization

Based on a continuously differentiable exact penalty function and a regularization technique for dealing with the inconsistency of subproblems in the SQP method, we present a new SQP algorithm for nonlinear constrained optimization problems. The proposed algorithm incorporates automatic adjustment rules for the choice of the parameters and makes use of an approximate directional derivative of the merit function to avoid the need to evaluate second order derivatives of the problem functions. Under mild assumptions the algorithm is proved to be globally convergent, and in particular the superlinear convergence rate is established without assuming that the strict complementarity condition at the solution holds. Numerical results reported show that the proposed algorithm is promising.     

On the convergence of a new trust region algorithm

Summary. In this paper we present a new trust region algorithm for general nonlinear constrained optimization problems. The algorithm is based on the exact penalty function. Under very mild conditions, global convergence results for the algorithm are given. Local convergence properties are also studied. It is shown that the penalty parameter generated by the algorithm will be eventually not less than the norm of the Lagrange multipliers at the accumulation point. It is proved that the method is equivalent to the sequential quadratic programming method for all large , hence superlinearly convergent results of the SQP method can be applied. Numerical results are also reported. Received March 21, 1993     

New sequential quadratic programming algorithm with consistent subproblems

One of the most interesting topics related to sequential quadratic programming algorithms is how to guarantee the consistence of all quadratic programming subproblems. In this decade, much work trying to change the form of constraints to obtain the consistence of the subproblems has been done. The method proposed by De O. Pantoja J.F. A. and coworkers solves the consistent problem of SQP method, and is the best to the authors’ knowledge. However, the scale and complexity of the subproblems in De O. Pantoja’s work will be increased greatly since all equality constraints have to be changed into absolute form. A new sequential quadratic programming type algorithm is presented by means of a special ε-active set scheme and a special penalty function. Subproblems of the new algorithm are all consistent, and the form of constraints of the subproblems is as simple as one of the general SQP type algorithms. It can be proved that the new method keeps global convergence and Local superlinear convergence. Project partly supported by the National Natural Science Foundation of China.     

一个等式约束问题的SQP方法及其收敛性

本文提出一个SQP算法,其效益函数为Flether^[1]提出的连续可微精确罚函数。该算法具有全局收敛性和超线性收敛速度,并且能自动调节罚参数,能有效地处理计算搜索方向的二次子规划的不可行问题。     

半无限规划离散化问题一个两阶段序列二次规划算法

本文研究了求解半无限规划离散化问题(P)的一个新的算法.利用序列二次规划(SQP)两阶段方法和约束指标集的修正技术,提出了求解(P)的一个两阶段SQP算法.算法结构简单,搜索方向的计算成本较低.在适当的条件下,证明了算法具有全局收敛性.数值试验结果表明算法是有效的.推广了文献[4]中求解(P)的算法.     

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.     

非线性互补约束均衡问题的一个滤子SQP算法

提出了—个求解非线性互补约束均衡问题的滤子SQP算法.借助Fischer-Burmeister函数把均衡约束转化为—个非光滑方程组,然后利用逐步逼近和分裂思想,给出—个与原问题近似的一般的约束优化.引入滤子思想,避免了罚函数法在选择罚因子上的困难.在适当的条件下证明了算法的全局收敛性,部分的数值结果表明算法是有效的.     

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

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

An SQP algorithm with cautious updating criteria for nonlinear degenerate problems

An efficient SQP algorithm for solving nonlinear degenerate problems is proposed in the paper. At each iteration of the algorithm, a quadratic programming subproblem, which is always feasible by introducing a slack variable, is solved to obtain a search direction. The steplength along this direction is computed by employing the 1∞ exact penalty function through Armijo-type line search scheme. The algorithm is proved to be convergent globally under mild conditions.     

A robust SQP method based on a smoothing lower order penalty function†

Based on a smoothing approximation of a lower order penalty function and following Facchinei's method of dealing with the inconsistency of subproblems in SQP methods, we present a new robust SQP algorithm for solving a nonlinear constrained optimization problem. The proposed algorithm incorporates automatic adjustment rules for the choice of parameters. Under a new regularity condition at infeasible points, the algorithm is proved to be globally convergent.     

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.     

不等式约束优化的非单调可行信赖域-SQP算法

本文讨论不等式约束优化问题,给出一个信赖域方法与SQP方法相结合的新的可行算法,算法中采用了压缩技术,使得QP子问题产生的搜索方向尽可能为可行方向,并且采用了高阶校正的方法来克服算法产生的Maratos效应现象.在适当的条件下,证明了算法的全局收敛性和超线性收敛性.数值结果表明算法是有效的.     

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

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

A New Superlinearly Convergent Strongly Subfeasible Sequential Quadratic Programming Algorithm for Inequality-Constrained Optimization

Combining the ideas of generalized projection and the strongly subfeasible sequential quadratic programming (SQP) method, we present a new strongly subfeasible SQP algorithm for nonlinearly inequality-constrained optimization problems. The algorithm, in which a new unified step-length search of Armijo type is introduced, starting from an arbitrary initial point, produces a feasible point after a finite number of iterations and from then on becomes a feasible descent SQP algorithm. At each iteration, only one quadratic program needs to be solved, and two correctional directions are obtained simply by explicit formulas that contain the same inverse matrix. Furthermore, the global and superlinear convergence results are proved under mild assumptions without strict complementarity conditions. Finally, some preliminary numerical results show that the proposed algorithm is stable and promising.     

不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法

针对带不等式约束的极大极小问题,借鉴一般约束优化问题的模松弛强次可行SQP算法思想,提出了求解不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法.首先,通过在QCQP子问题中选取合适的罚函数,保证了算法的可行性以及目标函数F(x)的下降性,同时简化QCQP子问题二次约束项参数α_k的选取,可保证算法的可行性和收敛性.其次,算法步长的选取合理简单.最后,在适当的假设条件下证明了算法具有全局收敛性及强收敛性.初步的数值试验结果表明算法是可行有效的.     

Superlinear Convergence of a Smooth Approximation Method for Mathematical Programs with Nonlinear Complementarity Constraints

<正>Mathematical programs with complementarity constraints(MPCC) is an important subclass of MPEC.It is a natural way to solve MPCC by constructing a suitable approximation of the primal problem.In this paper,we propose a new smoothing method for MPCC by using the aggregation technique.A new SQP algorithm for solving the MPCC problem is presented.At each iteration,the master direction is computed by solving a quadratic program,and the revised direction for avoiding the Maratos effect is generated by an explicit formula.As the non-degeneracy condition holds and the smoothing parameter tends to zero,the proposed SQP algorithm converges globally to an S-stationary point of the MPEC problem,its convergence rate is superlinear.Some preliminary numerical results are reported.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

A superlinearly and quadratically convergent SQP type feasible method for constrained optimization

A new SQP type feasible method for inequality constrained optimization is presented, it is a combination of a master algorithm and an auxiliary algorithm which is taken only in finite iterations. The directions of the master algorithm are generated by only one quadratic programming, and its step-size is always one, the directions of the auxiliary algorithm are new “secondorder“ feasible descent. Under suitable assumptions, the algorithm is proved to possess global and strong convergence, superlinear and quadratic convergence.     

求解极小极大问题的非单调过滤算法

提出一种改进的求解极小极大问题的信赖域滤子方法,利用SQP子问题来求一个试探步,尾服用滤子来衡量是否接受试探步,避免了罚函数的使用;并且借用已有文献的思想, 使用了Lagrange函数作为效益函数和非单调技术,在适当的条件下,分析了算法的全局和局部收敛性,并进行了数值实验.