2025-11-23T02:40:16.760420

Dual-Regularized Riccati Recursions for Interior-Point Optimal Control

Sousa-Pinto, Orban
We derive closed-form extensions of Riccati's recursions (both sequential and parallel) for solving dual-regularized LQR problems. We show how these methods can be used to solve general constrained, non-convex, discrete-time optimal control problems via a regularized interior point method, while guaranteeing that each step is a descent direction of an Augmented Barrier-Lagrangian merit function. We provide MIT-licensed implementations of our methods in C++ and JAX.
academic

双正則化リッカチ再帰による内点最適制御

基本情報

  • 論文ID: 2509.16370
  • タイトル: Dual-Regularized Riccati Recursions for Interior-Point Optimal Control
  • 著者: João Sousa-Pinto, Dominique Orban
  • 分類: math.OC cs.MS cs.RO cs.SY eess.SY
  • 発表日時: 2025年10月15日 (arXiv v2)
  • 論文リンク: https://arxiv.org/abs/2509.16370

要旨

本論文は、双正則化LQR問題を解くためのリッカチ再帰の閉形式拡張（逐次版および並列版を含む）を導出している。著者らは、正則化内点法を用いてこれらの手法を一般的な制約条件、非凸、離散時間最適制御問題の求解に適用する方法を示し、各ステップが拡張バリア・ラグランジュ関数の下降方向であることを保証している。論文はC++およびJAXのMITライセンス実装を提供している。

研究背景と動機

中核問題

本研究が解決しようとする中核問題は、等式および不等式制約を有する非凸離散時間最適制御問題を効率的に解く方法である。従来の手法は以下の課題を抱えている：

  1. 計算効率の問題：標準的な内点法は最適制御問題を処理する際に大規模線形システムの求解が必要であり、計算複雑度が高い
  2. 数値安定性：正則化パラメータがゼロに近づく際、従来の手法は数値不安定性を示す可能性がある
  3. 並列化の困難さ：既存の手法は並列計算資源の十分な活用が困難である

問題の重要性

最適制御問題はロボット工学、航空宇宙工学、自動運転など多くの分野で広く応用されている。このような問題を効率的に解くことは、特に複雑な制約を処理する必要があるシナリオにおいて、リアルタイム制御システムにとって重要である。

既存手法の限界

  1. DDP アルゴリズム：実務で最も一般的に使用されているが、単一射撃法として状態軌跡のホットスタートが独立して実行できない
  2. 標準LQR法：無制約または単純な制約を有する線形システムにのみ適用可能
  3. 既存の内点法：IPOPTなどの汎用ソルバーは最適制御問題の構造的特性を十分に活用できない

中核的貢献

  1. 理論的貢献：双正則化LQR問題を解くための閉形式リッカチ再帰拡張を導出し、逐次版および並列版を含む
  2. アルゴリズムの革新：拡張バリア・ラグランジュ関数をメリット関数として用いて下降方向を保証する正則化内点法を提案
  3. 数値安定性：正則化パラメータδ→0の際に数値安定なアルゴリズムを設計し、標準LQRアルゴリズムの復帰を可能にする
  4. 並列化アルゴリズム：関連スキャン(associative scans)に基づいてO(log N)並列時間複雑度の求解アルゴリズムを実装
  5. ソフトウェア貢献：C++およびJAXのオープンソース実装を提供し、効率的なスパース線形代数演算をサポート

方法の詳細

タスク定義

離散時間最適制御問題を考える：

min⁡x0,u0,…,xN∑i=0N−1fi(xi,ui)+fN(xN)\min_{x_0,u_0,\ldots,x_N} \sum_{i=0}^{N-1} f_i(x_i, u_i) + f_N(x_N)

制約条件：

  • 初期状態：x0=s0x_0 = s_0
  • 動力学制約：xi+1=di(xi,ui),∀i∈{0,…,N−1}x_{i+1} = d_i(x_i, u_i), \forall i \in \{0,\ldots,N-1\}
  • 等式制約：ci(xi,ui)=0,∀i∈{0,…,N−1}c_i(x_i, u_i) = 0, \forall i \in \{0,\ldots,N-1\}
  • 不等式制約：gi(xi,ui)≤0,∀i∈{0,…,N−1}g_i(x_i, u_i) \leq 0, \forall i \in \{0,\ldots,N-1\}
  • 終端制約：cN(xN)=0,gN(xN)≤0c_N(x_N) = 0, g_N(x_N) \leq 0

正則化内点法フレームワーク

拡張バリア・ラグランジュ関数

バリア・ラグランジュ関数を定義する： L(x,s,y,z;μ)=f(x)−μ∑ilog⁡(si)+yTc(x)+zT(g(x)+s)L(x,s,y,z;\mu) = f(x) - \mu\sum_i \log(s_i) + y^T c(x) + z^T(g(x) + s)

