《不変埋没原理》

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

　ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考えることを「埋め込み」(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)\,$ の解($=\,$和)を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S(n)\, } とする. 最後の(一番大きい)問題 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm P}(10)\, } の解 $S(10)\,$ が求める解である. このとき, 最初の (一番易しい) 問題の解は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S(1) = 1\, } であり, 相隣る問題の解 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S(n)\, } と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S(n+1)\, } の間に漸化式

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S(n+1) = S(n) + n+1 \quad n = 1, 2, \ldots , 9; \quad S(1) = 1\, }

が成り立つ. 漸化式を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S(1), S(2), \ldots\, } の順に前向きに逐次解くことによって, $S(10)=55\,$ を得る. 他方, 「構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } から(いつも！)10までの自然数の和を求める」部分問題 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm Q}(n)\, } の族を考えても, 上述と同様に解くことができる. これを後向きの埋め込みという.

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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})) \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{s. t.} ~~~ x_{n+1} \in A_{n}(x_{n}) \quad (1 \le n \le N), \, }

の最大値 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u_{1}(x_{1})\, } と最大点 $x^{*}=(x_{1},x_{2}^{*},\ldots ,x_{N+1}^{*})\,$ を求めるには, 新たなパラメータ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda_{n} (\in \Lambda_{n}(x_{n}))\, } を含む部分問題群 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal P} = \{ {\rm P}_{n}(x_{n};\lambda_{n}) \}\, }  :

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\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})) \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{l}\mbox{s. t.} ~~~ x_{m+1} \in A_{m}(x_{m}) \quad (n \le m \le N), \\ ~~~~ x_{n} \in X_{n}, \; \lambda_{n} \in \Lambda_{n}(x_{n}), ~ (1 \le n \le N+1), \end{array} \, }

に埋め込むと, パラメータ空間列 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{\Lambda_{n}(\cdot)\}\, } は前向きの再帰式

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Lambda_{1}(x) = \{ \tilde{\lambda}\},~~x \in X_{1}\, } 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\tilde{\lambda}\, } は結合演算構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \circ\, } の左単位元構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle )\, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\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}\, }

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u_{n}(x; \lambda) = \max_{y \in A_{n}(x)}u_{n+1}(\,y\,; \lambda \circ g_{n}(x,\,y))\, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle ~~~~x \in X_{n}, ~~\lambda \in \Lambda_{n}(x),~~ n = 1, 2, \ldots , N\, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u_{N+1}(x; \lambda) = \psi(\lambda \circ k(x))~~x \in X_{N+1},~~\lambda \in \Lambda_{N+1}(x).\, }

これを後ろから逐次解き, 最後の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u_{1}(x_{1};\lambda_{1})\, } に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda_{1} = \tilde{\lambda}\, } を代入すると求める最大値が得られる： 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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}))\,$

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (P_{1}(x_{1}) := \{(x_{2}, \cdots , x_{N+1})\, |\, x_{n+1} \in A_{n}(x_{n})~~1 \le n \le 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.