不変埋没原理

【ふへんまいぼつげんり (principle of invariant imbedding)】

概要

動的計画法の基本原理の1つ. ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考える. これを「埋め込み」という. ただし, それぞれの問題の「構造」は不変である. このとき, 問題の大きさは小さいものから大きいものまであり, 「1番大きい」問題が与問題である. 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. 埋め込み方に工夫を要する.

詳説

　ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考えることを「埋め込み」(imbedding)という. すなわち, 与問題をある問題群の１つと見做すことである. このとき, 問題の大きさは小さい(易しい)ものから大きい(難しい)ものまであり, 一番大きい(解きたい)問題が与問題である. しかし, 問題の「構造」は不変である. さらに, 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. このような方法で解に至るまでを, 不変埋没原理 (principle of invariant imbedding)による方法という [1] [4] [5].

　たとえば,「1から10までの自然数の和を求める」問題を考えてみよう. 以下ではいつも「1から」(前向きの方法で)考えることにして, この問題を ${\rm {P}}(10)\,$ で表わし, 「解」(この場合, 和)を $S(10)\,$ としよう. このとき, 「1から $n\,$ までの自然数の和を求める」部分問題 ${\rm {P}}(n)\,$ からなる群 $\{{\rm {P}}(n);n=1,2,\ldots ,10\}\,$ を考える. このこと自体が埋め込みである. 部分問題 ${\rm {P}}(n)\,$ の解($=\,$和)を $S(n)\,$ とする. 最後の(一番大きい)問題 ${\rm {P}}(10)\,$ の解 $S(10)\,$ が求める解である. このとき, 最初の (一番易しい) 問題の解は $S(1)=1\,$ であり, 相隣る問題の解 $S(n)\,$ と $S(n+1)\,$ の間に漸化式

$S(n+1)=S(n)+n+1\quad n=1,2,\ldots ,9;\quad S(1)=1\,$

が成り立つ. 漸化式を $S(1),S(2),\ldots \,$ の順に前向きに逐次解くことによって, $S(10)=55\,$ を得る. 他方, 「$n\,$ から(いつも！)10までの自然数の和を求める」部分問題 ${\rm {Q}}(n)\,$ の族を考えても, 上述と同様に解くことができる. これを後向きの埋め込みという.

　一般の問題では, どのような大きさの問題群に埋め込むか, 関係式が導けるか, 解けるか, 解き易いかなど, 埋め込み方に工夫を要する. たとえば, 多段階の最適化問題

${\mbox{max.}}~~\psi (g_{1}(x_{1},x_{2})\circ g_{2}(x_{2},x_{3})\circ \cdots \circ g_{N}(x_{N},x_{N+1})\circ k(x_{N+1}))\,$

${\mbox{s. t.}}~~~x_{n+1}\in A_{n}(x_{n})\quad (1\leq n\leq N),\,$

の最大値 $u_{1}(x_{1})\,$ と最大点 $x^{*}=(x_{1},x_{2}^{*},\ldots ,x_{N+1}^{*})\,$ を求めるには, 新たなパラメータ $\lambda _{n}(\in \Lambda _{n}(x_{n}))\,$ を含む部分問題群 ${\mathcal {P}}=\{{\rm {P}}_{n}(x_{n};\lambda _{n})\}\,$ :

${\rm {max.}}~~\psi (\lambda _{n}\circ g_{n}(x_{n},x_{n+1})\circ \cdots \circ g_{N}(x_{N},x_{N+1})\circ k(x_{N+1}))\,$

${\begin{array}{l}{\mbox{s. t.}}~~~x_{m+1}\in A_{m}(x_{m})\quad (n\leq m\leq N),\\~~~~x_{n}\in X_{n},\;\lambda _{n}\in \Lambda _{n}(x_{n}),~(1\leq n\leq N+1),\end{array}}\,$

に埋め込むと, パラメータ空間列 $\{\Lambda _{n}(\cdot )\}\,$ は前向きの再帰式

$\Lambda _{1}(x)=\{{\tilde {\lambda }}\},~~x\in X_{1}\,$ $({\tilde {\lambda }}\,$は結合演算$\circ \,$の左単位元$)\,$

${\begin{array}{lr}\Lambda _{n+1}(y)=&\{\,\lambda \circ g_{n}(x,\,y)\,|\,\lambda \in \Lambda _{n}(x),~y\in A_{n}(x)\,\}\\&y\in X_{n+1},~~n=1,2,\ldots ,N\end{array}}\,$

で生成され, 最適値関数 $u_{n}=u_{n}(x_{n};\lambda _{n})\,$は次の後向き再帰式を満たす：

$u_{n}(x;\lambda )=\max _{y\in A_{n}(x)}u_{n+1}(\,y\,;\lambda \circ g_{n}(x,\,y))\,$

$~~~~x\in X_{n},~~\lambda \in \Lambda _{n}(x),~~n=1,2,\ldots ,N\,$

$u_{N+1}(x;\lambda )=\psi (\lambda \circ k(x))~~x\in X_{N+1},~~\lambda \in \Lambda _{N+1}(x).\,$

これを後ろから逐次解き, 最後の $u_{1}(x_{1};\lambda _{1})\,$ に $\lambda _{1}={\tilde {\lambda }}\,$ を代入すると求める最大値が得られる： $u_{1}(x_{1})=u_{1}(x_{1};{\tilde {\lambda }}).\,$

　また, 非最適化問題としては, 木の総容量など, 多重和 (多重和の解法)

${\mbox{S}}_{1}(x_{1}):~~{\sum \sum \cdots \sum }_{(x_{2},x_{3},\cdots ,x_{N+1})\in P_{1}(x_{1})}\psi (g_{1}(x_{1},x_{2})\circ \cdots \circ g_{N}(x_{N},x_{N+1})\circ k(x_{N+1}))\,$

$(P_{1}(x_{1}):=\{(x_{2},\cdots ,x_{N+1})\,|\,x_{n+1}\in A_{n}(x_{n})~~1\leq n\leq N\})\,$

を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.

　このようなパラメータを導入した埋め込みは非可分性に起因し, 単一評価系, 複合評価系の最適化, 期待値最適化, 多重和, 多重積分 (多重積分の解法) などで考えられる [2] [3]. 不変埋没原理は変数の離散と連続, システムの確定や確率やファジィ, 問題の最適と非最適を問わず, 歴史的には数学(微分方程式, 偏微分方程式の応用), 物理数学などで, また近年はコンピュータサイエンスで幅広く用いられている.

---

参考文献

[1] R. E. Bellman and E. D. Denman, Invariant Imbedding, Lect. Notes in Operation Research and Mathematical Systems, Vol. 52, Springer-Verlag, Berlin, 1971.

[2] S. Iwamoto and T. Fujita, "Stochastic Decision-making in a Fuzzy Environment," Journal of the Operations Research Society of Japan, 38 (1995), 467-482.

[3] 岩本誠一,「不変埋没によるファジィ動的計画法」, 日本オペレーションズ・リサーチ学会第33回シンポジウム, 25-33, 1995.

[4] E. S. Lee, Quasilinearization and Invariant Imbedding, Academic Press, 1968.

[5] 相良節夫, 杉坂政典,「Invariant Imbedding について」,『システムと制御』, 17 (1973), 596-601.