拡張版： A(x,s,y,z;μ,η)=L(x,s,y,z;μ)+η2(∥c(x)∥2+∥g(x)+s∥2)A(x,s,y,z;\mu,\eta) = L(x,s,y,z;\mu) + \frac{\eta}{2}(\|c(x)\|^2 + \|g(x)+s\|^2)

線形システムの求解

各反復では以下の線形システムを求解する必要がある： [P0CTGT0S−1Z0IC0−1ηI0GI0−1ηI][ΔxΔsΔyΔz]=−∇L(x,s,y,z;μ)\begin{bmatrix} P & 0 & C^T & G^T \\ 0 & S^{-1}Z & 0 & I \\ C & 0 & -\frac{1}{\eta}I & 0 \\ G & I & 0 & -\frac{1}{\eta}I \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta s \\ \Delta y \\ \Delta z \end{bmatrix} = -\nabla L(x,s,y,z;\mu)

双正則化LQR問題

変数消去により、内点法の線形システムを双正則化LQR問題に変換する： [PCTC−δI][xy]=−[sc]\begin{bmatrix} P & C^T \\ C & -\delta I \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = -\begin{bmatrix} s \\ c \end{bmatrix}

ここでδ>0\delta > 0は正則化パラメータであり、行列PPはブロック対角構造を有し、CCは動力学制約のヤコビアンを含む。

逐次アルゴリズム

後向再帰

主要な変数を定義する：

  • Vi=1δ(Fi−I)V_i = \frac{1}{\delta}(F_i - I)：値関数近似
  • vi=1δ(fi+ci)v_i = \frac{1}{\delta}(f_i + c_i)：オフセットベクトル

再帰公式：

G_i = B_i^T W_{i+1} B_i + R_i
H_i = B_i^T W_{i+1} A_i + M_i^T
h_i = r_i + B_i^T g_{i+1}
K_i = -G_i^{-1} H_i
k_i = -G_i^{-1} h_i
V_i = A_i^T W_{i+1} A_i + Q_i + H_i^T K_i
v_i = q_i + A_i^T g_{i+1} + H_i^T k_i
W_i = (I + \delta V_i)^{-1} V_i
g_i = v_i + W_i(c_i - \delta v_i)

前向再帰

制御則ui=Kixi+kiu_i = K_i x_i + k_iと状態遷移方程式を通じて最適軌跡を復帰させる。

並列アルゴリズム

関連スキャン並列化

関連スキャンを用いてO(log N)並列時間複雑度を実現する：

  1. 区間値関数：Vi→j(xi,xj)V_{i \to j}(x_i, x_j)をステージiからjへの値関数として定義
  2. 組合せ規則：区間値関数の組合せ演算を確立し、結合性を満たす
  3. 並列計算：逆向き関連スキャンを通じてすべてのVi→N+1V_{i \to N+1}を並列計算

アフィン関数の組合せ

前向き再帰をアフィン関数の組合せに変換する： xi+1=Mixi+mix_{i+1} = M_i x_i + m_i

関連スキャンを用いてすべてのアフィン変換を並列に組み合わせ、O(log N)の並列前向き伝播を実現する。

技術的革新点

  1. 数値安定性設計：再パラメータ化によりδ→0\delta \to 0の際の数値問題を回避
  2. 下降方向の保証：探索方向が拡張バリア・ラグランジュ関数の下降方向であることを理論的に証明
  3. 構造化求解：最適制御問題の時間構造を十分に活用し、大規模密行列線形システムの求解を回避
  4. 並列化設計：関数型プログラミングの関連スキャンに基づいた効率的な並列化

実験設定

実装の詳細

論文は2つの実装を提供している：

  1. C++実装：
    • SIP (Simple Interior Point)フレームワークに基づく
    • QDLDLスパースソルバーの統合をサポート
    • 実行時の動的メモリ割り当てを回避
    • カスタムKKTシステムソルバーをサポート
  2. JAX実装：
    • 自動微分をサポート
    • GPU/TPU加速
    • 完全なユニットテストを含む

検証方法

  • 必要な正定性を満たすランダムサンプルでアルゴリズムの正確性を検証
  • δ=0\delta = 0の際の標準LQRアルゴリズムとの一貫性を検証
  • 数値安定性テスト

実験結果

正確性の検証

論文は以下の方法でアルゴリズムの正確性を検証している：

  1. 理論的検証：δ=0\delta = 0の際、アルゴリズムは標準LQRアルゴリズムに退化する
  2. 数値的検証：ランダムに生成されたテストケースで解の正確性を検証
  3. ユニットテスト：JAX実装は完全なユニットテストスイートを含む

