微分動的計画法

微分動的計画法 (DDP)（びぶんどうてきけいかくほう、）は軌道最適化のために用いられる最適制御アルゴリズムの一つである。 本アルゴリズムは1966年に Mayne によって紹介され、
その後JacobsonとMayneによるその名の由来となった著作の中で分析された。
このアルゴリズムはシステムのダイナミクスとコスト関数を局所的な二次形式によってモデル化し、2次収束を示す。 また、Pantojaのstep-wise Newton法とも密接に関連している。
有限horizon離散時間問題.
次式のダイナミクスを考える。
これは制御入力 formula_1 のもとでの状態 formula_2 の時刻 formula_3 から formula_4までの時間発展を表している。
 "総コスト" formula_5 は、ランニングコスト formula_6 と最終コスト formula_7　の和として与えられ、状態 formula_8 と終端時刻までに適用する制御系列 formula_9 によって定まる:
ここで formula_11であり、時刻 formula_12 における状態　formula_13は式によって与えられる。この最適制御問題の解は、上式を最小化する制御系列
formula_14
である。
これに対し、ありえる初期状態すべてを考えるのではなく、特定の初期状態 formula_15 に対して最適な入力系列 formula_16 を求めるのが "軌道最適化"である。
動的計画法.
今、 formula_17 を制御入力の部分系列 formula_18　とし、
"残余コスト(cost-to-go)" formula_19　を formula_3 から formula_21までの部分和として定義する:
最適な残余コスト、または時刻 formula_3 での"価値関数" は、以下のような制御系列による最小化で与えられる :
 formula_25を出発点として、 時間を遡る方向に制御入力を一ステップ毎に最小化することにより、動的計画法の原理は全体の最小化に必要な計算量を削減する。
これがベルマン方程式である。
微分動的計画法 (DDP).
微分動的計画法 (DDP) では、新しい制御系列を計算するために、ノミナルな軌道に沿って逆方向パスの計算を行い、次に（得られた制御系列のもとでの）新しい軌道とその評価値を得るために順方向パスの計算を行うことを繰り返す。逆方向パスの計算から始めよう。
式の formula_26 演算子の引数
に関して、その値の変分を時刻formula_3の状態-入力ペア formula_29 周辺でとったものをformula_30としよう:
これを、二次形式に展開する。
 & Q_{\mathbf{x}\mathbf{u}}\\
1\\
\delta\mathbf{x}\\
ここで用いる formula_30の表記は、森本淳 (ATR脳情報研究所) の記法の変形版であり、添え字は偏微分の分母を示している。
見やすくするため、添え字のformula_3を省略し、次の時間ステップの変数は formula_34のようにプライムをつけて示そう。テイラー展開により係数は以下となる。
最後の三つの方程式に現れる最終項はベクトルとテンソルの縮約(contraction)を表す。 二次形式で近似された式 を入力formula_36に関して最小化することで次式を得る。
^* = \operatorname{argmin}\limits_{\delta \mathbf{u}}Q(\delta \mathbf{x},\delta
\mathbf{u})=-Q_{\mathbf{u}\mathbf{u}}^{-1}(Q_\mathbf{u}+Q_{\mathbf{u}\mathbf{x}}\delta \mathbf{x}),
これにより、オープンループ項 formula_37 とフィードバック項formula_38が与えられる。この結果を式 に代入することにより 時間formula_3 における価値関数が得られる。
formula_41 からformula_42に向かって、再帰的に価値関数 formula_43 の局所的な二次形式のモデルと、制御の修正量 formula_44を求めるのが逆方向パスの計算である。
先に述べたように、価値関数の初期値は formula_25である。逆方向パスの完了後、新しい軌道にそって順方向パスの計算を行う。 
以上の逆方向パスと順方向パスの計算を収束するまで繰り返す。
正則化と直線探索.
微分動的計画法は、ニュートン法と同様に、二次収束を示すアルゴリズムである。 そのため、最小値に向けて大きな修正ステップが発生するため、収束を保証するために、正則化 および/または直線探索が必要となる。
DDPの文脈における正則化とは、式の行列 formula_47 の正定性を保証することである。 DDPにおける直線検索は、オープンループ制御修正量 formula_48 をスカラー formula_49でスケーリングすることに対応する。