動的計画法とハミルトン・ヤコビ・ベルマン方程式

値関数 $V (t, ξ)$ について最適性原理から HJB 方程式 $V_{t} + min_{u} {ℓ (x, u) + V_{x} f (x, u)} = 0$ , $V (T, x) = ϕ (x)$ を立て、括弧内を $u$ について最小化して最適なフィードバック制御 $u^{*} (t, x)$ を $V_{x}$ で表せる

前提

偏微分と全微分（大学数学微分積分）
ベルマン最適方程式と最適価値（大学数学オペレーションズ・リサーチ）
平方完成と 2 次関数のグラフ（数学I 2次関数）

この技能までの道筋（52 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
偏微分と全微分（大学数学微分積分）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
条件付き確率と乗法定理（数学A 場合の数と確率）
マルコフ連鎖と推移確率（大学数学確率・統計）
無限等比級数と無限級数（数学III 極限）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
マルコフ決定過程と方策の価値（大学数学オペレーションズ・リサーチ）
ベルマン最適方程式と最適価値（大学数学オペレーションズ・リサーチ）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）

説明

状態 $x (s)$ が $x ˙ = f (x, u)$ に従って連続時間で動き、制御 $u (s)$ を選んで費用 $J = \int_{t}^{T} ℓ (x (s), u (s)) d s + ϕ (x (T))$ を最小にしたい、という最適制御問題を扱います。出発時刻 $t$ ・出発状態 $ξ$ から最適に進んだときの最小費用を値関数 $V (t, ξ)$ とよび、離散時間のベルマン方程式の連続時間版である HJB 方程式 $V_{t} + min_{u} {ℓ (x, u) + V_{x} f (x, u)} = 0, V (T, x) = ϕ (x)$ を立てます。括弧の中を $u$ について最小化すると、各時刻・各状態で取るべき制御（フィードバック制御） $u^{*} (t, x)$ が $V_{x}$ で表せます。

なぜそうしてよいのか

ベルマン方程式は「今 1 ステップでかかる費用」＋「その次の状態から先の最適費用」を最小化するという最適性原理でした。連続時間では 1 ステップを短い時間 $h$ と考えます。時刻 $t$ に状態 $ξ$ にいて、時間 $[t, t + h]$ の間ほぼ一定の制御 $u$ を使うと、その間の費用はおよそ $ℓ (ξ, u) h$ 、時刻 $t + h$ の状態はおよそ $ξ + f (ξ, u) h$ です。その後は最適に進むとすると、最適性原理から
$V (t, ξ) \approx u min {ℓ (ξ, u) h + V (t + h, ξ + f (ξ, u) h)}$
となります（割引のない、遷移が確定的なベルマン方程式で、報酬の最大化の代わりに費用の最小化をしています）。 $V$ が偏微分可能だとして全微分で 1 次まで展開すると $V (t + h, ξ + f h) \approx V (t, ξ) + V_{t} h + V_{x} f h$ なので、両辺から $V (t, ξ)$ を引いて $h$ で割り、 $h \to 0$ とすると
$V_{t} (t, ξ) + u min {ℓ (ξ, u) + V_{x} (t, ξ) f (ξ, u)} = 0$
が得られます。時刻 $T$ に出発すれば残りの費用は終端費用だけなので $V (T, x) = ϕ (x)$ です。値関数は終端から時間を逆向きにたどって決まる、という点も離散時間の後ろ向き帰納と同じです。

逆向きの確認もできます。滑らかな関数 $V$ が HJB 方程式と終端条件を満たすとき、任意の制御で動く軌道に沿って $\frac{d}{d s} V (s, x (s)) = V_{t} + V_{x} f (x, u) \geq - ℓ (x, u)$ （括弧内の最小値以上だから）なので、 $t$ から $T$ まで積分すると $ϕ (x (T)) - V (t, ξ) \geq - \int_{t}^{T} ℓ d s$ 、つまり $J \geq V (t, ξ)$ です。括弧内を最小にする $u^{*} (t, x)$ を使えば等号が成り立つので、 $V$ は確かに最小費用で、 $u^{*}$ が最適なフィードバック制御です。

実際の計算では、括弧の中 $ℓ (x, u) + V_{x} f (x, u)$ を「 $V_{x}$ を定数とみた $u$ の関数」として最小化します。たとえば $ℓ$ が $u$ の 2 次式で $f$ が $u$ の 1 次式なら、平方完成で最小点 $u^{*}$ が $V_{x}$ の式として求まり、それを代入すると $V$ だけの偏微分方程式になります。

手順

問題を $x ˙ = f (x, u)$ 、費用 $\int_{t}^{T} ℓ (x, u) d s + ϕ (x (T))$ の形に整理し、 $f, ℓ, ϕ$ を読み取る。
HJB 方程式 $V_{t} + min_{u} {ℓ (x, u) + V_{x} f (x, u)} = 0$ と終端条件 $V (T, x) = ϕ (x)$ を書く。
括弧内を $V_{x}$ を定数とみて $u$ について最小化する（2 次式なら平方完成）。最小点が最適フィードバック $u^{*} (t, x)$ （ $V_{x}$ で表される）になる。最小値が存在すること（2 次の係数が正など）を確認する。
最小値を HJB 方程式に代入して、 $V$ の偏微分方程式にする。
与えられた（または仮定した形の） $V$ について $V_{t}, V_{x}$ を計算し、方程式と終端条件を満たすことを確かめてから、 $V_{x}$ を $u^{*}$ の式に代入する。