下降方向の保証

定理1.2はΔx≠0\Delta x \neq 0またはΔs≠0\Delta s \neq 0の際、方向微分が以下を満たすことを証明している： D(A(⋅,⋅,y,z;μ,η);(Δx,Δs))(x,s)<0D(A(\cdot,\cdot,y,z;\mu,\eta);(\Delta x,\Delta s))(x,s) < 0

これはアルゴリズムの大域収束性を保証する。

複雑度分析

  • 逐次アルゴリズム：O(N)時間複雑度
  • 並列アルゴリズム：O(log N)並列時間複雑度
  • 空間複雑度：O(N)、問題規模に線形

関連研究

主要な研究方向

  1. 古典的LQR法：Kalman (1960)が最初にリッカチ再帰を導出
  2. 内点法の応用：Rao等(1998)が最初に内点法をモデル予測制御に適用
  3. 並列LQR：Särkkä and García-Fernández (2021)が最初のO(log N)並列LQRアルゴリズムを提案
  4. 構造化ソルバー：FATROPなどの最近の研究が構造化制約処理を探索

本論文の相対的優位性

  1. 理論的完全性：完全な理論分析と収束性保証を提供
  2. 数値安定性：正則化パラメータがゼロに近づく際の数値問題を解決
  3. 実用性：完全なオープンソース実装を提供
  4. 汎用性：一般的な非凸制約最適制御問題を処理可能

結論と考察

主要な結論

  1. 双正則化LQR問題の閉形式リッカチ再帰拡張の導出に成功
  2. 正則化内点法との関連性を確立し、アルゴリズムの収束性を保証
  3. O(log N)並列時間複雑度の効率的なアルゴリズムを実装
  4. 数値安定で実用的なオープンソース実装を提供

限界

  1. 制約タイプの制限：手法は主にLQR形式に変換可能な問題に適用可能
  2. 正定性要件：アルゴリズムはヘッシアン行列の正定性仮定を要求
  3. 実際の性能：大規模実問題の性能比較が不足している

今後の方向

  1. より一般的な制約への拡張：経路制約とより複雑な終端制約を処理
  2. 適応的正則化：正則化パラメータを選択する適応的戦略の開発
  3. 実際の応用検証：ロボット制御などの実際の応用で手法の有効性を検証

深い評価

利点

  1. 理論的貢献が顕著：双正則化技術とリッカチ再帰を初めて組み合わせ、理論分析が完全
  2. アルゴリズム設計が優雅：最適制御問題の時間構造を巧妙に活用
  3. 数値的配慮が周到：特に数値安定性の問題に注目
  4. 実装品質が高い：2つの言語の高品質なオープンソース実装を提供
  5. 並列化の革新：関連スキャンに基づく並列化手法は理論的および実践的価値を有する

不足

  1. 実験検証が限定的：主に理論検証と単純な数値テストであり、大規模実問題の比較が不足
  2. 性能分析が不十分：詳細な計算時間とメモリ使用量の分析がない
  3. 適用範囲の議論が不十分：どの種類の最適制御問題がこの手法に最も適しているかについての深い議論が不足
  4. パラメータ選択の指針が不足：正則化パラメータの選択戦略についての議論が少ない

影響力

  1. 学術的価値：最適制御の数値手法に新しい理論的ツールを提供
  2. 実用的価値：オープンソース実装は手法の普及を促進
  3. 再現性：詳細なアルゴリズム記述とオープンソースコードが再現性を保証
  4. 示唆性：双正則化の考え方は他の最適化問題の求解に示唆を与える可能性がある

適用シーン

  1. リアルタイム制御システム：高速求解が必要なモデル予測制御応用
  2. 大規模最適化：長い時間域を有する最適制御問題
  3. 並列計算環境：マルチコアまたはGPUリソースを十分に活用できる応用シーン
  4. 制約最適化：複雑な等式および不等式制約を処理する必要がある制御問題

参考文献

論文は本分野の重要な文献を引用している：

  • Kalman (1960)：最適制御理論の基礎
  • Blelloch (1989)：関連スキャンの並列アルゴリズム理論
  • Särkkä & García-Fernández (2021)：並列LQRアルゴリズム
  • Wächter & Biegler (2006)：IPOPTの内点法ソルバー

総合評価：これは理論的貢献が顕著で、技術的革新が明らかな優秀な論文である。著者らは双正則化技術をリッカチ再帰に成功裏に導入し、数値安定性を維持しながら効率的な並列化を実現している。実際の応用検証の面ではまだ改善の余地があるが、その理論的価値とオープンソース貢献により、最適制御の数値手法分野における重要な進展となっている。