Global Convergence of a Line-Search Filter Differential Dynamic Programming Method

技術要約：ラインサーチ・フィルタを用いた微分動的計画法の世界的収束性

問題提起
本論文は、状態および制御に関する非線形等式制約、ならびにシステムダイナミクスに従う離散時間有限ホライゾン最適制御問題（OCP）を解く際の課題に対処している。微分動的計画法（DDP）は、メインとジェイコブソンによって提案された、既知の局所的な二次収束性を有する「制約なし」のOCPのための確立された手法であるが、その制約付きへの適用においては、多くの既存の拡張において厳密な世界的収束性の保証が欠如している。逐次二次計画法や原始・双対定式化に基づく従来の制約付きDDPのバリアントは、多くの場合、局所的な収束結果は提供するものの、世界的解析を省略している。本研究が対象とする特定のギャップは、Xuらによって提案された、一般的な非線形計画法（NLP）のフィルタ手法（WächterおよびBieglerによるもの）をDDPフレームワークに適応させたラインサーチ・フィルタ法であるFilterDDPに対する、厳密な世界的収束性の証明の欠如である。

手法
著者らは、ラインサーチ・フィルタ手順をDDP構造に統合したFilterDDPアルゴリズムの形式的な解析を提案している。核心となる手法は、一般的なNLPフィルタ法で通常用いられる減衰ニュートンステップを、以下の2つのフェーズからなるDDP特有の試行点生成プロセスに置き換えることである。

1. 後退再帰（Backward Recursion）： 値関数の近似およびラグランジュ乗数の再帰的な更新。このフェーズでは、摂動を加えたヘッセ行列を計算し、線形システムを解くことで、制御、乗数、および状態に対する更新方向（$\zeta, \beta, \psi, \omega$）を決定する。
2. 前方シミュレーション（Forward Simulation）： 計算された更新量とステップサイズ$\alpha$に基づき、新しい軌道を生成するシミュレーションフェーズ。極めて重要な点は、このフェーズが、DDPに固有の特性として、各反復において動的制約（$x_{t+1} = f(x_t, u_t)$）が満たされることを保証することである。

アルゴリズムは、ラグランジュ関数の減少（目的関数としての尺度）と制約違反の尺度とのバランスを取るために、試行点を受け入れるフィルタメカニズムを利用する。ステップ受け入れ基準には、ラグランジュ関数または制約違反のいずれかの十分な減少条件、 「L型」反復のためのArmijo型条件、およびステップサイズが小さすぎる場合や制約ヤコビ行列のランクが不足した場合に呼び出される実行可能回復フェーズが含まれる。

主要な貢献
本研究の主要な貢献は、FilterDDPアルゴリズムの世界的収束性の確立である。著者らは、DDPの特定の後退・前方プロセスが、WächterおよびBieglerによって確立された一般的なNLPにおけるラインサーチ・フィルタ法の世界的収束に必要な解析的性質と同じ性質を満たすことを示すことで、これを達成している。

この貢献における主要な技術的ステップは以下の通りである：

• ステップの等価性： DDPの後退再帰と前方シミュレーションが、世界的収束解析の観点から見たとき、OCPのKKT条件に適用された減衰ニュートンステップと同一に振る舞うことを証明すること。
• 補題の導出： 更新ルールをバウンドし、非最適実行可能点に対する降下特性を確立し、更新ルールが局所的にフィルタ基準（ラグランジュ関数および制約違反）を線形化することを示す一連の補題（WächterおよびBieglerの研究における補題1〜3に相当）を確立すること。
• 内点法への拡張： バリア内点法を介して、不等式制約（具体的には $u_t \geq 0$）を扱うために世界的収束解析を拡張すること。これには、ヘッセ行列近似の適応、および反復が不等式制約の境界から離れた状態に留まり、バリア目的関数とその導関数が定義され続けることを証明することが含まれる。

結果
等式制約に関する一連の標準的な正則性と滑らかさの仮定（等式制約については仮定G、バリア拡張については仮定Bと表記）の下で、論文は以下の収束特性を証明している。

1. 実行可能性： 反復列の極限点は実行可能である。具体的には、反復回数 $k \to \infty$ のとき、制約違反尺度 $\theta(w_k)$ はゼロに収束する。
2. 最適性： 反復列が有界であれば、制約付きOCPの一次最適条件（KKT条件）を満たす極限点が少なくとも一つ存在する。これは、射影勾配成分のノルムによって定義される臨界度尺度 $\chi(w_k)$ の下限がゼロであることを示すことにより実証される。
3. バリア収束： 内点法拡張において、反復が不等式制約の境界から一様に離れて留まることが証明されており、これにより最適化プロセス全体を通じてバリア定式化の妥当性が保証される。

意義と主張
本論文は、FilterDDPの実用的な成功と厳密な理論的保証の間の溝を正式に埋めることで、その意義を主張している。著者らは、FilterDDPの局所的な二次収束性は（ステップ受け入れ基準を無視すれば）以前から確立されていたが、世界的収束解析が欠けていたと述べている。WächterおよびBieglerの解析を適応させることで、本論文は、DDP構造がフィルタ法の世界的収束特性を妨げるものではなく、むしろ後退・前方再帰が一般的なNLPの文脈におけるニュートンステップと同じ役割を効果的に果たすことを示している。

著者らは、この解析が、実行可能回復フェーズが正常に終了すること、およびアルゴリズムが非KKT点において早期に停止しないという仮定に依存していることを控えめに述べている。さらに、本論文は、FilterDDPの高速な局所収束（ステップ受け入れ基準を無視しない場合）を確立することは依然として未解決の問題であることを指摘しており、将来の研究のために、一般的なNLPで使用されるものと同様の二次補正ステップが必要である可能性を示唆している。本論文は、新しい応用や実験的ベンチマークを提案するものではなく、アルゴリズムの理論的な収束特性に厳密に焦点を当てている。