Dual-Regularized Riccati Recursions for Interior-Point Optimal Control
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An interior-point stochastic approximation method and an L1-regularized delta rule
The stochastic approximation method is behind the solution to many important, actively-studied problems in machine learning. Despite its far-reaching application, there is almost no work on applying stochastic approximat…
BIG-bench Machine Learningfeature selectionFaster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs
Linear programming (LP) is used in many machine learning applications, such as $\ell_1$-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular m…
Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent
Over the past decades, Linear Programming (LP) has been widely used in different areas and considered as one of the mature technologies in numerical optimization. However, the complexity offered by state-of-the-art algor…
Regularized Model Predictive Control
In model predictive control (MPC), the choice of cost-weighting matrices and designing the Hessian matrix directly affects the trade-off between rapid state regulation and minimizing the control effort. However, traditio…
modelModel Predictive ControlReinforcement learning for adaptive interior point methods in convex quadratic programming
Quadratic programming is a workhorse of modern nonlinear optimization, control, and data science. Although regularized methods offer convergence guarantees under minimal assumptions on the problem data, they can exhibit …
Reinforcement Learning