動的計画

【どうてきけいかく (dynamic programming)】

概要

1957年, ベルマン (R.E. Bellman) によって提案された多変数最適化問題を解くための手法. 目的関数に再帰性(可分性)と単調性があり, 制約式が逐次的であるとき, 原問題をある部分問題群に埋め込んで, 各部分問題の最適値を定義し, 相隣る問題の最適値間の関係式(再帰式)を導く. これを逐次解いて, 最後に与問題の最適解を求める方法である. 解法の効率化のためには, 決定変数, 状態変数, 評価関数などの選択・設定に個々の創意工夫を要する.

詳説

　多変数最適化問題の目的関数が再帰性(可分性)と単調性をもち, 制約条件に逐次性があるとき, 再帰式 を導いて, これを１変数ずつ解いて最後に与問題の最適解を求めようとする方法を, 動的計画(dynamic programming)と呼ぶ. 原理としては ${\mbox{(i)}}\,$ 最適性の原理 (principle of optimality), ${\mbox{(ii)}}\,$ 不変埋没原理(principle of invariant imbedding), ${\mbox{(iii)}}\,$ 因果律の原理(principle of causality), の三つに基づく[1]. 最適性の原理には ${\mbox{(1)}}\,$ オリジナル版, ${\mbox{(2)}}\,$ シンプル版, ${\mbox{ (3)}}\,$ "${\mbox{Life}}\,$"版, ${\mbox{(4)}}\,$ 構造解析版, ${\mbox{(5)}}\,$ 数学版, などがある[9]. 数学的にはマックスマックス定理 に遡ることができる[2][4]. 応用面では, 逐次決定過程 [3][6]の基本原理として用いられ, マルコフ決定過程の政策改良法, 最短経路問題のダイクストラ法, 巡回セールスマン問題など種々の最適化問題の解法としてアルゴリズムに組み込まれている.

　一般に, 再帰型関数 $h:[0,\infty )^{N}\to \mathbf {R} ^{1}\,$ は

$h(x_{1},x_{2},\ldots ,x_{N})=h_{1}(x_{1};h_{2}(x_{2};\ldots ,h_{N-1}(x_{N-1};h_{N}(x_{N}))\ldots ))\,$

で表わされる. このとき, 部分関数 $h_{n}:[0,\infty )^{N-n+1}\to \mathbf {R} ^{1}\,$ を

$h_{n}(x_{n},\ldots ,x_{N}):=h_{n}(x_{n};\ldots ,h_{N-1}(x_{N-1};h_{N}(x_{N}))\ldots )\,$

で定義する. 構成要素の１変数関数 $h_{n}(x;\cdot ),h_{N}(\cdot )\,$ がすべて単調な(狭義単調な)とき, 特に単調性(狭義単調性)をもつ再帰型関数という. 単調性をもつ再帰型関数 $f,\,g$ を目的式と制約式にする主問題

${\mbox{P}}(c)\quad {\begin{array}{lll}{\mbox{max.}}&f(x_{1},x_{2},\ldots ,x_{N})\\{\mbox{s. t.}}&g(x_{1},x_{2},\ldots ,x_{N})\leq c,&x_{1},x_{2},\ldots ,x_{N}\geq 0,\end{array}}\,$

の解(最大値関数と最大点関数)は次のように求められる：

主問題 ${\mbox{P}}(c)\,$ を部分問題群 ${\mathbf {P} }=\{{\mbox{P}}_{n}(c)\}:\,$

${\mbox{P}}_{n}(c)\quad {\begin{array}{lll}{\mbox{max.}}&f_{n}(x_{n},\ldots ,x_{N})\\{\mbox{s. t.}}&g_{n}(x_{n},\ldots ,x_{N})\leq c,&x_{n},\ldots ,x_{N}\geq 0,\end{array}}\,$

に埋め込み, この最大値を $u_{n}(c)\,$ とする. このとき, 制約式の狭義単調性と両式の連続性を仮定すると, 再帰式

$u_{n}(c)=\max _{x\geq 0}\,f_{n}(\,x\,;u_{n+1}(g_{nx}^{-1}(c)))\quad 1\leq n\leq N-1\,$

$u_{N}(c)=f_{N}(g_{N}^{-1}(c))\,$

