ORWiki - 利用者の投稿記録 [ja]

《不変埋没原理》

2007-07-18T00:39:24Z

131.112.125.103:

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

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

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

<center>
<math>S(n+1) = S(n) + n+1 \quad n = 1, 2, \ldots , 9; \quad S(1) = 1\, </math>
</center>

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

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

<table align="center">
<tr>
<td><math>\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})) \, </math>
</td>
</tr>
<tr>
<td><math>\mbox{s. t.} ~~~ x_{n+1} \in A_{n}(x_{n}) \quad (1 \le n \le N), \, </math>
</td>
</tr>
</table>

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

<table align="center">
<tr>
<td><math>{\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})) \, </math></td>
</tr>
<tr>
<td><math>\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} \, </math></td>
</tr>
</table>

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

<table align="center">
<tr>
<td><math>\Lambda_{1}(x) = \{ \tilde{\lambda}\},~~x \in X_{1}\, </math> <math>(\tilde{\lambda}\, </math>は結合演算<math>\circ\, </math>の左単位元<math>)\, </math> </td>
</tr>
<tr>
<td><math>\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}\, </math></td>
</tr>
</table>

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

<table align="center">
<tr>
<td><math>u_{n}(x; \lambda) = \max_{y \in A_{n}(x)}u_{n+1}(\,y\,;
\lambda \circ g_{n}(x,\,y))\, </math></td>
</tr>
<tr>
<td align="right"><math>~~~~x \in X_{n}, ~~\lambda \in \Lambda_{n}(x),~~ n = 1, 2, \ldots , N\, </math></td>
</tr>
<tr>
<td><math>u_{N+1}(x; \lambda) = \psi(\lambda \circ k(x))~~x \in X_{N+1},~~\lambda \in \Lambda_{N+1}(x).\, </math></td>
</tr>
</table>

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

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

[[スタイル検討#不変埋没原理 (0054-a-e-04-1)|スタイル検討]]



<table align="center">
<tr>
<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
g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1}))\, </math>
</td>
</tr>
<tr>
<td><math>(P_{1}(x_{1}) := \{(x_{2}, \cdots , x_{N+1})\, |\,
x_{n+1} \in A_{n}(x_{n})~~1 \le n \le N \})\, </math></td>
</tr>
</table>

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

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

131.112.125.103:

'''【くろすこうりつち (cross efficiency)】'''

評価対象事業体(DMU) <math>a\,</math>の効率値を求めるための最適な乗数を用いて計算される, DMU <math>a\,</math>以外のDMUの効率値をクロス効率値と呼ぶ. 入力数を<math>m\,</math>, 出力数を<math>k\,</math>とし, DMU <math>a\,</math>の効率値を計算する入力乗数を <math>v_{ia}^*\,</math>, 出力乗数を <math>u_{ra}^*\,</math> とすると, DMU <math>j\,</math> のクロス効率値は

<table>
<tr><math>
\eta_{ja} = \left. {\displaystyle{\sum_{r=1}^{k} Y_{rj} \cdot u_{ra}^*}} \right/
{\displaystyle{\sum_{i=1}^{m} X_{ij} \cdot v_{ia}^*}}\,</math></tr>
<tr><math> (j=1, \ldots, n; a=1, \ldots, n) \,</math></tr>
</table>

で計算される. 評価対象DMUがD効率的なとき, その最適乗数やクロス効率値は一意に決まるとは限らないことに注意が必要である.

繰り返し法 (動的計画法における)

2007-07-11T18:19:16Z

131.112.125.103:

'''【くりかえしほう (iterative method)】'''

基本的には多変数同時問題を1変数問題の繰り返しで解く方法. 例えば, 原始政策 <math> \mu = \{\mu_{1}, \mu_{2} \} \in \Pi_{p} \,</math> の2変数同時最適化問題

<math>
\mathbf{max}_{\mu}
\sum \sum_{(x_2,x_3)}
g(x_1,u_1,x_2,u_2,x_3) \cdot
p(x_2\vert x_1,u_1)p(x_3\vert x_2, u_2)
\,</math>

を解く代わりに, <math> \mu_{2} \,</math> による最適化の後に <math> \mu_{1} \,</math> による最適化を行なう問題

<math>
{\mathbf{max}}_{\mu_1}\mathbf{max}_{\mu_2}
\sum \sum_{(x_2,x_3)} g(x_1,u_1,x_2,u_2,x_3) \cdot p(x_2\vert x_1,u_1)p(x_3\vert x_2, u_2)
\,</math>

を解く方法. ただし, <math>u_{1} = \mu_{1}(x_{1}), u_{2} = \mu_{2}(x_{1},u_{1},x_{2})\,</math>.

