The ParaOpt algorithm was recently introduced as a time-parallel solver for optimal-control problems with a terminal-cost objective, and convergence results have been presented for the linear diffusive case with implicit-Euler time integrators. We reformulate ParaOpt for tracking problems and provide generalized convergence analyses for both objectives. We focus on linear diffusive equations and prove convergence bounds that are generic in the time integrators used. For large problem dimensions, ParaOpt's performance depends crucially on having a good preconditioner to solve the arising linear systems. For the case where ParaOpt's cheap, coarse-grained propagator is linear, we introduce diagonalization-based preconditioners, inspired by recent advances in the ParaDiag family of methods. These preconditioners not only lead to a weakly-scalable ParaOpt version, but are themselves invertible in parallel, making maximal use of available concurrency. They have proven convergence properties in the linear diffusive case that are generic in the time discretization used, similarly to our ParaOpt results. Numerical results confirm that the iteration count of the iterative solvers used for ParaOpt's linear systems becomes constant in the limit of an increasing processor count. The paper is accompanied by a sequential MATLAB implementation.
翻译:Translated abstract:
ParaOpt算法是一种时间并行求解器,用于具有终端成本目标的最优控制问题,并且已证明在具有隐式欧拉时间积分器的线性扩散情况下具有收敛结果。我们针对跟踪问题重新构造ParaOpt并提供两个目标的广义收敛分析。我们将重点放在线性扩散方程上,并证明了这些收敛界限在使用的时间积分器中是通用的。对于大规模问题维数,ParaOpt的性能关键取决于具有良好预处理器来解决出现的线性系统。对于ParaOpt的方便、粗粒度传播是线性的情况,我们介绍了基于对角化的预处理器,它受ParaDiag方法家族最新进展的启发。这些预处理器不仅会导致一个弱可伸缩的ParaOpt版本,而且在并行中本身是可逆的,使最大利用可用并发性。在线性扩散情况下,它们具有通用于使用时间离散化的收敛性质,与ParaOpt的结果类似。数值结果证实,ParaOpt线性系统使用的迭代求解器的迭代次数在处理器数目增加到极限时变为常数。本文附带一个顺序MATLAB实现。