【ふへんまいぼつげんり (principle of invariant imbedding)】
ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考えることを「埋め込み」(imbedding)という. すなわち, 与問題をある問題群の1つと見做すことである. このとき, 問題の大きさは小さい(易しい)ものから大きい(難しい)ものまであり, 一番大きい(解きたい)問題が与問題である. しかし, 問題の「構造」は不変である. さらに, 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. このような方法で解に至るまでを, 不変埋没原理 (principle of invariant imbedding)による方法という [1] [4] [5].
たとえば,「1から10までの自然数の和を求める」問題を考えてみよう. 以下ではいつも「1から」(前向きの方法で)考えることにして, この問題を
で表わし, 「解」(この場合, 和)を
としよう. このとき, 「1から
までの自然数の和を求める」部分問題
からなる群
を考える. このこと自体が埋め込みである. 部分問題
の解(
和)を
とする. 最後の(一番大きい)問題
の解
が求める解である. このとき, 最初の (一番易しい) 問題の解は
であり, 相隣る問題の解
と
の間に漸化式
が成り立つ. 漸化式を
の順に前向きに逐次解くことによって,
を得る. 他方, 「
から(いつも!)10までの自然数の和を求める」部分問題
の族を考えても, 上述と同様に解くことができる. これを後向きの埋め込みという.
一般の問題では, どのような大きさの問題群に埋め込むか, 関係式が導けるか, 解けるか, 解き易いかなど, 埋め込み方に工夫を要する. たとえば, 多段階の最適化問題
|
|
の最大値
と最大点
を求めるには, 新たなパラメータ
を含む部分問題群
:
![{\displaystyle {\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}))\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3610c927ab93840ec71fa51d4b43db0e4c34a00e) |
![{\displaystyle {\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}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/429715c294afa754f2376768a44794f22c0ef83c) |
に埋め込むと, パラメータ空間列
は前向きの再帰式
は結合演算 の左単位元 |
![{\displaystyle {\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}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2c31a11ca542740851dbb920776a3ad77ee12a49) |
で生成され, 最適値関数
は次の後向き再帰式を満たす:
![{\displaystyle u_{n}(x;\lambda )=\max _{y\in A_{n}(x)}u_{n+1}(\,y\,;\lambda \circ g_{n}(x,\,y))\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/def2e1336e6b1d31c05b2b62b7bcb8ee504b6549) |
![{\displaystyle ~~~~x\in X_{n},~~\lambda \in \Lambda _{n}(x),~~n=1,2,\ldots ,N\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2cfbded2f095091f2c1f55e73039ed119691b296) |
![{\displaystyle u_{N+1}(x;\lambda )=\psi (\lambda \circ k(x))~~x\in X_{N+1},~~\lambda \in \Lambda _{N+1}(x).\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6c49199ebcd9b9f2854528901815105d22dae32f) |
これを後ろから逐次解き, 最後の
に
を代入すると求める最大値が得られる:
また, 非最適化問題としては, 木の総容量など, 多重和 (多重和の解法)
|
![{\displaystyle (P_{1}(x_{1}):=\{(x_{2},\cdots ,x_{N+1})\,|\,x_{n+1}\in A_{n}(x_{n})~~1\leq n\leq N\})\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ba8bed1c0b7d190f7f9eb52b23adf361b9a07985) |
を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.
このようなパラメータを導入した埋め込みは非可分性に起因し, 単一評価系, 複合評価系の最適化, 期待値最適化, 多重和, 多重積分 (多重積分の解法) などで考えられる [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.