A TRUNCATED SQP METHOD BASED ON INEXACT INTERIOR-POINT SOLUTIONS OF SUBPROBLEMS

作者：Izmailov A F^*; Solodov M V

来源：SIAM Journal on Optimization, 2010, 20(5): 2584-2613.

DOI：10.1137/090758015

• sequential quadratic programming
• inexact sequential quadratic programming
• truncated sequential quadratic programming
• interior-point method
• superlinear convergence

We consider sequential quadratic programming (SQP) methods applied to optimization problems with nonlinear equality constraints and simple bounds. In particular, we propose and analyze a truncated SQP algorithm in which subproblems are solved approximately by an infeasible predictor-corrector interior-point method, followed by setting to zero some variables and some multipliers so that complementarity conditions for approximate solutions are enforced. Verifiable truncation conditions based on the residual of optimality conditions of subproblems are developed to ensure both global and fast local convergence. Global convergence is established under assumptions that are standard for linesearch SQP with exact solution of subproblems. The local superlinear convergence rate is shown under the weakest assumptions that guarantee this property for pure SQP with exact solution of subproblems, namely, the strict Mangasarian-Fromovitz constraint qualification and second-order sufficiency. Local convergence results for our truncated method are presented as a special case of the local convergence for a more general perturbed SQP framework, which is of independent interest and is applicable even to some algorithms whose subproblems are not quadratic programs. For example, the framework can also be used to derive sharp local convergence results for linearly constrained Lagrangian methods. Preliminary numerical results confirm that it can be indeed beneficial to solve subproblems approximately, especially on early iterations.

• 出版日期2010