A second-derivative SQP method with a 'trust-region-free' predictor step

作者：Gould Nicholas I M; Robinson Daniel P^*

来源：IMA Journal of Numerical Analysis, 2012, 32(2): 580-601.

DOI：10.1093/imanum/drq043

• nonlinear programming
• nonlinear inequality constraints
• sequential quadratic programming
• l(1)-penalty function
• nonsmooth optimization

Gould and Robinson (2010, SIAM J. Optim., 20, 2023-2048; 2010, SIAM J. Optim., 20, 2049-2079) introduced a second-derivative sequential quadratic programming method (S2QP) for solving nonlinear nonconvex optimization problems. We proved that the method is globally and locally superlinearly convergent under common assumptions. A critical component of the algorithm is the so-called predictor step, which is computed from a strictly convex quadratic program with a trust-region constraint. This step is essential for proving global convergence but its propensity to identify the optimal active set is paramount for achieving fast local convergence. Thus the global and local efficiency of the method is intimately coupled with the quality of the predictor step. In this paper we study the effects of removing the trust-region constraint from the computation of the predictor step. This is reasonable since the resulting problem is still strictly convex and thus well defined. Although it is interesting theoretically to verify that the same convergence guarantees hold when no trust-region constraint is used, our motivation is based on the practical behaviour of the algorithm. Preliminary numerical experience with S2QP indicates that the trust-region constraint occasionally degrades the quality of the predictor step and diminishes its ability to correctly identify the optimal active set. Moreover, removal of the trust-region constraint allows for re-use of the predictor step over a sequence of failed iterations, thus reducing computation. We show that the modified algorithm remains globally convergent and preserves local superlinear convergence provided that a nonmonotone strategy is incorporated.

• 出版日期2012-4