提出新型Riccati递推法,高效求解带正则化的最优控制问题。
Dual-Regularized Riccati Recursions for Interior-Point Optimal Control
- 基于双重正则化LQR构造串行与并行Riccati递推公式
- 在长时域、高维、多约束下性能优于主流求解器
- 提供可验证的数学条件与开源实现,适合控制算法研究者
我们推导了用于求解双重正则化线性二次调节器(LQR)问题的闭式串行与并行Riccati递推方法,分别具有O(N)串行时间复杂度和O(log(N))并行时间复杂度。我们证明,当使用带正则化的原始-对偶内点法通过多段射击法求解平滑、有约束、非凸的离散时间最优控制问题时,这些子问题自然出现,即使存在逐阶段等式或不等式约束,且无需对约束雅可比矩阵施加秩条件。我们证明,当满足Newton-KKT矩阵的某些惯性条件时,每个非零原始步均为增广障碍-拉格朗日势函数的下降方向。我们以双重正则化Riccati主元的正定性来刻画这些惯性条件(弱于标准LQR要求),从而获得廉价的惯性验证。我们提供了C++与JAX中的MIT许可证实现,以及在Lean中完整的形式化证明。我们在复杂轨迹优化问题上对比了领先的最优控制与非线性规划求解器,结果显示,在中等规模问题上表现相当,而随着时域长度、问题维度和约束数量增加,性能优势显著提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。