例題

$T > 0$ を定数とする。状態方程式 $x ˙ = u$ （ $x, u$ は実数）のもとで、費用 $J = \int_{t}^{T} u (s)^{2} d s + x (T)^{2}$ を最小にする問題を考える。 $V (t, x) = \frac{x ^{2}}{1 + T - t}$ （ $t \leq T$ ）が HJB 方程式と終端条件を満たすことを確かめ、最適なフィードバック制御 $u^{*} (t, x)$ を求めよ。

例題の解答

【手順 1】 $f (x, u) = u, ℓ (x, u) = u^{2}, ϕ (x) = x^{2}$ 。

【手順 2】HJB 方程式は $V_{t} + min_{u} {u^{2} + V_{x} u} = 0$ 、終端条件は $V (T, x) = x^{2}$ 。

【手順 3】 $u^{2} + V_{x} u = (u + \frac{V _{x}}{2})^{2} - \frac{V _{x}^{2}}{4}$ と平方完成すると、2 次の係数が正なので最小点は $u^{*} = - \frac{V _{x}}{2}$ 、最小値は $- \frac{V _{x}^{2}}{4}$ 。

【手順 4】HJB 方程式は $V_{t} - \frac{V _{x}^{2}}{4} = 0$ となる。

【手順 5】 $V = \frac{x ^{2}}{1 + T - t}$ より $V_{t} = \frac{x ^{2}}{( 1 + T - t ) ^{2}}$ 、 $V_{x} = \frac{2 x}{1 + T - t}$ 。すると $V_{t} - \frac{V _{x}^{2}}{4} = \frac{x ^{2}}{( 1 + T - t ) ^{2}} - \frac{x ^{2}}{( 1 + T - t ) ^{2}} = 0$ で方程式を満たし、 $V (T, x) = \frac{x ^{2}}{1} = x^{2}$ で終端条件も満たす（ $t \leq T$ では $1 + T - t \geq 1 > 0$ なので分母は 0 にならない）。よって
$u^{*} (t, x) = - \frac{V _{x}}{2} = - \frac{x}{1 + T - t} .$
（終端時刻が近づくほど、状態を 0 に引き戻す力が強くなる。）

答え: $- \frac{x}{1 + T - t}$

よくある誤り

最小化を済ませずに、 $u$ を含んだまま $V_{t} + ℓ (x, u) + V_{x} f (x, u) = 0$ を方程式としてしまう誤り。正しくは括弧内を $u$ について最小化した値を入れる。例題なら $V_{t} + u^{2} + V_{x} u = 0$ ではなく $V_{t} - \frac{V _{x}^{2}}{4} = 0$ である。
平方完成の係数を落とす誤り。 $u^{2} + V_{x} u$ の最小点を $u^{*} = - V_{x}$ としてしまう。正しくは $\frac{d}{d u} (u^{2} + V_{x} u) = 2 u + V_{x} = 0$ より $u^{*} = - \frac{V _{x}}{2}$ 。費用が $r u^{2}$ （ $r > 0$ ）なら $u^{*} = - \frac{V _{x}}{2 r}$ になる。
終端条件を初期時刻に置いてしまう誤り。 $V (0, x) = ϕ (x)$ としてしまう。正しくは値関数は「残りの最小費用」なので $V (T, x) = ϕ (x)$ であり、時間を逆向きに解く。
最大化と最小化、または符号を取り違える誤り。強化学習のベルマン方程式にならって $V_{t} + max_{u} {ℓ + V_{x} f} = 0$ としてしまう。 $ℓ$ が費用なら正しくは $min$ であり、 $ℓ = u^{2}$ を $max$ にすると括弧内は上に有界でなく、最適制御が存在しない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
実数値の状態 $x (t)$ と制御 $u (t)$ （ $u$ は $[0, 1]$ 上の区分的に連続な実数値関数で、値に制限はない）について、状態方程式
$x ˙ (t) = u (t) (0 \leq t \leq 1), x (0) = 3$
のもとで、評価関数
$J [u] = \int_{0}^{1} u (t)^{2} d t + 2 x (1)^{2}$
を最小にしたい。時刻 $t$ に状態 $ξ$ から出発したときの $\int_{t}^{1} u (s)^{2} d s + 2 x (1)^{2}$ の最小値を値関数 $V (t, ξ)$ とし、 $V (t, ξ) = p (t) ξ^{2}$ の形であることを用いてよい。 $J [u]$ の最小値を求めよ。

この技能を使う問題

この技能の次に学べること

線形 2 次（LQ）制御とリカッチ方程式（大学院数学変分法・最適制御）