A Flexible Iterative Solver for Nonconvex, Equality-Constrained Quadratic Subproblems

Abstract

We present an iterative primal-dual solver for nonconvex equality-constrained quadratic optimization subproblems. The solver constructs the primal and dual trial steps from the subspace generated by the generalized Arnoldi procedure used in flexible GMRES (FGMRES). This permits the use of a wide range of preconditioners for the primal-dual system. In contrast with FGMRES, the proposed method selects the subspace solution that minimizes a quadratic penalty function over a trust region. Analysis of the method indicates the potential for fast asymptotic convergence near the solution, which is corroborated by numerical experiments. The results also demonstrate the effectiveness and efficiency of the method in the presence of nonconvexity. Overall, the iterative solver is a promising matrix-free linear algebra kernel for inexact-Newton optimization algorithms and is well-suited to partial differential equation–constrained optimization.

Publication
SIAM Journal on Scientific Computing