が成り立つ. ただし, $g_{nx}^{-1}(\cdot )\,$ は $g_{n}(x;\cdot )\,$ の逆関数. この再帰式を後向きに解いて, 最後に主問題の最大値 $u_{1}(c)\,$ が得られる. これが動的計画法である. さらに, 主問題 ${\mbox{P}}(c)\,$ と逆問題

${\mbox{I}}(c)\quad {\begin{array}{lll}{\mbox{min.}}&g(x_{1},x_{2},\ldots ,x_{N})\\{\mbox{s. t.}}&f(x_{1},x_{2},\ldots ,x_{N})\geq c,&x_{1},x_{2},\ldots ,x_{N}\geq 0,\end{array}}\,$

の解(最小値関数と最小点関数)の間には互いに逆関数の関係にある(逆定理 [5]). これは線形計画における双対定理に類似して, 動的計画の双対定理と考えられる[11].

　また, 狭義単調性をもつ再帰型関数 $h\,$ が終端値 $k\,$ をもつときは

$h(x_{1},\ldots ,x_{N},k)=h_{1}(x_{1};\ldots ,h_{N-1}(x_{N-1};h_{N}(x_{N};k))\ldots )\,$

で表わされる. これに対して反転関数(逐次パラメトリック逆関数) $h^{-1}:\mathbf {R} ^{N+1}\to \mathbf {R} ^{1}\,$ を

$h^{-1}(x_{N},\ldots ,x_{2},x_{1},c):\;=\;h_{N}^{-1}(x_{N};\ldots ,h_{2}^{-1}(x_{2};h_{1}^{-1}(x_{1};c))\ldots )\,$

で定義する. このとき, 目的式 $f\,$, 制約式 $g\,$ (ただし $g_{N}(x_{N};l):=g_{N}(x_{N})+l)\,$をもつ主問題の反転問題を

${\mbox{R}}(c)\quad {\begin{array}{lll}{\mbox{min.}}&f^{-1}(x_{N},\ldots ,x_{1},u_{1}^{-1}(c))\\{\mbox{s. t.}}&g^{-1}(x_{N},\ldots ,x_{1},c)=0,&x_{N},\ldots ,x_{1}\geq 0,\end{array}}\,$

で考えると, 反転問題の最小値は主問題の終端値となる (反転定理 [7]).

　さらに, 準線形化, 最大変換(共役変換)による双対理論を組み込んだ三面鏡理論 [8]が制御過程上で展開されている. 逆問題, 反転問題, 双対問題は基本的に動的計画法で解くことができるが, それぞれの問題の最適解は直接解くことなく, 対応する定理によって得られる[7].

　再帰性, 単調性がない場合の最適化としては, 非可分性との関連で結合性などの下で事前条件付き決定過程, 事後条件付き決定過程[10]がファジィ動的計画, 非加法型再帰的効用関数の経済学などで研究されている. これらの問題はマルコフ政策のクラスで再帰式が導かれる.

---

参考文献

[1] R. Bellman, Dynamic Programming, Princeton Univ. Press, 1957.

[2] G. H. Hardy, J. E. littlewood and G. Pólya, Inequalities, 2nd ed., Cambridge Univ. Press, 1952.

[3] 茨木俊秀,『組合せ最適化の理論』, 電子通信学会, 1979.

[4] 伊理正夫ほか, 座談会「最大問題最小問題をめぐって」,『数学セミナー』, 7月号 (1966), 40-48.

[5] S. Iwamoto, "Inverse Theorems in Dynamic Programming I, II, III," Journal of Mathematical Analysis and Applications, 58 (1977), 113-134, 249-279, 439-448.

[6] 岩本誠一,「逐次決定過程としての動的計画論I,II」,『オペレーションズ・リサーチ』, 22 (1977), 427-434, 496-501.

[7] 岩本誠一,『動的計画論』, 九州大学出版会(経済工学シリーズ), 1987.

[8] S. Iwamoto, "A three mirror problem on dynamic programming," in Proceedings of the Third Bellman Continuum Workshop, 363-382, 1989.

[9] 岩本誠一,「動的計画の最近の進歩」, 第２回ＲＡＭＰシンポジウム論文集, 129-140, 1990.

[10] S. Iwamoto, "Conditional decision processes with recursive reward function,"Journal of Mathematical Analysis and Applications, 230 (1999), 193-210.

[11] 近藤次郎,『最適化法』, コロナ社, 1984.