| Large scale optimization of systems governed by partial differential equations (PDEs) is a frontier problem in scientific computation. The state-of-the-art for such problems is reduced quasi-Newton sequential quadratic programming (SQP) methods. 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 thesis we propose a new method for PDE-constrained optimization, based on the idea of full space SQP with reduced space quasi-Newton SQP preconditioning. The basic components of the method are: Newton solution of the first-order optimality conditions that characterize stationarity of the Lagrangian function; Krylov solution of the Karush-Kuhn-Tucker (KKT) linear systems arising at each Newton iteration using a symmetric quasi-minimum residual method; and 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 BFGS approximation. 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. As a remedy for divergence or convergence to saddle points, we propose several globalization techniques: line searching, deferring to quasi-Newton directions when Newton descent directions cannot be found, and continuation. Finally, we employ inexact Newton methods to achieve further savings in execution time.; To test LNKS, we solve model optimal flow control problems, with both Stokes and Navier-Stokes equations as constraints. The objective is to minimize dissipation or the deviation from a given velocity field; control variables are boundary velocities. Tests on cylinder and wing flow problems on up to 256 processors 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 1,000,000 state and 50,000 decision variables—at 5 times the cost of a single PDE solution. Finally, we describe Veltiston, an object-oriented implementation of all of the algorithms described in the thesis. |
