We present a parallel solver for finite-horizon linear-quadratic regulator (LQR) problems with arbitrary stagewise linear equality constraints, using linear work and logarithmic depth in the horizon for fixed local dimensions. The solver uses a two-part reduction that separates feasibility from optimization. First, an associative suffix scan computes the states from which each remaining horizon is feasible. Second, we use these feasible-continuation sets to eliminate the constraints independently at each stage, producing an unconstrained LQR problem with smaller or equal, possibly stage-varying dimensions. A parallel unconstrained-LQR solver completes the primal solution. Finally, we recover valid multipliers from the original KKT stationarity equations using a logarithmic-depth contraction-expansion procedure, even when the multipliers are not unique. Sequential and parallel implementations are validated against dense KKT solutions and original residuals. We release a C++/CUDA implementation with JAX bindings under the MIT license.
Figures & tables
Fig. 1: Median solve time versus horizon at fixed state dimension.
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.
Luyao Zhang, Gabriel Bravo-Palacios, Brian Plancher +1
Delft Center for Systems and Control, TU Delft, The Netherlands · Barnard College, Columbia University, New York, NY 10027 USA · & Dartmouth College, Hanover, NH 03755, USA
In this article, we present socx, a GPU-accelerated solver for lifted convex reformulations of linear stochastic optimal control under chance constraints, implemented in JAX. We demonstrate that by exploiting the sparse and independent structure of the problem, distributed optimization can reduce it to simpler problems: independent linear-quadratic tracking (LQT) problems and Euclidean projections onto sets. These simpler problems can be solved in parallel and then coupled using the constraints. To validate our solver, we run it on a hover-linearized 3D quadrotor and show a speed-up of up to 98× over MOSEK and up to 2224× over SCS. socx also solves horizons up to N=1120, whereas MOSEK runs out of memory at N=320. We present ablations to isolate the key components that enable the speed-up.
Tanmay Dokania, Yashwanth Kumar Nakka
Authors are with the Daniel Guggenheim School of Aerospace Engineering at the Georgia Institute of Technology, Atlanta, GA, 30332 USA.
Inspired by REINFORCE, we introduce a novel receding-horizon algorithm for the Linear Quadratic Regulator (LQR) problem with unknown dynamics. Unlike prior methods, our algorithm avoids reliance on two-point gradient estimates while maintaining the same order of sample complexity. Furthermore, it eliminates the restrictive requirement of starting with a stable initial policy, broadening its applicability. Beyond these improvements, we introduce a refined analysis of error propagation through the contraction of the Riccati operator under the Riemannian distance. This refinement leads to a better sample complexity and ensures improved convergence guarantees.
Amirreza Neshaei Moghaddam, Alex Olshevsky, Bahman Gharesifard