arXiv:2407.05433 · v9

An Efficient Parallel Solver for Linear-Equality-Constrained LQR Problems

首次提交 2024-07-08 00:36

版本更新 2026-10-26 08:39

雷达观测 2026-10-29 00:36

摘要

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.

作者备注：Accepted for publication in IEEE Control Systems Letters (L-CSS) on October 25th, 2026