《不変埋没原理》 - 版の履歴

2007年8月6日 (月) 17:21にKuwashimaによる

2007-08-06T17:21:41Z

2007年7月25日 (水) 03:47にOrsjwikiによる

2007-07-25T03:47:06Z

Orsjwiki: "《不変埋没原理》" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T13:23:15Z

"《不変埋没原理》" を保護しました。 [edit=sysop:move=sysop]

2007年7月18日 (水) 00:39に131.112.125.103による

2007-07-18T00:39:24Z

2007年7月16日 (月) 13:40に220.104.197.230による

2007-07-16T13:40:00Z

2007年7月12日 (木) 03:15に122.17.2.240による

2007-07-12T03:15:27Z

2007年7月4日 (水) 07:37にOrsjwikiによる

2007-07-04T07:37:12Z

2007年7月4日 (水) 06:06にOrsjwikiによる

2007-07-04T06:06:00Z

差分を表示

Orsjwiki: 新しいページ: ''''【ふへんまいぼつげんり (principle of invariant imbedding)】''' 　ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)...'

2007-07-03T08:29:23Z

新しいページ: ''''【ふへんまいぼつげんり (principle of invariant imbedding)】''' 　ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)...'

新規ページ

'''【ふへんまいぼつげんり (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) $ の解($=$和)を $ S(n) $ とする. 最後の(一番大きい)問題 $ {\rm P}(10) $ の解 $ S(10) $ が求める解である. このとき, 最初の(一番易しい)問題の解は $ S(1) = 1$ であり, 相隣る問題の解 $ S(n) $ と $ S(n+1) $ の間に漸化式

$$ S(n+1) = S(n) + n+1[[利用者:Orsjwiki|Orsjwiki]] 2007年7月3日 (水) 17:29 (JST)n = 1, 2, \ldots , 9;2007年7月3日 (水) 17:29 (JST)~S(1) = 1 $$

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

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

\begin{eqnarray*}
& & \hspace{5mm} {\rm max.} \hspace{4mm}
\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})) \\
& & \hspace{5mm}\mbox{s. t.} \hspace{7mm}
x_{n+1} \in A_{n}(x_{n}) [[利用者:Orsjwiki|Orsjwiki]] (1 \le n \le N),
\end{eqnarray*}

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

\begin{eqnarray*}
& & \hspace{5mm} {\rm max.} \hspace{4mm}
\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})) \\
& & \hspace{5mm}\mbox{s. t.} \hspace{7mm}
x_{m+1} \in A_{m}(x_{m}) [[利用者:Orsjwiki|Orsjwiki]] (n \le m \le N), \\[2.34mm]
& & \hspace*{7.9mm} x_{n} \in X_{n},~~\lambda_{n}
\in \Lambda_{n}(x_{n}),~~(1 \le n \le N+1),
\end{eqnarray*}
%

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

\begin{eqnarray}
& & \Lambda_{1}(x) = \{ \tilde{\lambda}\},~~x \in X_{1}[[利用者:Orsjwiki|Orsjwiki]] 2007年7月3日 (水) 17:29 (JST) (
\tilde{\lambda}\ は\mbox{結合演算}~\circ~ \mbox{の左単位元})
\nonumber \\
& & \Lambda_{n+1}(y) = \{\, \lambda \circ g_{n}(x,\,y) \, | \, \lambda \in
\Lambda_{n}(x),~y \in A_{n}(x) \, \} \nonumber \\[-2.12mm]
& & \hspace*{40mm} y \in X_{n+1},~~ n = 1, 2, \ldots , N \nonumber
\end{eqnarray}

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

\begin{eqnarray}
& & u_{n}(x; \lambda) = \mathop{{\rm max}}_{y \in A_{n}(x)}u_{n+1}(\,y\,;
\lambda \circ g_{n}(x,\,y)) \nonumber \\[-2.12mm]
& & \hspace*{40mm} x \in X_{n}, ~~\lambda \in \Lambda_{n}(x),~~ n = 1, 2,
\ldots , N \nonumber \\
& & u_{N+1}(x; \lambda) = \psi(\lambda \circ k(x))2007年7月3日 (水) 17:29 (JST)~x \in
X_{N+1},~~\lambda \in \Lambda_{N+1}(x). \nonumber
\end{eqnarray}

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

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

\begin{eqnarray}
{\rm S}_{1}(x_{1}):\hspace{-2.21mm}& & \sum
\hspace{0.3mm}\sum\hspace{0.3mm}\cdots\hspace{0.3mm}\sum
_{\hspace{-21.1mm}(x_{2}, x_{3}, \cdots , x_{N+1}) \in P_{1}(x_{1})}
\hspace{-1.9mm}\psi(g_{1}(x_{1},x_{2}) \circ \cdots \circ
g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1}))\ \nonumber \\[2.34mm]
& & \hspace*{0.8mm}( P_{1}(x_{1}) := \{(x_{2}, \cdots , x_{N+1})\, |\,
x_{n+1} \in A_{n}(x_{n})~~1 \le n \le N \}) \nonumber
\end{eqnarray}
を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.

　このようなパラメータを導入した埋め込みは[[非可分性(動的計画法における)]] に起因し, [[単一評価系(多段決定過程における)]], [[複合評価系(多段決定過程における)]]の最適化, 期待値最適化, 多重和, 多重積分 ([[多重積分の解法]]) などで考えられる [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.

← 古い版		2007年8月6日 (月) 17:21時点における版
126行目:		126行目:

	[5] 相良節夫, 杉坂政典,「Invariant Imbedding について」,『システムと制御』, '''17''' (1973), 596-601.		[5] 相良節夫, 杉坂政典,「Invariant Imbedding について」,『システムと制御』, '''17''' (1973), 596-601.
		+
		+
		+	[[Category:動的・確率・多目的計画\|ふへんまいぼつげんり]]

← 古い版		2007年7月25日 (水) 03:47時点における版
81行目:		81行目:

	また, [[非最適化]]問題としては, [[木の総容量]]など, 多重和 ([[多重和の解法]])		また, [[非最適化]]問題としては, [[木の総容量]]など, 多重和 ([[多重和の解法]])
−
−	~~[[スタイル検討#不変埋没原理 (0054-a-e-04-1)\|スタイル検討]]~~

	<!--		<!--

@@ 81行目: / 81行目: @@
 　また, [[非最適化]]問題としては, [[木の総容量]]など, 多重和 ([[多重和の解法]])
 <table align="center">
 <tr>
-<td>[[スタイル検討#不変埋没原理 (0054-a-e-04-1)|スタイル検討]]  <math>\mbox{S}_{1}(x_{1}):~~ {\sum \sum \cdots \sum}
+<td> <math>\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

@@ 6行目: / 6行目: @@
-:<math>S(n+1) = S(n) + n+1 \quad n = 1, 2, \ldots , 9; \quad S(1) = 1\, </math>
+<center>
@@ 14行目: / 16行目: @@
-:<math>\mbox{max.} ~~ \psi(g_{1}(x_{1},x_{2}) \circ g_{2}(x_{2},x_{3}) \circ
+<table align="center">
   \cdots \circ g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1}))  \, </math>
+</td>
-:<math>\mbox{s. t.} ~~~ x_{n+1} \in A_{n}(x_{n}) \quad (1 \le n \le N), \, </math>
+</tr>
@@ 23行目: / 32行目: @@
-:<math>{\rm max.}~~ \psi(\lambda_{n} \circ g_{n}(x_{n},x_{n+1}) \circ \cdots
+<table align="center">
-  \circ g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1})) \, </math>
+<tr>
+<td><math>{\rm max.}~~ \psi(\lambda_{n} \circ g_{n}(x_{n},x_{n+1}) \circ \cdots
-:<math>\mbox{s. t.}~~~ x_{m+1} \in A_{m}(x_{m}) \quad (n \le m \le N),\, </math>
+  \circ g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1})) \, </math></td>
+</tr>
-:<math>x_{n} \in X_{n},~~ \lambda_{n} \in \Lambda_{n}(x_{n}),~~(1 \le n \le N+1),\, </math>
+<tr>
@@ 34行目: / 48行目: @@
-:<math>\Lambda_{1}(x) = \{ \tilde{\lambda}\},~~x \in X_{1}\, </math> <math>(\tilde{\lambda}\, </math>は結合演算<math>\circ\, </math>の左単位元<math>)\, </math>
+<table align="center">
+<tr>
-:<math>\begin{array}{lr}
+<td><math>\Lambda_{1}(x) = \{ \tilde{\lambda}\},~~x \in X_{1}\, </math> <math>(\tilde{\lambda}\, </math>は結合演算<math>\circ\, </math>の左単位元<math>)\, </math>  </td>
 \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}\, </math>
+\end{array}\, </math></td>
@@ 45行目: / 64行目: @@
-:<math>u_{n}(x; \lambda) = \max_{y \in A_{n}(x)}u_{n+1}(\,y\,;
+<table align="center">
-\lambda \circ g_{n}(x,\,y))\, </math>
+<tr>
-:::::<math>x \in X_{n}, ~~\lambda \in \Lambda_{n}(x),~~ n = 1, 2, \ldots , N\, </math>
+<td><math>u_{n}(x; \lambda) = \max_{y \in A_{n}(x)}u_{n+1}(\,y\,;
+\lambda \circ g_{n}(x,\,y))\, </math></td>
-:<math>u_{N+1}(x; \lambda) = \psi(\lambda \circ k(x))~~x \in X_{N+1},~~\lambda \in \Lambda_{N+1}(x).\, </math>
+</tr>
@@ 56行目: / 82行目: @@
 　また, [[非最適化]]問題としては, [[木の総容量]]など, 多重和 ([[多重和の解法]])
+<table align="center">
-:[[スタイル検討#不変埋没原理 (0054-a-e-04-1)|スタイル検討]]<math>\mbox{S}_{1}(x_{1}):~~ {\sum \sum \cdots \sum}
+<tr>
 _{(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}))\, </math>
+</td>
+</tr>
-:<math>(P_{1}(x_{1}) := \{(x_{2}, \cdots , x_{N+1})\, |\,
+<tr>
-  x_{n+1} \in A_{n}(x_{n})~~1 \le n \le N \})\, </math>
+<td><math>(P_{1}(x_{1}) := \{(x_{2}, \cdots , x_{N+1})\, |\,

@@ 57行目: / 57行目: @@
-:<math>\mbox{S}_{1}(x_{1}):~~ \displaystyle {\sum \sum \cdots \sum}
+:[[スタイル検討#不変埋没原理 (0054-a-e-04-1)|スタイル検討]]<math>\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

← 古い版	2007年7月19日 (木) 13:23時点における版
(相違点なし)

← 古い版		2007年7月4日 (水) 07:37時点における版
69行目:		69行目:
	を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.		を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.

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