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.