グラフ (グラフ理論の)

2007-07-11T18:06:03Z

131.112.125.103:

'''【ぐらふ (graph)】'''
グラフは, 点の集合<math>V\,</math>, 枝の集合<math>A\,</math>および各枝<math>a\in A\,</math>の始点と終点を指定する2つの写像<math>\partial^+: A \to V\,</math>と<math>\partial^-: A \to V\,</math>からなる複合概念であり, グラフ<math>G=(V,A;\partial^+,\partial^-)\,</math> (あるいは <math>(V,A)\,</math> )のように記される. グラフは平面上に, 点を丸で, 枝を矢線で描き, 幾何学的に表現される. 枝<math>a\,</math>の矢線の始点が<math>\partial^+a\,</math>を, 終点が<math>\partial^-a\,</math>を表す. 枝の方向を考慮する場合を有向グラフ, 考慮しない場合を無向グラフと呼び区別する.

グラビティーモデル

2007-07-11T18:04:07Z

131.112.125.103:

'''【ぐらびてぃーもでる (gravity model)】'''

2つの物体間に働く引力の大きさを与えるニュートンの万有引力の法則に基づいて, 地域<math>i\,</math>から地域<math>j\,</math>への物資あるいは情報の移動量<math>f_{ij}\,</math>を, 地域<math>i\,</math>を出発地とする移動総量<math>p_{i}\,</math>, 地域<math>j\,</math>を到着地とする移動総量<math>q_{j}\,</math>, <math>i\,</math>, <math>j\,</math>両地域間の距離<math>d_{ij}\,</math>, パラメタ<math> K, a, b, c \,</math>を用いて

<math> f_{ij} = K \frac{p_{i}^{a}q_{j}^{b}}{d_{ij}^{c}}
i \in N, j \in N \,</math>

のように表し, 実証データに基づいてパラメタ値を推計したもの.

クラスMAX SNP

2007-07-11T18:02:18Z

131.112.125.103:

'''【くらすまっくすえすえぬぴー (class MAX SNP)】'''

厳密解だけでなく, よい近似解すら求めるのが困難な問題のクラスの1つ. 厳密解を求めることが困難な問題であっても, 任意の正定数<math>\epsilon\,</math>を与えれば, <math>(1/\epsilon)\,</math>と入力の大きさの多項式時間で, 近似率<math>\epsilon\,</math>の解を求められる場合がある. しかしMAXSNP困難な問題は, <math>\mbox{P}\neq \mbox{NP}\,</math>という仮定の下では, 多項式時間で近似率<math>\epsilon\,</math>の近似解を求められるような<math>\epsilon\,</math>に限界がある.

クラスNC

2007-07-11T18:00:39Z

131.112.125.103:

'''【くらすえぬしい (class NC)】'''

並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ<math>n\,</math>の多項式個のプロセッサを使えば, <math>\log n\,</math>の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである.

クラインロックの保存則

2007-07-11T17:59:27Z

131.112.125.103:

'''【くらいんろっくのほぞんそく (Kleinrock's conservation law)】'''

任意の単一サーバ待ち行列G/GI/1システムを考える. <math>C\,</math>クラスの客がシステムに到着し, クラス<math>c\,</math> の到着率は <math>\lambda_c\,</math>, サービス時間<math>S_c\,</math>は独立で同一分布にしたがうならば, 平均残余仕事量E(<math>V\,</math>)(時間平均) は次式で与えられる.

<math> E(V) = \sum_{c = 1}^C [ E(Q_c) E(S_c) +
\rho_c \,E(S_c^2) / 2 E(S_c)] \,</math>

ここで, クラス<math>c\,</math>に対しE<math>(Q_c)\,</math>は平均待ち行列長(時間平均), E<math>(S_c)\,</math>, E<math>(S_c^2)\,</math> はサービス時間の1, 2次積率, <math>\rho_c \ (= \lambda_c \mbox{E} (S_c))\,</math> はトラヒック密度である.

区間木

2007-07-11T17:56:24Z

131.112.125.103:

'''【くかんぎ (interval tree)】'''

整数区間<math>I\,</math>を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. %区間木のノードにはそれぞれ分割に対応する整数区間が付随する. さらに<math>I\,</math>の与えられた部分区間の集合<math>\mathcal{I}\,</math>をこの対応に基づいて適切に記憶することにより, 区間の集合に対する探索をサポートする効率的なデータ構造が得られる. それを用いれば, <math>n\,</math>個の区間の集合<math>\mathcal{I}\,</math>に対して, 質問点<math>x\,</math>を含む <math>\mathcal{I}\,</math> の区間をすべて求める問題などが%区間木を用いて効率的に解ける.

