[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
A Stabilized SQP Method: Global Convergence
by Philip E. Gill, Vyacheslav Kungurtsev, Daniel P. Robinson
Abstract:
Stabilized sequential quadratic programming (SQP) methods for nonlinear optimization are designed to provide a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the global convergence properties of a stabilized SQP method with a primal-dual augmented Lagrangian merit function. The proposed method incorporates several novel features. (i) A flexible line search is used based on a direction formed from an approximate solution of a strictly convex QP subproblem and, when one exists, a direction of negative curvature for the primal-dual merit function. (ii) When certain conditions hold, an approximate QP solution is computed by solving a single linear system defined in terms of an estimate of the optimal active set. The conditions exploit the formal equivalence between the conventional stabilized SQP subproblem and a bound-constrained QP associated with minimizing a quadratic model of the merit function. (iii) It is shown that with an appropriate choice of termination condition, the method terminates in a finite number of iterations without the assumption of a constraint qualification. The method may be interpreted as an SQP method with an augmented Lagrangian safeguarding strategy. This safeguarding becomes relevant only when the iterates are converging to an infeasible stationary point of the norm of the constraint violations. Otherwise, the method terminates with a point that approximately satisfies certain second-order necessary conditions for optimality. In this situation, if all termination conditions are removed, then the limit points either satisfy the same second-order necessary conditions exactly or fail to satisfy a weak second-order constraint qualification. (iv) The global convergence analysis concerns a specific algorithm that estimates the least curvature of the merit function at each step. If negative curvature directions are omitted, the analysis still applies and establishes convergence to either first-order solutions or infeasible stationary points. The superlinear convergence of the iterates and the formal local equivalence to stabilized SQP is established in a companion paper (Report CCoM 14-01, Center for Computational Mathematics}, University of California, San Diego, 2014.
UCSD-CCoM-13-04.pdf October 2013
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
by Philip E. Gill, Vyacheslav Kungurtsev, Daniel P. Robinson
Abstract:
Stabilized sequential quadratic programming (SQP) methods for nonlinear optimization are designed to provide a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the global convergence properties of a stabilized SQP method with a primal-dual augmented Lagrangian merit function. The proposed method incorporates several novel features. (i) A flexible line search is used based on a direction formed from an approximate solution of a strictly convex QP subproblem and, when one exists, a direction of negative curvature for the primal-dual merit function. (ii) When certain conditions hold, an approximate QP solution is computed by solving a single linear system defined in terms of an estimate of the optimal active set. The conditions exploit the formal equivalence between the conventional stabilized SQP subproblem and a bound-constrained QP associated with minimizing a quadratic model of the merit function. (iii) It is shown that with an appropriate choice of termination condition, the method terminates in a finite number of iterations without the assumption of a constraint qualification. The method may be interpreted as an SQP method with an augmented Lagrangian safeguarding strategy. This safeguarding becomes relevant only when the iterates are converging to an infeasible stationary point of the norm of the constraint violations. Otherwise, the method terminates with a point that approximately satisfies certain second-order necessary conditions for optimality. In this situation, if all termination conditions are removed, then the limit points either satisfy the same second-order necessary conditions exactly or fail to satisfy a weak second-order constraint qualification. (iv) The global convergence analysis concerns a specific algorithm that estimates the least curvature of the merit function at each step. If negative curvature directions are omitted, the analysis still applies and establishes convergence to either first-order solutions or infeasible stationary points. The superlinear convergence of the iterates and the formal local equivalence to stabilized SQP is established in a companion paper (Report CCoM 14-01, Center for Computational Mathematics}, University of California, San Diego, 2014.
UCSD-CCoM-13-04.pdf October 2013