Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver

Abstract. In this paper we follow up our discussion on algorithms suitable for optimization of systems governed by partial differential equations. In the first part of of this paper we proposed a Lagrange-Newton-Krylov-Schur method (LNKS) that uses Krylov iterations to solve the Karush-Kuhn-Tucker system of optimality conditions, but invokes a preconditioner inspired by reduced space quasi-Newton algorithms. In the second part we focus our discussion to the outer iteration and we provide details on how to obtain a robust and globally convergent algorithm. Newton’s step is known to lead to divergence for points far from the optimum. Furthermore for highly nonlinear problems the computation of a step by itself is very difficult (for both QN-RSQP and LNKS methods). As a remedy we employ line search methods, mixing quasi-Newton with Newton algorithms and continuation. We test the globalized LNKS algorithm on a optimal flow control problem were the constraints are the steady incompressible Navier-Stokes equations. The objective function is the minimization of the dissipation functional. We report results from runs on up to 128 processors on a T3E-900 at the Pittsburgh Supercomputing Center. Tests on cylinder and wing flow problems demonstrate the very good parallelism and scalability of the new method. Moreover, LNKS is an order of magnitude faster than reduced quasi-Newton SQP, and we are able to solve previously intractable problems of up to 800,000 state and 5,000 decision variables—at 5 times the cost of a single PDE solution. 1. Introduction. In the first part of the paper we concentrated on the Krylov-Schu