id: 05029110
dt: j
an: 05029110
au: Biros, George; Ghattas, Omar
ti: Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained
    optimization. I: The Krylov-Schur solver.
so: SIAM J. Sci. Comput. 27, No. 2, 687-713 (2005).
py: 2005
pu: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
la: EN
cc: 
ut: sequential quadratic programming; nonlinear equations; parallel algorithms;
    adjoint methods; PDE-constrained optimization; optimal control;
    Lagrange-Newton-Krylov-Schur methods; Navier-Stokes equation; finite
    elements; preconditioners; indefinite systems; numerical experiments
ci: Zbl 1091.65063
li: doi:10.1137/S106482750241565X
ab: Summary: Large-scale optimization of systems governed by partial
    differential equations (PDEs) is a frontier problem in scientific
    computation. Reduced quasi-Newton sequential quadratic programming
    (SQP) methods are state-of-the-art approaches for such problems. These
    methods take full advantage of existing PDE solver technology and
    parallelize well. However, their algorithmic scalability is
    questionable; for certain problem classes they can be very slow to
    converge.  In this two-part article we propose a new method for
    steady-state PDE-constrained optimization, based on the idea of using a
    full space Newton solver combined with an approximate reduced space
    quasi-Newton SQP preconditioner. The basic components of the method are
    a Newton solution of the first-order optimality conditions that
    characterize stationarity of the Lagrangian function; the Krylov
    solution of the Karush-Kuhn-Tucker (KKT) linear systems arising at each
    Newton iteration using a symmetric quasi-minimum residual method;
    preconditioning of the KKT system using an approximate state/decision
    variable decomposition that replaces the forward PDE Jacobians by their
    own preconditioners, and the decision space Schur complement (the
    reduced Hessian) by a Broyden-Fletcher-Goldfarb-Shanno approximation
    initialized by a two-step stationary method. Accordingly, we term the
    new method Lagrange-Newton-Krylov-Schur (LNKS). It is fully
    parallelizable, exploits the structure of available parallel algorithms
    for the PDE forward problem, and is locally quadratically convergent. 
    In part I of this two-part article, we investigate the effectiveness of
    the KKT linear system solver. We test our method on two optimal control
    problems in which the state constraints are described by the
    steady-state Stokes equations. The objective is to minimize dissipation
    or the deviation from a given velocity field; the control variables are
    the boundary velocities. Numerical experiments on up to 256 Cray T3E
    processors and on an SGI Origin 2000 include scalability and
    performance assessment of the LNKS algorithm and comparisons with
    reduced SQP for up to $1,000,000$ state and 50,000 decision variables.
    In part II of the article [ibid. 27, No.~2, 714‒739 (2005; reviewed
    below)], we address globalization and inexactness issues, and apply
    LNKS to the optimal control of the steady incompressible Navier-Stokes
    equations.
rv: