A Matrix-Free Trust-Region SQP Method for Equality Constrained Optimization

M. Heinkenschloss
Department of Computational and Applied Mathematics
Rice University

D. Ridzal
Optimization and Uncertainty Quantification
Sandia National Laboratories


SIAM Journal on Optimization, 2014, Vol. 24, No. 3, pp.1507-1541.

Abstract

We introduce and analyze a trust--region sequential quadratic programming (SQP) method for the solution of smooth equality constrained optimization problems, which allows the inexact and hence iterative solution of linear systems. Iterative solution of linear systems is important in large-scale applications, such as optimization problems with partial differential equation constraints, where direct linear solves are too expensive or not applicable because system matrices are never formed explicitly. Our trust-region SQP algorithm is based on a composite-step approach which decouples the step into a quasi-normal and a tangential step and includes several critical modifications of step computations needed to cope with the inexact solution of linear systems. The global convergence of our algorithm is guaranteed under rather general conditions on the substeps. We propose algorithms to compute the substeps and prove that these algorithms satisfy the conditions to ensure global convergence. All components of the resulting algorithm are specified in such a way that they can be directly implemented. Our linear solver stopping criteria accommodate user-supplied parameters that can be used to tune the efficiency of the algorithm, yet they are free of Lipschitz constants and other application-dependent parameters that are difficult or impossible to compute. Numerical results indicate that our algorithm converges even for very coarse linear solver requirements. Furthermore, the linear solver stopping criteria are adapted to the convergence of the overall SQP algorithm. Coarse and therefore inexpensive linear system solves are used frequently.

Keywords

Sequential quadratic programming, trust-region, large-scale optimization, matrix-free, inexact linear system solvers, PDE constrained optimization, Krylov subspace methods.

See also D. Ridzal, M. Aguilo and M. Heinkenschloss, Numerical study of a matrix-free trust-region SQP method for equality constrained optimization. Sandia National Laboratories Technical Report SAND 2011-9346.