A new diagonalization based method for parallel-in-time solution of linear-quadratic optimal control problems

¹ Department of Computational Applied Mathematics & Operations Research, MS-134, Rice University, 6100 Main Street, Houston, TX 77005-1892, USA
² Department of Statistics, MS-138, Rice University, 6100 Main Street, Houston, TX 77005-1892, USA

^* Corresponding author: heinken@rice.edu

Received: 12 September 2022
Accepted: 12 July 2024

Abstract

A new diagonalization technique for the parallel-in-time solution of linear-quadratic optimal control problems with time-invariant system matrices is introduced. The target problems are often derived from a semi-discretization of a Partial Differential Equation (PDE)-constrained optimization problem. The solution of large-scale time dependent optimal control problems is computationally challenging as the states, controls, and adjoints are coupled to each other throughout the whole time domain. This computational difficulty motivates the use of parallel-in-time methods. For time-periodic problems our diagonalization efficiently transforms the discretized optimality system into n_t (=number of time steps) decoupled complex valued 2n_y × 2n_y systems, where ny is the dimension of the state space. These systems resemble optimality systems corresponding to a steady-state version of the optimal control problem and they can be solved in parallel across the time steps, but are complex valued. For optimal control problems with initial value state equations a direct solution via diagonalization is not possible, but an efficient preconditioner can be constructed from the corresponding time periodic optimal control problem. The preconditioner can be efficiently applied parallel-in-time using the diagonalization technique. The observed number of preconditioned GMRES iterations is small and insensitive to the size of the problem discretization.