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

変分不等式問題

2007-07-13T18:26:11Z

222.225.128.209:

【へんぶんふとうしきもんだい (variational inequality problem)】

閉凸集合<math>S\subseteq {\mathbf R}^n\,</math>, <math>{\mathbf R}^n\,</math>から<math>{\mathbf R}^n\,</math>へのベクトル値関数<math>F(x)=(F_1(x),\dots,F_n(x))\,</math>が与えられているとき, 不等式<br><br><center>

<math>
\langle F(x), y-x \rangle \geq 0,\;\;\;\forall y\in S
\,</math>
</center><br>

を満たす点<math>x\in S\,</math>を求める問題. 特に<math>S=\{x\in {\mathbf R}^n\;|\; x_{i}\geq 0 \quad (i=1,\dots,n)\}\,</math>のとき, 相補性問題に帰着される.

変分不等式問題

2007-07-13T18:25:45Z

222.225.128.209:

【へんぶんふとうしきもんだい (variational inequality problem)】

閉凸集合<math>S\subseteq {\mathbf R}^n\,</math>, <math>{\mathbf R}^n\,</math>から<math>{\mathbf R}^n\,</math>へのベクトル値関数<math>F(x)=(F_1(x),\dots,F_n(x))\,</math>が与えられているとき, 不等式<br><br><center>

<math>
\langle F(x), y-x \rangle \geq 0,\;\;\;\forall y\in S
\,</math>
</center><br><br>

を満たす点<math>x\in S\,</math>を求める問題. 特に<math>S=\{x\in {\mathbf R}^n\;|\; x_{i}\geq 0 \quad (i=1,\dots,n)\}\,</math>のとき, 相補性問題に帰着される.

変分不等式問題

2007-07-13T18:25:11Z

222.225.128.209:

【へんぶんふとうしきもんだい (variational inequality problem)】

閉凸集合<math>S\subseteq {\mathbf R}^n\,</math>, <math>{\mathbf R}^n\,</math>から<math>{\mathbf R}^n\,</math>へのベクトル値関数<math>F(x)=(F_1(x),\dots,F_n(x))\,</math>が与えられているとき, 不等式<br><br><center>

<math>
\langle F(x), y-x \rangle \geq 0,\;\;\;\forall y\in S
\,</math><br>

を満たす点<math>x\in S\,</math>を求める問題. 特に<math>S=\{x\in {\mathbf R}^n\;|\; x_{i}\geq 0 \quad (i=1,\dots,n)\}\,</math>のとき, 相補性問題に帰着される.

ベンダース分解法

2007-07-13T18:12:32Z

222.225.128.209:

【べんだーすぶんかいほう (Benders decomposition method)】

行列 <math>A\,</math>, ベクトル <math>b\,</math> と <math>c\,</math>, スカラー値関数 <math>f\,</math>, ベクトル値関数 <math>g\,</math> と有界閉集合 <math>Y\,</math> により定義される次のような制約付き問題に対する 2 段階の反復法. <br><br>

<table align = center>
<tr><td>min.　</td> <td><math>c^{\top} x + f(y)\,</math></td></tr>
<tr><td>s.t.　</td> <td><math>A x + g(y) \leq b,\,</math></td></tr>
<tr><td></td> <td><math>x \geq 0, \quad y \in Y.\,</math></td></tr>
</table>

変数 <math>y\,</math> を固定した線形計画問題の最適値関数を <math>\phi(y)\,</math> とするとき, 等価な問題<td><td>

<table align = center>
<tr><td>min.　</td> <td><math>\phi(y)\,</math></td></tr>
<tr><td>s.t.　</td> <td><math>y \in Y \cap \{ y\,</math>　|　<math>\exists x \geq 0\,</math>　s.t.<math>A x + g(y) \leq b\}\,</math></td></tr>
</table>
の目的関数と実行可能集合が有限回の反復で確定できることに基づいている.

ヘッセ行列

2007-07-13T17:44:08Z

222.225.128.209:

【へっせぎょうれつ (Hessian matrix)】

多変数スカラ値関数 <math>f(x) = f(x_1,\cdots,x_n)\,</math> を各変数に関して2階偏微分した2階共変テンソルのこと. 通常 <math>H(x)\,</math> と行列で表記する:<br>
\[
H(\fat x) :=
\left[
\begin{array}{ccc}
\frac{\partial^2 f}{\partial x_1\partial x_1}(\fat x)&\cdots&\frac{\partial^2 f}{\partial x_1\partial x_n}(\fat x)\\
\vdots & & \vdots\\
\frac{\partial^2 f}{\partial x_n\partial x_1}(\fat x)&\cdots&\frac{\partial^2 f}{\partial x_n\partial x_n}(\fat x)
\end{array}
\right].
\]

