両的計画

【りょうてきけいかく (bynamic programming)】

概要

いわゆる動的計画法を2元連立的に考えた逐次最適化法. 単調性「非減少性」に代わって両調性「非減少性または非増加性のいずれか」の下では, 部分最大化問題群と部分最小化問題群の両群を考えて, 両群の相隣る問題間の関係を両帰式としてを導く. これを逐次解いて, 最後に与問題の最適解を求める方法である.負値乗法型, 負値乗加法型などの評価系が両的計画で解ける. 確率系ではマルコフ両決定過程ともいう.

詳説

　動的計画法は単調性 monotonicity と再帰性 recursiveness (可分性 separability) の下で適用される. この単調性は目的関数の「非減少性」を意味しているが, これを両調性 bitonicity「非減少性または非増加性のいずれか」まで拡大解釈すると, より広い逐次決定過程が考えられる. これを両的計画と呼ぶ. 特に, 確率システム上ではマルコフ両決定過程[3]という. これは確率的動的計画法を単にマルコフ決定過程ということに準じている.

　両的計画法によって最大化問題を解く場合, 与問題に対する部分最大化問題群ばかりでなく部分最小化問題群をも考える必要がある. このとき, 最大値関数と最小値関数の間に成り立つ連立再帰式を両帰式という. 負値乗法型評価系[1], 負値乗加法型評価系 [2] の最適化問題や最短最長ルート問題などは両帰式で解ける.

　さて, 逐次決定過程が次の要素で与えられるとしよう：

　 　

$S\,$ は状態空間, $s_{n}\in S\,$ は第$n\,$状態, $A\,$は決定空間

$A(s_{n})\,$は$s_{n}\,$での可能決定空間, $a_{n}\in A(s_{n})\,$は第$n\,$決定

$r:S\times A\to \mathbf {R} ^{1}$は利得関数, $\beta :S\times A\to (-1,\,1)\,$は割引き関数

$k:S\to \mathbf {R} ^{1}\,$は終端関数, $T:S\times A\to S\,$は状態変換

$p=\{p(t|s,a)\}\,$はマルコフ推移法則, $\sum _{t\in S}p(t|s,a)=1,p(t|s,a)\geq 0\,$

このとき, 確定系上の負値乗加法評価系の最大化または最小化は

${\begin{array}{lll}{\rm {max.~and~min.}}&r_{1}+\beta _{1}r_{2}+\beta _{1}\beta _{2}r_{3}+\cdots \\&+\beta _{1}\beta _{2}\cdots \beta _{N-1}r_{N}+\beta _{1}\beta _{2}\cdots \beta _{N}k\\{\mbox{s. t.}}\;T(s_{n},a_{n})=&s_{n+1},~a_{n}\in A(s_{n})\quad (n=1,2,\ldots ,N),\end{array}}\,$

で表わされる. ただし $r_{n}=r(s_{n},a_{n}),~~\beta _{n}=\beta (s_{n},a_{n})\,$. このとき, 第$n\,$段の状態 $s_{n}\,$ から始まる部分問題

${\begin{array}{lll}{\rm {max.~and~min.}}&r_{n}+\beta _{n}r_{n+1}+\beta _{n}\beta _{n+1}r_{n+2}+\cdots \\&+\beta _{n}\beta _{n+1}\cdots \beta _{N-1}r_{N}+\beta _{n}\beta _{n+1}\cdots \beta _{N}k\\{\mbox{s. t.}}\;T(s_{m},a_{m})=&s_{m+1},~a_{m}\in A(s_{m})\quad (m=n,n+1,\ldots ,N),\end{array}}\,$

の最大値を $U_{n}(s_{n})\,$, 最小値を $u_{n}(s_{n})\,$ とすると, 両最適値関数は両帰式

$U_{n}(s)=\max _{a:-}T(s,a;u_{n+1})\vee \max _{a:+}T(s,a;U_{n+1})\,$

$u_{n}(s)=\min _{a:-}T(s,a;U_{n+1})\wedge \min _{a:+}T(s,a;u_{n+1})\quad \quad {\mbox{(1)}}\,$

$U_{N+1}(s)=u_{N+1}(s)=k(s)\,$

を満たす. ここに~ $T(s,a;w):=r(s,a)+\beta (s,a)w(T(s,a)),~a:-(+)\,$は $\beta (s,a)<(\geq )\,0\,$ なる $a\,$ である.

　また, マルコフ推移法則 $p=\{p(t|s,a)\}\,$ 上での期待値最適化問題

${\begin{array}{ll}{\rm {max.~and~min.}}&E[\,r_{1}+\beta _{1}r_{2}+\beta _{1}\beta _{2}r_{3}+\cdots \\&+\beta _{1}\beta _{2}\cdots \beta _{N-1}r_{N}+\beta _{1}\beta _{2}\cdots \beta _{N}k\,]\end{array}}\,$

${\mbox{s. t.}}\;\;p(\cdot |s_{n},a_{n})~\sim s_{n+1},~a_{n}\in A(s_{n})\;(n=1,2,\ldots ),\,$

の両帰式は一次変換

$T(s,a;w):=r(s,a)+\beta (s,a){\displaystyle \sum _{t\in S}w(t)p(t|s,a)}\,$

を用いて(1)と同じ型で与えられる[4].

---

参考文献

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

[2] S. Iwamoto, "From Dynamic Programming to Bynamic programming," Journal of Mathematical Analysis and Applications, 177 (1993), 56-74.

[3] S. Iwamoto, "On Bidecision Processes," Journal of Mathematical Analysis and Applications, 187 (1994), 676-699.

[4] T. Fujita and K. Tsurusaki, "Stochastic Optimization of Multiplicative Functions with Negative Value," Journal of the Operations Research Society of Japan, 41 (1998), 351-373.