Fast methods for nonlinear optimization with ordinary differential equations (ODEs) and partial differential equations (PDEs) are critical to the solution of optimal control, optimal design and inverse problems in fluid, flight, structural and electrodynamics. To compute a step, based on the derivatives of the cost function and the governing differential equations, conventional methods rely on the forward and backward (adjoint) time evolution of the dynamical system. The serial nature of time stepping introduces an inherent computational bottleneck, resulting in long solution times even for relatively simple problems governed by scalar ODEs. In contrast, matrix-free composite-step sequential quadratic programming (SQP) methods [1,2] offer an interesting alternative. Specifically, they solve a sequence of convex quadratic optimization problems that lead to Karush Kuhn Tucker (KKT) saddle-point systems in which the linearized forward and adjoint time evolutions are fully coupled. This time-domain coupling, combined with the convexity of the quadratic subproblems, enables a multigrid-in-time approach.
To develop our multigrid-in-time method, we first express the KKT systems in their block-tridiagonal form, where the diagonal blocks maintain the saddle-point structure on each time interval, and the off-diagonal block expose the time coupling. From the tridiagonal form, we construct block-Jacobi and block-Gauss-Seidel fixed-point schemes. The block-Jacobi scheme is used as the pre- and post-smoother for the proposed multigrid method. This smoother is trivially parallelizable in the time domain. A Symmetric block-Gauss-Seidel (SGS) scheme is used as the preconditioner for a coarse-grid solver based on an inner GMRES iteration. The SGS scheme, which is also investigated in [3], serializes in the time domain, however its cost is acceptable as it is applied to only a handful of time steps. Our prolongation and restriction operators are based on simple one-dimensional grid projection and injection operations. We use the multigrid method as the preconditioner for an outer flexible GMRES (FGMRES) iteration.
We demonstrate excellent algorithmic scalability of the proposed multigrid-in-time approach, and the overall SQP method, on nonlinear optimization problems with ODE and PDE constraints. More concretely, the scalability extends to (i) the inner coarse-grid SGS-preconditioned GMRES method, (ii) the outer multigrid-preconditioned FGMRES method, and (iii) the SQP method. Our results also point to a very mild influence of dynamical system coefficients on the number of FGMRES iterations.

The full approximation scheme constraint decomposition (FASCD) multilevel method for solving variational inequalities (VIs) is a joint extension of both the full approximation scheme (FAS) multigrid technique for nonlinear partial differential equations, due to A. Brandt, and the constraint decomposition (CD) method introduced by X.-C. Tai for VIs arising in optimization. It extends the CD idea by exploiting the telescoping nature of certain subset decompositions arising from multilevel mesh hierarchies. When a reduced-space (active set) Newton method is applied as a smoother, with work proportional to the number of unknowns on a given mesh level, FASCD V-cycles exhibit nearly mesh-independent convergence rates. The full multigrid cycle version is observed to be an optimal solver. Example problems include differential operators which are symmetric linear, nonsymmetric linear, and nonlinear, in unilateral and bilateral VI problems.

(Note: this abstract may be updated in the future). When solving optimal control problems where the system is governed by wave propagation phenomena, each gradient calculation requires integrating the forward and adjoint PDEs. To add spatial and time parallelism to these forward and adjoint solves, we propose a waveform relaxation method with adaptive pipelining, as described in Kwok and Ong [SISC 2019]. We will study the convergence behaviour of this method applied to the wave equation and the theoretical speedup achievable when solving the overall optimal control problem.