区間AHP

2007-07-11T17:54:43Z

131.112.125.103:

'''【くかんえいえいちぴー (interval AHP)】'''

意思決定者のあいまいな判断を取り入れるために, 一対比較値を区間表現として拡張した方法の1つであり, 一対比較値<math>a_{ij}\,</math>を区間値<math>[l_{ij},u_{ij}]\,</math>で表現したAHPである.

クープマン問題

2007-07-11T17:53:47Z

131.112.125.103:

'''【くーぷまんもんだい (Koopman problem)】'''

クープマンが1957年に最初に提起した探索努力の最適配分問題である. 探索空間全体を <math> X=(-\infty, \infty) \,</math>, 点<math> x \in X\,</math>に目標物が存在する確率密度を<math> p(x) \,</math> とする. 点<math> x\,</math>に投入する探索努力密度を<math> \varphi(x) \,</math>とするとき, ここに存在する目標物を確率<math> 1-\exp( - \varphi(x) ) \,</math>で探知できると仮定する. このとき, 探索努力総量<math> \Phi\,</math>の制約下で目標探知確率最大化の探索努力密度を求める次の問題のこと.

<math>
\max_{\{\varphi(x)\}} \int_X p(x) [ 1- \exp(- \varphi(x)) ] dx .
\,</math>

ただし, <math>\varphi(x) \geq 0, \displaystyle{\int_X \varphi(x) {\mbox{d}}x =\Phi .}\,</math>

近接点法

2007-07-11T17:49:35Z

131.112.125.103:

'''【きんせつてんほう (proximal point method)】'''

写像 <math>F: \mathbf{R}^{n} \rightarrow \mathbf{R}^{n}\,</math> と凸集合 <math>S \subseteq \mathbf{R}^{n}\,</math> により定義される変分不等式問題

<math>
\mathbf{find}x \in S \quad \mathbf{s.t.}
( z - x )^{\top} F(x) \geq 0, \forall \, z \in S,
\,</math>

に対する反復法. 単調非減少な正定数の列 <math>\{ \lambda^{(k)} \}\,</math> を定め, 変分不等式

<math>
( z - x )^{\top}\{ F(x) + ( x - x^{(k)} ) \, / \, \lambda^{(k)}
\} \geq 0, \forall \, z \in S,
\,</math>

の解を <math>x^{(k+1)}\,</math> とおいて点列 <math>\{ x^{(k)} \}\,</math> を生成する. 付加された項が問題の性質を改善するので, 複雑な問題を効率的に解くアルゴリズムを構成できる.

近接可能領域

2007-07-11T17:43:59Z

131.112.125.103:

'''【きんせつかのうりょういき (region of approach)】'''

劣速の目標物(速度 <math>u\,</math>)が探索者(速度 <math>v\,</math>)に会合できるのは, 目標物が探索針路から <math>\pm \theta= \pm \sin^{-1}(u/v), v>u\,</math>, の楔形領域にいるときである. 角 <math>\theta \,</math>を近接限度角という. 制限時間 <math> T\,</math> があるときは探索者の針路を挟む中心角 <math> 2\theta\,</math>, 弦の長さ <math> vT\,</math>, 弧の曲率半径 <math> uT\,</math> の扇形領域が目標物の近接可能領域となる. 目標物が優速ならば時間制限がなければ常に探索者に会合できるが, 時間制限があれば近接可能領域は探索者の前方 <math> vT\,</math> の点を中心とする半径 <math> uT\,</math> の円内となる.

均衡問題 (ゲーム理論における)

2007-07-11T17:42:31Z

131.112.125.103: 新しいページ: ''''【きんこうもんだい (equilibrium problem)】''' 複数の競合するプレイヤーが参加するゲームにおいて, 各プレイヤーが自分の戦略を変...'

'''【きんこうもんだい (equilibrium problem)】'''

複数の競合するプレイヤーが参加するゲームにおいて, 各プレイヤーが自分の戦略を変えることによって自分の利得を増やすことができない状態を均衡状態といい, そのような均衡状態を求める問題を均衡問題と呼ぶ. 多くの均衡問題は相補性問題や変分不等式問題として定式化できる.

均衡制約計画問題

2007-07-11T17:41:41Z

131.112.125.103:

'''【きんこうせいやくけいかくもんだい (mathematical programming problem with equilibrium constraints (MPEC))】'''

パラメータ <math>y\in \mathbf{R}^m\,</math> をもつ相補性問題の解集合を

<table>
<tr><td><math>
S(y):=\{ x \in \mathbf{R}^n \,</math></td><td><math> | x_{i}\geq 0, F_{i}(x,y)\geq 0, \,</math></td></tr>
<tr><td></td><td><math> x_iF_i(x,y)=0 (i=1,\dots,n)\}
</math></td></tr>
</table>

