Parallel Dynamic Programming for Conic Linear Quadratic Control
For real-time control applications requiring fast computation on multi-core hardware, this work offers a practical speedup but is an incremental improvement over existing ADMM-based methods.
The authors tackle the serial bottleneck of solving Linear Quadratic (LQ) control problems by proposing a parallel-in-time ADMM-based approach. They achieve up to 5x speedup on multi-core CPUs compared to existing methods.
Linear Quadratic (LQ) control problems are at the heart of linear control theory and Model Predictive Control (MPC). While performant, standard approaches to solving such problems are inherently serial, limiting real-time scalability despite the parallel computing power available on modern multi-core CPUs. Contributing to addressing this challenge and motivated by ``divide and conquer'' strategies, we present a parallel-in-time approach that solves computationally demanding conic optimal control problems through the use of the alternating direction method of multipliers (ADMM). In particular, we formulate the inner primal update of ADMM as an LQ problem and split the reformulated problem along the time horizon. This enables us to derive a variant of the Riccati recursion using dynamic programming to solve each subproblem in parallel. Numerical benchmarks on two real-world applications demonstrate as much as a 5x speedup compared to existing related approaches on multi-core CPU hardware.