Optimization Online


A Regularized SQP Method with Convergence to Second-Order Optimal Points

Philip E. Gill (pgill***at***ucsd.edu)
Vyacheslav Kungurtsev (vkungurt***at***esat.kuleuven.be)
Daniel P. Robinson (daniel.p.robinson***at***jhu.edu)

Abstract: Regularized and stabilized sequential quadratic programming methods are two classes of sequential quadratic programming (SQP) methods designed to resolve the numerical and theoretical difficulties associated with ill-posed or degenerate nonlinear optimization problems. Recently, a regularized SQP method has been proposed that provides a strong connection between augmented Lagrangian methods and stabilized SQP methods. The method is formulated as a regularized SQP method with an implicit safeguarding strategy based on minimizing a bound-constrained primal-dual augmented Lagrangian. Each iteration involves the solution of a regularized quadratic program (QP) that is equivalent to a strictly convex bound-constrained QP based on minimizing a quadratic model of the augmented Lagrangian. The solution of the QP subproblem defines a descent direction for a flexible line search that provides a sufficient decrease in a primal-dual augmented Lagrangian merit function. Under certain conditions, the method is guaranteed to converge to a point satisfying the first-order Karush-Kuhn-Tucker (KKT) conditions. In this paper, the regularized SQP method is extended to allow convergence to points satisfying certain second-order KKT conditions. The method is based on performing a flexible line search along a direction formed from the solution of a strictly convex regularized quadratic programming subproblem and, when one exists, a direction of negative curvature for the primal-dual augmented Lagrangian. It is shown that with an appropriate choice of termination condition, the method terminates in a finite number of iterations. As in the first-order case, the method is formulated as a regularized SQP method with an augmented Lagrangian safeguarding strategy. It is shown that this safeguarding becomes relevant only when the iterates are converging to an infeasible stationary point of the constraint violations. Otherwise, the method terminates with a point that either satisfies the second-order necessary conditions for optimality, or fails to satisfy a weak second-order constraint qualification.

Keywords: Nonlinear programming, augmented Lagrangian, sequential quadratic programming, SQP methods, stabilized SQP, regularized methods, primal-dual methods, second-order optimality.

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: UCSD Center for Computational Mathematics Technical Report CCoM-13-4 October 30, 2013

Download: [PDF]

Entry Submitted: 10/30/2013
Entry Accepted: 10/31/2013
Entry Last Modified: 10/31/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society