とする. このとき, 数理計画問題

<table><tr><td><math>
\min.\,</math></td><td><math> f(x,y)\,</math></td></tr>
<tr><td><math>
s.t.\,</math></td><td><math> x \in S(y), \quad (x,y) \in X \subseteq \mathbf{R}^{n+m}\,</math></td></tr>
</table>

を均衡制約計画問題という.

キングマン, ジョン・F・C

2007-07-11T17:31:44Z

131.112.125.103:

'''【きんぐまん, じょん・F・C (Kingman, John F. C.)】'''

待ち行列モデルに対するキングマン代数(Kingman algebra)を構築して, それまでの解析手法を代数的な視点で解釈するとともに, 一般的な複数サーバモデルの理論解析が極めて困難であることを明らかにし, その後の待ち行列研究の方向性に影響を与えた. この他にも, 待ち行列モデルの重負荷近似, 待ち時間に対する不等式, 人口過程における可逆過程, 確率過程のエルゴード性, 再生型過程など, 確率過程論全般にわたって先駆的な研究を行っている(1939--　).

距離対探知確率曲線

2007-07-11T17:30:37Z

131.112.125.103:

'''【きょりたいたんちかくりつきょくせん (detection probability versus range curve)】'''

一定の目標条件・環境・センサーの条件の下で, 相対距離 <math> r\,</math> にある目標物を単位時間の探索で発見する確率を距離対探知確率といい, <math>r \,</math>に対するその関数を距離対探知確率曲線 <math> b(r) \,</math> と呼ぶ. この値はセンサーによる目標空間の走査が連続的な場合は, 単位時間当りの確率密度(瞬間探知率), 離散的な場合には1回のべっ見の探知確率(べっ見探知確率)で表わされる. また発見法則と呼ばれることもある.

許容解

2007-07-11T17:29:42Z

131.112.125.103:

'''【きょようかい (feasible solution)】'''

:参照：[[実行可能集合]]

許容集合

2007-07-11T17:28:13Z

131.112.125.103:

'''【きょようしゅうごう (feasible region)】'''

:参照：[[実行可能集合]]

許容集合

2007-07-11T17:26:23Z

131.112.125.103:

極変換

2007-07-11T17:24:49Z

131.112.125.103:

'''【きょくへんかん (polar transformation)】'''

2次曲線に関する点と直線の双対変換のこと. <math>d\,</math>次元空間では, 2次曲面が<math>(d+1) \times (d+1)\,</math>対称行列<math>A\,</math>と<math>d\,</math>次元ベクトル<math>x\,</math>を用いて<math>(x,1)^{\top} A(x,1)=0\,</math>と表せ, 点<math>p\,</math>に対して, 方程式<math>(x,1)^{\top} A(p,1)=0\,</math>を満たす超平面<math>D(p)\,</math>を対応させる. 逆に定数ベクトル<math>p\,</math>を用いて<math>(x,1) A(p,1)=0\,</math>と書ける超平面<math>h\,</math>に対して点 <math>D(h)=p\,</math>を対応させる. 明らかに<math>D(D(p))=p\,</math>, <math>D(D(h))=h\,</math>である. 極変換は, 接続関係を保存する.

局所辺連結度

2007-07-11T17:21:20Z

131.112.125.103:

'''【きょくしょへんれんけつど (local edge connectivity)】'''

無向(有向)グラフの2点<math>s,t\,</math>に対し, <math>s\,</math>から<math>t\,</math>への辺素である(すなわち互いに辺を共有しない)路の本数の最大値を<math>s,t\,</math>間の局所辺連結度という. この値は, <math>s\,</math>から<math>t\,</math>への路をなくすために取り除くべき辺の本数の最小値に等しい(辺型のメンガー(Menger)の定理).

局所点連結度

2007-07-11T17:20:04Z

131.112.125.103:

'''【きょくしょてんれんけつど (local vertex connectivity)】'''

無向(有向)グラフの2点<math>s,t\,</math>に対し, <math>s\,</math>から<math>t\,</math>への内素である(すなわち<math>s,t\,</math>以外では点を共有しない)路の本数の最大値を<math>s,t\,</math>間の局所点連結度という. この値は, <math>s\,</math>から<math>t\,</math>への辺が存在しないとき, <math>s\,</math>から<math>t\,</math>への路をなくすために取り除くべき<math>s,t\,</math>以外の点の個数の最小値に等しい(点型のメンガー(Menger)の定理).

局所的最適解

2007-07-11T17:18:52Z

131.112.125.103:

