On Temporal Decomposition for Parallel Solution of Equality Constrained Optimal Control Problems

ABSTRACT In this contribution, we discuss temporal decomposition techniques tailored to stagewise and terminal equality constrained discrete time optimal control problems. Such decomposition allows for parallel treatment of the problem when multiple computational cores are available. Each core handles a subtrajectory of the optimal control problem conditioned by an arbitrary terminal state. Rather than relying on Lagrangian multipliers to account for the various stagewise and terminal equality constraints, the discussed approach relies on an explicit parametric representation and backtracing of the subproblems' value function domains. We show how the solution to the original problem can be retrieved optimally by means of a parallel prefix sum algorithm. For the equality‐constrained linear quadratic optimal control problem, the time complexity reduces approximately to from with the horizon and the number of cores. The actual ratio suffers from auxiliary effects, yet for medium‐ to long‐horizon problems and sufficiently many cores, significant speed‐up can still be achieved. The present study focuses on the theoretical development of the parallel formulation of constrained dynamic programming and specializes the result to the linear‐quadratic setting.