A Regularized SQP Method with Convergence to Second-Order Optimal Points
Philip E. Gill (pgillucsd.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
Entry Submitted: 10/30/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|