'''【きょくしょてきさいてきかい (local optimal solution)】'''

数理計画問題:

<math>
\min. \ f(x) \quad \mbox{s.t.} \ x \in S
\,</math>

において, 点 <math>x^* \in S\,</math> とその適当な近傍 <math>N(x^*)\,</math> に対して

<math>
f(x^*) \le f(x) \quad \forall \ x \in S \cap N(x^*)
\,</math>

が成り立つとき, <math>x^*\,</math> を局所的最適解という. 非凸計画問題においては通常多くの局所的最適解が存在し, 大域的最適解を見出すのは困難なことが多い.

局所探索法

2007-07-11T17:16:30Z

131.112.125.103:

'''【きょくしょたんさくほう (local search)】'''

最適化問題の実行可能解や近似解<math>x\,</math>に対して, その近傍の解集合<math>N(x)\,</math>を定義する. 何らかの順序で(あるいはランダムに)<math>N(x)\,</math>内の解を探索してゆき, <math>x\,</math>よりも良い解が見つかれば<math>x\,</math>の更新を行い, 再びその<math>x\,</math>に対して<math>N(x)\,</math>を生成し, 同様の手続きを更新が行われるかぎり繰り返す. 局所探索の結果得られる解は局所最適ではあるが, 大域最適であるとは限らないため, メタヒューリスティクス等の様々な手法が取り入れられる.

極限分布

2007-07-11T17:14:59Z

131.112.125.103:

'''【きょくげんぶんぷ (limiting distribution)】'''

確率過程の時点<math>t\,</math>における分布が, <math>t\rightarrow\infty\,</math>のとき初期状態に無関係な分布に収束する場合, その分布を極限分布と呼ぶ.

行列分割法

2007-07-11T17:13:39Z

131.112.125.103:

'''【ぎょうれつぶんかつほう (matrix splitting method)】'''

行列 <math>M\,</math>, ベクトル <math>q\,</math> と凸多面体 <math>X\,</math> により定義される線形変分不等式問題

<math>
\mathbf{find}x \in X \quad \mathbf{s.t.} ( z - x )^{\top} ( M x + q ) \geq 0, \forall \, z \in X,
\,</math>

に対する反復法. 条件 <math>M = B + C\,</math> を満たす行列 <math>B\,</math>, <math>C\,</math> を選び, 変分不等式

<math>
( z - x )^{\top} ( B x + C x^{(k)} + q ) \geq 0,
\forall \, z \in X,
\,</math>

の解を <math>x^{(k+1)}\,</math> とおいて点列 <math>\{ x^{(k)} \}\,</math> を生成する. 行列 <math>B\,</math> を適切に選ぶことにより, 大規模問題を効率的に解くための様々なアルゴリズムが得られる.

行列分割法

2007-07-11T17:12:21Z

131.112.125.103:

'''【ぎょうれつぶんかつほう (matrix splitting method)】'''
行列 <math>M\,</math>, ベクトル <math>q\,</math> と凸多面体 <math>X\,</math> により定義される線形変分不等式問題

<math>
\mathbf{find}x \in X \quad \mathbf{s.t.} ( z - x )^{\top} ( M x + q ) \geq 0, \forall \, z \in X,
\,</math>

に対する反復法. 条件 <math>M = B + C\,</math> を満たす行列 <math>B\,</math>, <math>C\,</math> を選び, 変分不等式

<math>
( z - x )^{\top} ( B x + C x^{(k)} + q ) \geq 0,
\forall \, z \in X,
\,</math>

の解を <math>x^{(k+1)}\,</math> とおいて点列 <math>\{ x^{(k)} \}\,</math> を生成する. 行列 <math>B\,</math> を適切に選ぶことにより, 大規模問題を効率的に解くための様々なアルゴリズムが得られる.

行列幾何形式解

2007-07-11T17:06:55Z

131.112.125.103:

'''【ぎょうれつきかけいしきかい (matrix-geometric solution)】'''

ある種のエルゴード的マルコフ連鎖の定常状態確率ベクトル<math>\pi\,</math>が, 状態空間の分割に対応して <math>\pi=(\pi_0, \pi_1,\pi_2,\cdots )\,</math> と小ベクトルに分割されたとき, 公比行列と呼ばれる行列 <math>R\,</math> によって

<table><tr>
<td><math>\pi_n=\pi_1 R^{n-1},\,</math></td><td></td>
<td><math>
\quad n=1,2,\ldots\,</math></td>
</tr></table>

と書けるとき, これを行列幾何形式解という. 例えば, PH/PH/<math>c\,</math> 待ち行列モデルでは定常状態確率ベクトルがこの形になることが知られている.

鏡像原理

