Trust-region SQP methods with inexact linear system solves for large-scale optimization

[摘要] This thesis extends the design and the global convergence analysis of a class of trust-region sequential quadratic programming (SQP) algorithms for smooth nonlinear optimization to allow for an efficient integration of inexact linear system solvers. Each iteration within an SQP method requires the solution of several linear systems, whose system matrix/operator involves the linearized constraints. Most existing implementations of SQP algorithms use direct linear algebra methods to solve these systems. For many optimization problems in science and engineering this is infeasible, because the systems are too large or the matrices associated with the linearized constraints are not formed explicitly. Instead, iterative solvers, such as preconditioned Krylov subspace methods have to be applied for the approximate solution of the linear systems arising within the SQP algorithm. In this case, the optimization algorithm has to provide stopping tolerances for the iterative solver. The existing literature on the treatment of inexact linear system solves in SQP algorithms is rather scarce. Most theoretical results either provide stopping tolerances for iterative solvers that cannot be easily implemented in practice, or are restricted to specific classes of optimization problems. This thesis provides concrete stopping criteria for the iterative solution of so-called augmented systems; which allows for a wider applicability of the resulting SQP algorithm and a rigorous integration of available KKT preconditioners. A key contribution is the development of an inexact conjugate gradient algorithm for the solution of quadratic subproblems with linear constraints that are subject to arbitrary nonlinear perturbations that arise from the approximate computation of projections via Krylov subspace methods. The resulting SQP algorithm dynamically adjusts stopping tolerances for iterative linear system solves based on its current progress toward a KKT point. The stopping tolerances can be easily implemented and efficiently computed, and are sufficient to guarantee first-order global convergence of the algorithm. The performance of the algorithm is examined on optimal control problems governed by Burgers and Navier-Stokes equations.

[发布机构] Rice University