Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver
Parallel Lagrange-Newton-Krylov-Schur methods for PDE-constrained optimization. Part I: The Krylov-Schur solver
复制标题
DOI：
10.1137/s106482750241565x
复制
发表时间：
2005-01-01
影响因子：
3.1
通讯作者：
Ghattas, O
中科院分区：
文献类型：
--
作者：
Biros, G;Ghattas, O
由部分微分方程（PDE）控制的系统的大规模优化是科学计算中的前沿问题。降低的准Newton顺序二次编程（SQP）方法是解决此类问题的最新方法。这些方法充分利用了现有的PDE求解器技术，并平行得很好。但是，它们的算法可伸缩性值得怀疑。对于某些问题类别，它们的收敛速度可能很慢。在这两部分的文章中，我们提出了一种新方法，以使用完整的空间牛顿求解器与近似降低的空间Quasi-Newton SQP Proventioner相结合的想法。该方法的基本组件是表征拉格朗日函数平稳性的一阶最佳条件的牛顿解决方案。 Karush -Kuhn -Tucker（KKT）线性系统的Krylov解决方案，使用对称的准级剩余方法在每个牛顿迭代时出现；使用近似状态/决策变量分解对KKT系统的预处理，该分解代替了自己的前提条件，并通过BFGS近似（由两步式平稳方法初始化的BFGS近似值）代替了前向PDE Jacobians，而决策空间Schur补充（减少了Hessian）。因此，我们称新方法拉格朗日-Newton -Krylov -Schur（LNKS）。它是完全并行的，可利用PDE正向问题的可用并行算法的结构，并且在局部四边形收敛。在这本两部分文章的第一部分中，我们研究了KKT线性系统求解器的有效性。我们在两个最佳控制问题上测试我们的方法，其中稳态Stokes方程描述了状态约束。目的是最大程度地减少耗散或与给定速度场的偏差；控制变量是边界速度。最多256个Cray T3E处理器和SGI Origin 2000的数值实验包括对LNKS算法的可伸缩性和性能评估以及与SQP减少的比较，最高可达1、000、000个状态和50,000个决策变量。在本文的第二部分中，我们解决了全球化和不符合性问题，并将LNK应用于对稳定不可压缩的Navier-Stokes方程的最佳控制。
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 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; 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 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, we address globalization and inexactness issues, and apply LNKS to the optimal control of the steady incompressible Navier-Stokes equations.