Dual-Regularized Riccati Recursions for Interior-Point Optimal Control
For researchers in optimal control and robotics, this provides a scalable and certifiable method for solving constrained trajectory optimization problems, particularly beneficial for long horizons and high dimensions.
The paper derives closed-form extensions of Riccati recursions for dual-regularized LQR problems, enabling efficient solution of constrained non-convex optimal control problems via interior-point methods, with O(N) sequential and O(log N) parallel time. Benchmarking shows competitive performance on moderate problems and substantial gains as problem size increases.
We derive closed-form extensions of the sequential and parallel Riccati recursions for solving dual-regularized linear-quadratic regulator (LQR) problems, with $O(N)$ sequential time and $O(\log(N))$ parallel time, respectively. We show that these subproblems arise when using regularized primal-dual interior-point methods to solve smooth, constrained, non-convex, discrete-time optimal control problems via multiple-shooting, even in the presence of stagewise equality or inequality constraints, and without imposing any rank requirements on constraint Jacobians. We prove that, when certain inertia conditions on the Newton-KKT matrix are met, each nonzero primal step is a descent direction of an augmented barrier-Lagrangian merit function. We characterize these inertia conditions in terms of the positive-definiteness of the dual-regularized Riccati pivots (a weaker condition than the standard LQR positive-definiteness requirements), thereby yielding inexpensive certificates of the required inertia. We provide MIT-licensed implementations of our methods in C++ and in JAX, as well as a full formalization of our results in Lean. We benchmark our algorithm against leading optimal control and nonlinear programming solvers on complex trajectory optimization problems, establishing competitive performance on moderate problems and substantial gains as the horizon length, problem dimension, and constraint count increase.