2007-07-11T16:56:18Z

131.112.125.103:

'''【きょうぞうげんり (reflection principle)】'''

<math>\{B(t)\}_{t\ge0}\,</math> をドリフトのないブラウン運動, <math>T\,</math> を <math>\{B(t)\}_{t\ge0}\,</math> (の履歴)に関する停止時とするとき,

<table>
<tr>
<td rowspan="2"><math>\bar{B}(t)=\Bigg\{\,</math></td>
<td><math>B(t),\,</math></td><td><math>\quad t <T,\,</math></td>
</tr>
<tr>
<td><math>2\,B(T) - B(t),\,</math></td><td><math> \quad t\ge T,\,</math></td>
</tr>
</table>

によって定義される確率過程<math>\{\bar{B}(t)\}_{t\ge0}\,</math> がまたドリフトのないブラウン運動になる性質. 初到達時間の計算などに利用される.

逆凸計画問題

2007-07-11T16:45:11Z

131.112.125.103:

'''【ぎゃくとつけいかくもんだい (reverse convex programming problem)】'''

実行可能集合が閉凸集合<math>D \subset \mathbf{R}^n\,</math>と開凸集合<math>C \subset \mathbf{R}^n\,</math>の差<math>D \setminus C :=
\{x \in \mathbf{R}^n \mid x \in D,\; x \not\in C\}\,</math>によって与えられる最適化問題:

<table><tr>
<td><math>\mathbf{min.}f(x) \quad \,</math></td><td></td><td><math> \mathbf{s.t.} x \in D \setminus C.\,</math>
</tr></table>

目的関数<math>f\,</math>が凸関数であっても, <math>D \setminus C\,</math>が一般に凸集合ではないため, 値が異なる複数の局所的最適解が存在する.

逆n乗発見法則

2007-07-11T16:32:55Z

131.112.125.103:

'''【ぎゃくえぬじょうはっけんほうそく (inverse <math>n\,</math>th power detection law)】'''

距離対探知確率曲線(発見法則)の近似モデルの1つであり, 瞬間探知率<math>b(r)\,</math>が目標物と探索者の相対距離<math>r\,</math>の<math>n\,</math>乗に逆比例すると仮定し, 2つのパラメータ<math>(k,n)\,</math>を用いて, <math>b(r) = ( k/r)^n\,</math>で表わす. 特殊ケースとして逆3乗法則<math>(n=3\,</math>の場合)や完全定距離法則<math>( n \to \infty \,</math>の場合)を含む一般的な発見法則であり, 横距離探知確率や有効探索幅等も解析的に閉じた式で求められる.

既約

2007-07-11T16:27:38Z

131.112.125.103:

'''【きやく (irreducible)】'''

マルコフ連鎖やマルコフ過程において, どの状態から他のどの状態へも到達可能であること.

客

2007-07-11T16:27:25Z

131.112.125.103:

'''【きゃく (customer)】'''

待ち行列モデルにおいて, サービスを受ける主体. 実際問題への応用の際には, 製品, 部品, ジョブ, 呼(こ, よび), 情報など様々な実体が客として扱われる. なお``呼''というのは電話における接続要求のことで, 待ち行列理論が最初に電話の問題へ適用された名残から``呼損率''などの用語の中で今も使われている.

基本分割

2007-07-11T16:25:15Z

131.112.125.103:

'''【きほんぶんかつ (principal partition)】'''

有限集合 <math>N\,</math> の部分集合族 <math>\mathcal{D}\,</math> が分配束をなすとき, <math>\mathcal{D}\,</math> 上の劣モジュラ関数 <math>f\,</math> の最小値を達成する <math>X\in\mathcal{D}\,</math> の全体は, <math>\mathcal{D}\,</math> の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は <math>N\,</math> の適当な部分集合への分割と各成分間の半順序関係によって表現される. この原理に基づいて, 劣モジュラ関数で記述された離散システムを分解する手法を総称して基本分割と呼ぶ.

規模の効率性

2007-07-11T16:23:08Z

131.112.125.103:

'''【きぼのこうりつせい (scale efficiency)】'''

BCCモデルはCCRモデルよりも制約が多いため生産可能集合が狭められて着目DMU <math>J\,</math>の効率値<math>\theta_J\,</math> (BCC)はCCRモデルの効率値<math>\theta_J\,</math> (CCR)以上になる. そこで<math>\theta_J\,</math> (CCR)を全体効率性, <math>\theta_J\,</math> (BCC)を技術効率性と考え, その差異は規模の効率性によるものと考えると, 規模の効率性<math>=\,</math>全体効率性<math>\theta_J\,</math> (CCR) / 技術効率性<math>\theta_J\,</math> (BCC)と捉えることができる. すなわち, 規模の効率性は最も生産的な規模にどの程度近いかを表す指標である.

基底解

2007-07-11T16:14:33Z

131.112.125.103:

'''【きていかい (basic solution)】'''

方程式系 <math>Ax=b\,</math>を考える. ただし, <math>A\,</math>は<math>m\times n\,</math>行列(<math>m \leq n\,</math>)で,<math>b\,</math>は<math>n\,</math>次元のベクトルである.<math>A\,</math>から <math>m\times m\,</math> 正則部分行列 <math>B\,</math> を任意に選ぶ. この行列 <math>B\,</math> を基底行列と呼ぶ. 基底行列 <math>B\,</math>の列に対応する <math>x\,</math>の要素は基底変数,対応しない <math>x\,</math>の要素は非基底変数と呼ばれる. 非基底変数をすべて<math>0\,</math>にして得られる方程式系<math>Ax=b\,</math>の解<math>x\,</math>は一意に定まるが,この解を基底行列<math>B\,</math>についての基底解と呼ぶ.

基底解

2007-07-11T16:13:55Z

131.112.125.103:

'''【きていかい (basic solution)】'''

方程式系 <math>Ax=b\,</math>を考える. ただし, <math>A\,</math>は<math>m\times n\,</math>行列(<math>m \leq n\,</math>)で,<math>b\,</math>は<math>n\,</math>次元の
ベクトルである.<math>A\,</math>から <math>m\times m\,</math> 正則部分行列 <math>B\,</math> を任意に選ぶ. この行列 <math>B\,</math> を
基底行列と呼ぶ. 基底行列 <math>B\,</math>の列に対応する <math>x\,</math>の要素は基底変数,対応しない <math>x\,</math>の要素は非基底変数と呼ばれる. 非基底変数をすべて<math>0\,</math>にして得られる方程
式系<math>Ax=b\,</math>の解<math>x\,</math>は一意に定まるが,この解を基底行列<math>B\,</math>についての基底
解と呼ぶ.

基底解

2007-07-11T16:12:12Z

131.112.125.103:

基多面体

2007-07-11T15:58:02Z

131.112.125.103:

'''【きためんたい (base polyhedron)】'''

有限集合 <math>N\,</math> 上の実数値関数全体のなす線形空間を <math>\mathbf{R}^N\,</math> と表す. 劣モジュラシステム <math>(\mathcal{D},f)\,</math> は, <math>\mathbf{R}^N\,</math> 中の基多面体

<table>
<tr>
<td><math> \mathbf{B}(f)=\{x\,</math></td><td><math>\mid x\in\mathbf{R}^N,\sum_{i\in N}x(i)=f(N),\,</math></td>
</tr>
<tr><td></td><td><math>\forall X\in\mathcal{D}:\sum_{i\in X}x(i)\leq f(X)\}\,</math></td></tr>
</table>

を定める. 基多面体上では, 貪欲アルゴリズムによって線形目的関数の最適化が可能である.

期待値

2007-07-11T15:38:23Z

131.112.125.103:

'''【きたいち (expectation)】'''

確率変数<math>X\,</math> の確率分布関数を <math>F(x)\,</math> とするとき, <math>\mathrm{E}(X)=\int_{-\infty}^\infty x \mathrm{d} F(x)\,</math> で定義される値. 分布の中心を表す代表的な値である. <math>F(x)\,</math> が確率関数 <math>p(i)=\mathrm{P}(X=a_i)\,</math> をもつ離散型分布の場合は <math>\sum_i a_i p(i)\,</math>, 密度関数 <math>f(x)\,</math> をもつ場合は <math>\int_{-\infty}^\infty x f(x) \mathrm{d} x\,</math> で計算される.

基族

2007-07-11T15:36:45Z

131.112.125.103:

'''【きぞく (base family)】'''

マトロイド <math>\mathbf{M}=(N,\mathcal{I})\,</math> において, 極大な独立集合を基と呼ぶ. すべての基を集めた基族 <math>\mathcal{B}\,</math> は以下の <math>(\mathbf{B0})-(\mathbf{B1})\,</math> を満たす.

<math>(\mathbf{B0})\,</math> <math>\mathcal{B}\neq\emptyset\,</math>.

<math>(\mathbf{B1})\,</math> <math>B,F\in\mathcal{B}\,</math>,
<math>i\in B\backslash F\Rightarrow\exists j\in F\backslash B\,</math>:
<math>(B\backslash\{i\})\cup\{j\}\in\mathcal{B}\,</math>.

逆に, <math>(\mathbf{B0})-(\mathbf{B1})\,</math> を満たす部分集合族 <math>\mathcal{B}\,</math> によってマトロイドを定義することもできる.

技術効率性

2007-07-11T15:26:50Z

131.112.125.103:

'''【ぎじゅつこうりつせい (technical efficiency)】'''

DEA において, 入出力項目ともに技術的要素に基づいて測定される効率性. BCCモデルはCCRモデルよりも制約が多いため生産可能集合が狭められて着目DMU <math>J\,</math>の効率値<math>\theta_J\,</math> (BCC)はCCRモデルの効率値<math>\theta_J\,</math> (CCR)以上になる. そこで<math>\theta_J\,</math> (CCR)を全体効率性, <math>\theta_J\,</math>(BCC)を技術効率性と考えて2つの効率性を区別できる. また, コスト効率性を全体効率性<math>\theta_J\,</math> (cost)と考えて, CCRモデルの効率値<math>\theta_J\,</math> (CCR) を(全体)技術効率性と考えることもできる.

幾何ブラウン運動

2007-07-11T15:24:01Z

131.112.125.103:

'''【きかぶらうんうんどう (geometric Brownian motion)】'''

<math>S_t\,</math>を時刻<math>t\,</math>における危険資産価格とする. <math>S_t\,</math>が次の確率微分方程式

<math> \mathbf{d}S_t=\mu S_t \mathbf{d}t +\sigma S_t \mathbf{d}B_t \,</math>

にしたがうとき, 幾何ブラウン運動という. ただし<math>B_t\,</math>は標準ブラウン運動, <math>\mu\,</math>,<math>\sigma\,</math>は,ある一定の係数とする. 時点<math>0\,</math>での株価を<math>S_0\,</math>とすると, <math>S_t\,</math>の解過程は

<math>S_t=S_0 \exp \{(\mu - (1/2) \sigma^2 )t+\sigma B_t \} \,</math>

で与えられる.

幾何ブラウン運動

2007-07-11T15:23:29Z

131.112.125.103:

'''【きかぶらうんうんどう (geometric Brownian motion)】'''

<math>S_t\,</math>を時刻<math>t\,</math>における危険資産価格とする. <math>S_t\,</math>が次の確率微分方程式

<math> \mathcal{d}S_t=\mu S_t \mathcal{d}t +\sigma S_t \mathcal{d}B_t \,</math>

にしたがうとき, 幾何ブラウン運動という. ただし<math>B_t\,</math>は標準ブラウン運動, <math>\mu\,</math>,<math>\sigma\,</math>は,ある一定の係数とする. 時点<math>0\,</math>での株価を<math>S_0\,</math>とすると, <math>S_t\,</math>の解過程は

<math>S_t=S_0 \exp \{(\mu - (1/2) \sigma^2 )t+\sigma B_t \} \,</math>

で与えられる.

幾何平均法 (AHPの)

2007-07-11T15:13:58Z

131.112.125.103:

'''【きかへいきんほう (geometric mean method)】'''

一対比較行列から重要度を算出する方法の1つであり, 一対比較行列の行の要素の幾何平均

<math>
w_i = \left( \prod^{n}_{j=1}a_{ij} \right)^{\frac{1}{n}} \;\; (i=1,2,\ldots,n)
\,</math>

を求め, 重要度を算出する方法である. 幾何平均法は, よく固有ベクトル法の簡便法として紹介されるが, 対数最小二乗法(LLSM)と同じである.

幾何分布

2007-07-11T14:54:39Z

131.112.125.103:

'''【きかぶんぷ (geometric distribution)】'''

自然数 <math>\{1,2,3,\ldots\}\,</math> をとる離散型分布の1つ. 実数 <math>p \in (0,1)\,</math> をパラメータとし, 確率関数は <math>p(k)=(1-p)^{k-1} p, \; k=1,2,\ldots\,</math> で与えられる. 例えば, 確率 <math>p\,</math> で表が出るコインを初めて表が出るまで投げたときに, コインを投げた回数は幾何分布にしたがう.

幾何計画問題

2007-07-11T14:30:06Z

131.112.125.103:

'''【きかけいかくもんだい (geometric programming problem)】'''

目的関数, 制約関数がいずれも変数 <math>x = (x_1, \ldots, x_n)\,</math> の累乗の和, つまり実数 <math>c_k\,</math>, <math>a_{kj}\,</math> (<math>j = 1, \ldots, n\,</math>)に対し, <math>c_k x_1^{a_{k1}} x_2^{a_{k2}} \cdots x_n^{a_{kn}}\,</math> の和として表される最適化問題. 係数 <math>c_k\,</math> がすべて非負である場合はポジノミアル計画問題(posynomial programming problem)と呼ばれ, 凸計画問題に帰着できる.