ヘッセ行列

2007-07-13T17:29:56Z

222.225.128.209:

【へっせぎょうれつ (Hessian matrix)】

多変数スカラ値関数 <math>f(\fat x) = f(x_1,\cdots,x_n)\,</math> を各変数に関して2階偏微分した2階共変テンソルのこと. 通常 <math>H(\fat x)\,</math> と行列で表記する:<br>
\[
H(\fat x) :=
\left[
\begin{array}{ccc}
\frac{\partial^2 f}{\partial x_1\partial x_1}(\fat x)&\cdots&\frac{\partial^2 f}{\partial x_1\partial x_n}(\fat x)\\
\vdots & & \vdots\\
\frac{\partial^2 f}{\partial x_n\partial x_1}(\fat x)&\cdots&\frac{\partial^2 f}{\partial x_n\partial x_n}(\fat x)
\end{array}
\right].
\]

ページの近似式

2007-07-13T17:26:59Z

222.225.128.209:

【ぺーじのきんじしき (Page's approximation)】

GI/G/<math>s\,</math>待ち行列の平均待ち時間E(<math>W_q^{{GI/G/}s}\,</math>)に対する2モーメント近似式. 到着時間間隔分布, サービス時間分布の変動係数をそれぞれ<math>c_a\,</math>, <math>c_s\,</math>とすると<br><br>
<center><math>
c_a^2 c_s^2E(W_q^{{\mathrm M/M/}s}) + c_a^2(1-c_s^2)E(W_q^{{\mathrm M/D/}s}) + (1-c_a^2)c_s^2E(W_q^{{\mathrm D/M/}s})
\,</math></center><br>

で近似される. ここで, E(<math>W_q^{{\mathrm M/M/}s}\,</math>), E(<math>W_q^{{\mathrm M/D/}s}\,</math>), E(<math>W_q^{{\mathrm D/M/}s}\,</math>)は, 近似対象の<math>{\mathrm GI/G/}s\,</math>待ち行列の到着時間間隔分布またはサービス時間分布を, 指数分布<math>{\mathrm (M)}\,</math>または一定時間分布<math>{\mathrm (D)}\,</math>に置き換えた待ち行列の平均待ち時間を表す.

ベイズ推定

2007-07-13T17:05:43Z

222.225.128.209:

【べいずすいてい (Bayes estimation)】

パラメータ<math>\theta\,</math>そのものやパラメータの関数(信頼度, 平均故障時間間隔など) <math>g(\theta)\,</math>を推定する場合に, <math>\theta\,</math>の事後分布が有する情報を用いて推定を行うことを意味する. なお, <math>g(\theta)\,</math>の事後分布(事前分布を用いることもある)に関する期待値をベイズ推定量と呼ぶ.

ベイズ推定

2007-07-13T17:04:49Z

222.225.128.209:

【べいずすいてい (Bayes estimation)】

パラメータ<math>\theta\,</math>そのものやパラメータの関数(信頼度, 平均故障時間間隔など) <math>g(\theta)\,<math>を推定する場合に, <math>\theta\,</math>の事後分布が有する情報を用いて推定を行うことを意味する. なお, <math>g(\theta)\,</math>の事後分布(事前分布を用いることもある)に関する期待値をベイズ推定量と呼ぶ.

平衡方程式

2007-07-13T16:57:30Z

222.225.128.209:

【へいこうほうていしき (balance equation)】

マルコフ過程において, ある状態から出ていく確率フローとその状態へ入ってくる確率フローが等しいとおくことで得られる方程式. 例えば, 状態空間が <math>{\mathcal S}\,</math> で推移確率行列が <math>P=p_{ij}\,</math> の離散時間マルコフ連鎖では<br><br>

<center><math>
\pi_j (1-p_{jj}) = \sum_{i\in {\mathcal S}-\{j\}} \pi_i, p_{ij}, \quad j \in {\mathcal S}
\,</math></center>

で与えられる.

平均値解析法

2007-07-13T16:46:01Z

222.225.128.209:

【へいきんちかいせきほう (mean value analysis (MVA))】

閉鎖型のジャクソンネットワークなどで平均列長などを系内客数<math>N\,</math>について0から繰り返し計算する方法である. 各ノードでの規律が先着順の場合のように, 平均待ち時間は到着時点での平均列長から求まることが肝要であり, 到着定理から, これが系内客数が<math>N-1\,</math>のネットワークの平均列長と等しくなることと, リトルの公式を利用する. 規律が先着順でなくても, 平均待ち時間が先着順の場合と一致する規律であればよい.

ヘア投票

2007-07-13T16:43:43Z

222.225.128.209:

【へあとうひょう (Hare vote)】

<math>m\,</math>個の選択対象の中から<math>k\,</math> (<math>1 \leq k \leq m\,</math>) 個を選ぶための投票方法. 各投票者は1から<math>m\,</math>までの順位付けを行う. 一般に<math>k \geq 1\,</math>の場合, <math>v\,</math>人の投票者に対して<math>q = \lfloor v/(k+1) \rfloor+1\,</math> \, (<math>\lfloor x \rfloor\,</math>は<math>x\,</math>を越えない最大整数)以上の第1順位の得票を獲得した選択肢を当選とする. ある選択肢が当選となると, その選択肢への投票者の投票力を削減し, 得票を再配分した上で新たな選択肢を求める操作を当選選択肢の個数が<math>k\,</math>となるまで繰り返す.

分離問題

2007-07-13T16:39:02Z

222.225.128.209:

【ぶんりもんだい (separation problem)】

凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_*\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_* > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.

分布関数

2007-07-13T16:23:27Z

222.225.128.209:

【ぶんぷかんすう (distribution function)】

1次元確率変数 <math>X\,</math> に対して, 関数 <math>F(x)=\mathrm{P}(X \leq x)\,</math> を確率分布関数, あるいは単に分布関数と呼ぶ. 単調非減少な右連続関数で, <math>\lim_{x \to -\infty} F(x)＝0\,</math>, <math>\lim_{x \to \infty} F(x)＝1\,</math> を満たす. 一般に, 連続で微分可能な <math>F_1(x)\,</math>, 可算個の点でのみ飛躍する <math>F_2(x)\,</math> 連続だが至るところ微分不可能な <math>F_3(x)\,</math> を用いて<math>F(x) = F_1(x) + F_2(x) + F_3(x)\,</math> の形に分解できる.

分数計画問題

2007-07-13T16:20:33Z

222.225.128.209:

【ぶんすうけいかくもんだい (fractional programming problem)】

2つの関数の比を目的関数にもつ最適化問題:<br><br>

<table align = center>
<tr><td>
min.　<math>f(x) / g(x) \quad s.t.\,</math>　<math>x \in D.\,</math>
</td></tr>
</table>

実行可能集合<math>D\,</math>上で<math>f\,</math>が非負の凸関数, <math>g\,</math>が正の凹関数ならば<math>f / g\,</math>は準凸関数(quasiconvex function)となり, <math>D\,</math>が凸集合のときには任意の局所的最適解が大域的最適解となる. 特に, <math>f\,</math>, <math>g\,</math>がともにアフィン関数で<math>D\,</math>が凸多面体の場合は線形計画問題に帰着できる.

分数計画問題

2007-07-13T16:19:47Z

222.225.128.209:

【ぶんすうけいかくもんだい (fractional programming problem)】

2つの関数の比を目的関数にもつ最適化問題:<br><br>

<table align = center>
<tr><td>
min.　<math>f(x) / g(x) \quad\,<math> s.t.　<math>x \in D.\,</math>
</td></tr>
</table>

実行可能集合<math>D\,</math>上で<math>f\,</math>が非負の凸関数, <math>g\,</math>が正の凹関数ならば<math>f / g\,</math>は準凸関数(quasiconvex function)となり, <math>D\,</math>が凸集合のときには任意の局所的最適解が大域的最適解となる. 特に, <math>f\,</math>, <math>g\,</math>がともにアフィン関数で<math>D\,</math>が凸多面体の場合は線形計画問題に帰着できる.

分数計画問題

2007-07-13T16:18:47Z

222.225.128.209:

分枝過程

2007-07-13T16:06:21Z

222.225.128.209:

【ぶんしかてい (branching process)】

互いに他の個体とは独立に消滅および増殖をしていく個体集団の個体数の変化をモデル化した確率過程. いくつかのモデルが提案されている. 例えば, 連続時間マルコフ連鎖としての分枝過程は, ある推移率 <math>a > 0\,</math> で各個体が消滅し, その消滅時に新たな個体を確率 <math>p_i, \, i=0, 1, 2, 3, ...\,</math> で<math>i\,</math> 個生成する(増殖する)モデルとなる.

分散

2007-07-13T16:00:22Z

222.225.128.209:

【ぶんさん (variance)】

分布の広がりを表現する値で, 確率変数 <math>X\,</math> の確率分布関数を <math>F(x)\,</math> とすると, <math>X\,</math> の分散は<math>\mathrm{V}(X) =\int (x - \mathrm{E}(X))^2 \mathrm{d}F(x)\,</math> で定義される. 分散の平方根が標準偏差となる.

分割アルゴリズム (スケジューリングの)

2007-07-13T15:58:59Z

222.225.128.209:

【ぶんかつあるごりずむ (decomposition algorithm for scheduling)】

大規模なスケジューリング問題を小さな部分問題に分割し, そのそれぞれを解いて得られる解を総合して原問題の解を求める分割法に基づくアルゴリズムをいう. 例えば, 一機械総納期遅れ最小化問題に対して, 納期順に並べた仕事列の中で最大の処理時間をもつ仕事を<math>k\,</math>番目に処理するとしたとき, 所定の条件を満たすならばその前後の2個の仕事群に分割することができることが知られており, これを用いたダイナミックプログラミングによる効率的解法が報告されている.

プロダクション規則

2007-07-13T15:57:25Z

222.225.128.209:

'''【ぷろだくしょんきそく (production rule)】'''

プロダクションシステムにおいて用いられる知識の表現形式であり, <math>\alpha \to \beta</math>, または if <math>\alpha</math> then <math>\beta</math> の形式で記述される. 矢印の左あるいは if の部分を前件部, 矢印の右あるいは then の部分を後件部という. この形式を用いて, ある事実から導かれる結論に関する知識や, ある条件が成立したときに取るべき行動に関する知識を記述することができる.

プロセッサシェアリング

2007-07-13T15:56:18Z

222.225.128.209:

'''【ぷろせっさしぇありんぐ (processor sharing)】'''

待ち行列モデルにおけるサービス規律の一種. システム内に <math>n</math> 人の客がいるとき, それぞれの客に対して窓口のもつ能力を <math>1/n</math> ずつ割り当て, 同時にサービスを施す. 計算機における CPU の動作モデルとして用いられる.

ブラック・ショールズ式

2007-07-13T15:55:06Z

222.225.128.209:

'''【ぶらっくしょーるずしき (Black-Scholes (B-S) formula)】'''

瞬間的な無リスク金利率を<math>r</math>とし, 株価を幾何ブラウン運動と仮定したコールオプションの評価モデルをブラック・ショールズモデルという. 行使価格が<math>K</math>, 満期が<math>T</math>のコールオプションの時刻0での価格<math>C</math>は, <math>N(x)</math>を標準正規分布関数とすると, 次式で与えられる. これをブラック・ショールズ式という. <br><br><center>

<math>\begin{array}{l}
C = S_0 N(d_1)-{\mbox{e}}^{-rT}K N(d_2) \\
d_1 = \{\log(S_0/K) + (r+(1/2) \sigma^2)T \} /
(\sigma \sqrt{T}) \\
d_2 = d_1-\sigma \sqrt{T}
\end{array}</math>

</center><br><br>

ブラウン運動

2007-07-13T15:50:38Z

222.225.128.209:

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

次の性質を満たす実数値連続確率過程 <math>\{B(t)\}_{t\ge0}</math>. <br>
(1) 重ならない区間における <math>\{B(t)\}_{t\ge 0}</math> の増分は互いに独立. <br>
(2) <math>B(s+t)-B(s)</math> は平均0, 分散<math>\sigma^2 t</math> の正規分布にしたがう. <br>
(3) <math>B(0)=0</math> かつ <math>B(t)</math> は <math>t=0</math> で連続. <br>
拡散係数 <math>\sigma^2=1</math> のときを標準ブラウン運動, <math>B_d(t) = \mu\,t + B(t)</math> をドリフトをもつブラウン運動と呼び, <math>\mu</math> をドリフト係数と呼ぶ.

不動点アルゴリズム

2007-07-13T15:48:05Z

222.225.128.209:

'''【ふどうてんあるごりずむ (fixed point algorithm)】'''

集合<math>C</math>とベクトル値関数<math>F:C\rightarrow C</math>が与えられたとき, 関数<math>F</math>の不動点<br><br><center>

<math>x=F(x)</math>

</center><br><br>
を求めるアルゴリズム. 一般に, 不動点アルゴリズムというときは, 連続変形法あるいは区分的線形近似法を用いてブラウエルの不動点を近似的に求めるアルゴリズムを指すことが多い.

付値マトロイド

2007-07-13T15:45:32Z

222.225.128.209:

'''【ふちまとろいど (valuated matroid)】'''

マトロイド <math>{\mathbf M}</math> の基族 <math>{\mathcal B}</math>上で定義された関数 <math>\omega</math> が以下の<math>\mbox{(V)}</math>を満たすとき, <math>\omega</math> を <math>{\mathbf M}</math> の付値といい, <math>({\mathbf M},\omega)</math> を付値マトロイドという. <br><br><center>

<math>\begin{array}{l}
\mbox{(V)} \quad B, F\in {\mathcal B},
i \in B \backslash F \Rightarrow \exists j \in F \backslash B: \\
\qquad \quad \omega((B\backslash\{i\})\cup\{j\})+\omega((F\cup\{i\})\backslash\{j\}) \\
\qquad \qquad \qquad \geq \omega(B)+\omega(F).
\end{array}</math>
</center><br><br>

マトロイドの付値は, 離散凸解析におけるM凹関数の特殊な場合に相当する.

フォンノイマン・モルゲンシュテルン効用関数

2007-07-13T15:44:09Z

222.225.128.209:

'''【ふぉんのいまんもるげんしゅてるんこうようかんすう (von Neumann-Morgenstern utility function)】'''

戦略の数が有限の戦略形ゲーム <math>G=(N; S_1,\ldots , S_n; u_1,\ldots ,u_n)</math> において, 各プレイヤーの混合戦略の組<math>x=(x_1, \ldots , x_n)</math>に対する各プレイヤー<math>i</math>の利得<math>U_i(x)</math> が期待効用 <math>\textstyle U_i (x) = \sum_{s \in S} u_i(s_1, \ldots , s_n ) x_1(s_1)\cdots x_n(s_n)</math> で与えられるような効用関数<math>U_i</math>をフォンノイマン・モルゲンシュテルン (NM) 効用関数という.フォンノイマンとモルゲンシュテルンが与えたNM効用関数の存在証明は, 社会科学における公理的方法の最初の適用例である.

フェンシェル型双対定理

2007-07-13T15:42:18Z

222.225.128.209:

'''【ふぇんしぇるがたそうついていり (Fenchel-type duality theorem)】'''

フェンシェル(フェンケル)型双対定理とは, 一般に, 「凸関数」と「凹関数」の組<math>(f,g)</math>とそれらの共役関数の組<math>(f^{\bullet}, g^{\circ})</math>の間に成り立つ最大最小定理を意味する. 例えば, <math>\textstyle \langle p, x \rangle = \sum_{i=1}^{n}p_{i}x_{i}</math>として, 以下の形の主張となる. <br><br>

<center>
<table　align = center>
<tr><td>
<math>\mbox{inf} \{ f(x) - g(x) \mid x \in {\mathbf Z} \} ^{n} =</math><br>
::<math>\mbox{sup} \{ g^{\circ}(p) - f^{\bullet}(p) \mid p \in {\mathbf Z}^{n} \} ,</math><br>
<math>f^{\bullet}(p) = \mbox{sup} \{\langle p, x \rangle - f(x) \mid x \in {\mathbf Z}^{n} \} : ( p \in {\mathbf Z}^{n}) ,</math><br>
<math>g^{\circ}(p) = \mbox{inf} \{\langle p, x \rangle - g(x) \mid x \in {\mathbf Z}^{n} \} : ( p \in {\mathbf Z}^{n}) .</math><br>
</td></tr>
</table></center>
<br>

フェンシェルの双対性

2007-07-13T15:39:05Z

222.225.128.209:

'''【ふぇんしぇるのそうついせい (Fenchel duality)】'''

2つの下半連続な真凸関数 <math>k: {\mathbf R}^n\to\bar{{\mathbf R}}</math> と <math>h: {\mathbf R}^m\to\bar{{\mathbf R}}</math>, および <math>A\in{{\mathbf R}^{m\times{n}}}</math>, <math>b\in{{\mathbf R}^m}</math>, <math>c\in{{\mathbf R}^n}</math> に対して, 次の問題のペアに対して成立する双対性のこと. <br><br><center>

<table border = 0>
<tr><td><math>\begin{array}{l}
\displaystyle{ \min_{x\in{{\mathbf R}^n}}\;\{c^{T}x+k(x)+h(b-Ax)\},} \\
\displaystyle{ \max_{y\in{{\mathbf R}^m}}\;\{b^{T}y-h^{*}(y)-k^{*}(A^{T}y-c)\} }
\end{array}</math>
</td></tr>
</table>
</center><br>

ここで, <math>{}^*</math> は共役関数を表す. 通常は, 簡略化して目的関数を凸関数 <math>f_1(x)</math> と凹関数 <math>f_2(x)</math> の差で表した主問題 <math>\min_{x}\{f_1(x)-f_2(x)\}</math> に対して, <math>\max_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}</math> をフェンシェルの双対問題と呼び, その双対性を指す.