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


CAAM Technical Report TR11-17

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 iterative and hence inexact solution of linear systems. The 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 included several important modifications of step computations needed to cope with inexact solution of linear systems. The global convergence of our algorithm is guaranteed under rather general conditions on the sub-steps. We propose algorithms to compute the sub-steps 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 system solver stopping criteria depend on user-specified parameters that can be used to tune the efficiency of the algorithm, but they are free of Lipschitz constants and other application dependent parameters that are not computable or only very expensive to compute. Our numerical results indicate that our algorithm is insensitive to user supplied parameters and converges even for very coarse linear solver requirements. Furthermore, the linear system 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.

PDF file of technical report.

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.