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

2次計画問題

2007-07-12T19:44:48Z

211.9.162.254:

【にじけいかくもんだい (quadratic programming problem)】

連続変数 <math>x=(x_1,\dots,x_n)\,</math> をもつ数理計画問題<br>

<table>
<tr><td>min.　</td> <td><math>f(x)\,</math></td></tr>
<tr><td>s.t.　</td> <td><math>g_i(x) \le 0\,</math>　<math>(i=1,\dots,m)\,</math></td></tr>
<tr><td> </td> <td><math>h_j(x) = 0\,</math>　<math>(j=1,\dots,l)\,</math></td></tr>
</table>
で, 目的関数 <math>f\,</math>が2次関数, 制約関数 <math>g_i\,</math>, <math>h_j\,</math> が1次関数で与えられているもの.

ナップサック問題

2007-07-12T19:39:02Z

211.9.162.254:

【なっぷさっくもんだい (knapsack problem)】

重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br>
<table>
<tr><td>目的関数　</td> <td><math>\sum_{i=1}^{n} c_{i}x_{i} \to \,</math>最大化</td></tr>
<tr><td>制約条件　</td> <td><math>\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,</math>：非負整数</td></tr>
</table>
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.

凸計画問題

2007-07-12T19:31:50Z

211.9.162.254:

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

連続変数 <math>x=(x_1,\dots,x_n)\,</math> をもつ数理計画問題<br><br>

<table>
<tr><td>min.　</td> <td><math>f(x)\,</math></td></tr>
<tr><td>s.t.　</td> <td><math>g_i(x) \le 0\,</math>　<math>(i=1,\dots,k)\,</math></td></tr>
<tr><td> </td> <td><math>h_j(x) = 0\,</math>　<math>(j=1,\dots,l)\,</math></td></tr>
</table>
で, 目的関数 <math>f\,</math> と制約関数 <math>g_i\,</math> がすべて凸で, <math>h_j\,</math> がすべてアフィン関数 (1次関数) であるようなもの.

独立集合族

2007-07-12T19:22:41Z

211.9.162.254:

【どくりつしゅうごうぞく (independent set family)】

有限集合 <math>N\,</math> とその部分集合族 <math>{\mathcal I}\,</math> が以下の (I0)-(I2) を満たすとき, <math>{\mathbf M}=(N,{\mathcal I})\,</math> をマトロイドと呼び, <math>{\mathcal I}\,</math> を <math>{\mathbf M}\,</math> の独立集合族と呼ぶ.<br><br>

<table>
<tr><td>(I0)</td> <td><math>\emptyset\in{\mathcal I}\,</math>.</td></tr>
<tr><td>(I1)</td> <td><math>I\subseteq J\in{\mathcal I}\Rightarrow I\in{\mathcal I}\,</math>.</td></tr>
<tr><td>(I2)</td> <td><math>I,J\in{\mathcal I}\,</math>, <math>|I|<|J|\Rightarrow\exists j\in J\backslash I\,</math>:
<math>I\cup\{j\}\in{\mathcal I}\,</math>.</td></tr>
</table>

デルタマトロイド

2007-07-12T19:17:02Z

211.9.162.254:

【でるたまとろいど (delta-matroid)】

有限集合 <math>N\,</math> において, 部分集合の対称差を取る二項演算を<math>\triangle\,</math> で表す. 部分集合族 <math>{\mathcal F}\,</math> が, 以下の (D0)--(D1) を満たすとき, <math>(N,{\mathcal F})\,</math> をデルタマトロイドという. <br><br>

<table border = 0>
<tr><td><b>(D0)</b></td> <td>　<math>{\mathcal F}\neq\emptyset\,</math>.</td></tr>
<tr><td><b>(D1)</b></td> <td>　<math>F,B\in{\mathcal F}\,</math>,<math>i\in F\triangle B\Rightarrow\exists j\in F\triangle B\,</math>:
<math>F\triangle\{i,j\}\in{\mathcal F}\,</math>.</td></tr>
</table>

デルタマトロイドの実行可能集合族 <math>{\mathcal F}\,</math> 上では, 貪欲アルゴリズムによって線形目的関数の最適化が可能である.

パレート最適解

2007-07-12T19:09:21Z

211.9.162.254:

【ぱれーとさいてきかい (Pareto optimal solution)】

多目的計画において, 複数の目的関数を同時に改善することが不可能な実行可能解. すなわち, 目的関数を<math>f_1, \ldots ,f_p\,</math>, 実行可能集合を<math>X\,</math>とするとき, <br><br><center>

<table border = 0>
<tr><td><math>f_i(x) \leq f_i(x^*)\,</math></td> <td>　<math>\forall i=1, \ldots ,p\,</math></td></tr>
<tr><td><math>f_i(x) < f_i(x^*)\,</math></td> <td>　<math>\exists i \in \{ 1, \ldots ,p \}\,</math></td></tr>
</table>
</center><br>
が成り立つ <math>x \in X\,</math> が存在しないような <math>x^* \in X\,</math> のこと. 非劣解, 有効解などとも呼ばれる. 関連して弱パレート解, 真性パレート解なども定義されている.

ハフ変換

2007-07-12T18:59:07Z

211.9.162.254:

【はふへんかん (Hough transformation)】

ハフ変換は, 2次元の直線を原点からこの直線への垂線の距離$r$と直線と$x$軸がなす角度<math>\theta\,</math>で表して, それを<br><center>

直線 <math>x\sin\theta+y\cos\theta=r\mapsto\,</math> 点<math>(r,\theta)\,</math>

</center><br>
<math>(r\ge0\,</math>, <math>0\le\theta<\pi)\,</math>と変換する. ハフ変換は, 画像からの直線成分やさらには楕円などを抽出することによく用いられる.

ハフ変換

2007-07-12T18:58:31Z

211.9.162.254:

【はふへんかん (Hough transformation)】

ハフ変換は, 2次元の直線を原点からこの直線への垂線の距離$r$と直線と$x$軸がなす角度$\theta$で表して, それを<br><center>

直線 <math>x\sin\theta+y\cos\theta=r\mapsto\,</math> 点<math>(r,\theta)\,</math>

</center><br>
<math>(r\ge0\,</math>, <math>0\le\theta<\pi)\,</math>と変換する. ハフ変換は, 画像からの直線成分やさらには楕円などを抽出することによく用いられる.

ハッシュ表

2007-07-12T18:54:09Z

211.9.162.254:

【はっしゅひょう (hash table)】

値(キー)をもつ<math>n\,</math> 個の要素の集合に対し, 挿入・削除・検索の3つの機能を高速化したデータ構造. 値をハッシュキーと呼ばれるいくつかのキーで分類し, それぞれの要素を連結リストなどにより保持する. 挿入と削除をO<math>(1)\,</math> 時間で行い, 検索は, 最悪の場合はO<math>(n)\,</math> となるが, ハッシュキーを適切に設定すれば平均的に O<math>(1)\,</math> となることが多い. 辞書データの保持に多く使われ, 辞書のデータを頭文字をハッシュキーとして保持する, などの例がある.

八分木

2007-07-12T18:52:59Z

211.9.162.254:

【はちぶんき (octree)】

与えられた3次元空間の点の集合の分割を表現するデータ構造で, 2次元平面における四分木に対応する. 根に全体の3次元空間が対応し, 根の8個の子には<math>x\,</math>軸, <math>y\,</math>軸, <math>z\,</math>軸に垂直な平面でそれぞれ二等分して八等分された部分領域が対応する. さらにそれぞれの子<math>v\,</math>に対応する部分領域を同様に八等分して<math>v\,</math>の8つの子に対応させる. このようにして得られる分割を表現するデータ構造が八分木である.

8の字哨戒

2007-07-12T18:51:51Z

211.9.162.254:

【はちのじしょうかい (crossover barrier patrol, bow-tie type barrier patrol)】

速度<math>u\,</math>の目標物に対して優速な速度<math>v\,</math>の探索者が目標物との会合針路の見越角 <math>\sin^{-1}(u/v)\,</math> をとった針路で目標径路帯を横断して, 通過する目標物を探索するのが8の字哨戒である. この探索法は探索者が目標物に比してかなり優速でなければ実行できない.

破産の問題

2007-07-12T18:50:46Z

211.9.162.254:

【はさんのもんだい (ruin problem)】

初期値<math>s\,</math> (<math>>0\,</math>) から出発したランダムウォークあるいはブラウン運動が, いつかは0以下の値をとる確率や, 初めて0以下の値をとる時点の分布を考える問題.

バケット法

2007-07-12T18:49:46Z

211.9.162.254:

【ばけっとほう (bucket method)】

幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.

バケット

2007-07-12T18:48:12Z

211.9.162.254:

【ばけっと (bucket)】

値(キー)をもつ要素の集合を値によって分類するときに使うデータ構造. 値の種類の数 <math>k\,</math> が小さいときに適している. リスト構造により実現すると, 要素の挿入, 取り出しが O<math>(1)\,</math> 時間で実行できる. また, バケットを使用したバケットソート, ラディックスソートは, <math>k\,</math> が小さい場合に効率が良く, 特に <math>k=\,</math>O<math>(1)\,</math> のときには線形時間となる.

暴露目標探知確率

2007-07-12T18:46:44Z

211.9.162.254:

【ばくろもくひょうたんちかくりつ (exposure detection probability)】

長レンジのセンサーでは1回の有効(探知可能)な遭遇径路が長いので, 目標物・探索者の変針変速やセンサーの寿命切れ, 探索条件の時間変化等のために直線相対径路を仮定した横距離曲線は適用できない. その場合に目標物の1回の暴露状態(目標条件やその継続時間, 針路・速度等)を定義し, 相対距離 <math>r\,</math> の点で目標物が暴露状態をとるときの条件付き目標探知確率 P<math>(r)\,</math> を暴露目標探知確率という. 有効探索幅は完全定距離法則換算の有効探知距離を用いる.

暴露目標探知確率

2007-07-12T18:46:12Z

211.9.162.254:

【ばくろもくひょうたんちかくりつ (exposure detection probability)】

長レンジのセンサーでは1回の有効(探知可能)な遭遇径路が長いので, 目標物・探索者の変針変速やセンサーの寿命切れ, 探索条件の時間変化等のために直線相対径路を仮定した横距離曲線は適用できない. その場合に目標物の1回の暴露状態(目標条件やその継続時間, 針路・速度等)を定義し, 相対距離 <math>r\,</math> の点で目標物が暴露状態をとるときの条件付き目標探知確率 <math>P(r)\,</math> を暴露目標探知確率という. 有効探索幅は完全定距離法則換算の有効探知距離を用いる.

配分

2007-07-12T18:44:48Z

211.9.162.254:

【はいぶん (imputation)】

提携形ゲーム<math>(N,v)\,</math>において,プレイヤー全員で提携を形成し, 総利得<math>v(N)\,</math>を分配する際に満たすべき最も基本的な条件, 全体合理性(パレート最適性,<math>\sum_{ i \in N }x_i = v(N)\,</math>)と個人合理性(<math>x_i \ge v( \{ i \} ) \;\;\forall i \in N\,</math>)を満たす利得ベクトル<math>x=(x_1, x_2, ..., x_n)\,</math>のこと. 利得ベクトルが全体合理性を満たし, 必ずしも個人合理性を満たさない場合は, 準配分と呼ばれる.

パーフェクトグラフ

2007-07-12T18:42:59Z

211.9.162.254:

【ぱーふぇくとぐらふ (perfect graph)】

グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ <math>G\,</math> のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, <math>G\,</math> をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている.

バークの定理

2007-07-12T18:42:09Z

211.9.162.254:

【ばーくのていり (Burke's theorem)】

安定なM/M/<math>c\,</math>待ち行列システムの定常状態退去過程はサービス率に依存することなく, 到着率と同じパラメータを有するポアソン過程となるという定理. バークはさらに, 窓口が1つで指数分布にしたがうサービスを行うノードからなる直列型ネットワークにポアソン到着があるとき, 到着時点に関して定常な分布のもとでは1人の客の各窓口での滞在時間は互いに独立であることも示している.

VaR

2007-07-12T18:41:21Z

211.9.162.254:

【ばー (VaR (value at risk))】

ポートフォリオの価値を<math>X\,</math>, その分布関数を<math>F_X(\cdot)\,</math>とするとき, <math>\inf\{x\mid F_X(x)\ge\alpha\}\,</math>を満たす<math>x\,</math>が, 信頼水準<math>1 - \alpha\,</math>におけるこのポートフォリオのVaRである. これは, <math>\alpha\,</math>の確率でこのポートフォリオの価値がVaRの値を下回るということである.

ネットワーク信頼性

2007-07-12T18:40:03Z

211.9.162.254:

【ねっとわーくしんらいせい (network reliability)】

ネットワーク信頼性の尺度としては, 特定の2端局間(節点)が通信できる確率である2端局信頼度, あらゆる2端局間が通信できる確率である全端局信頼度, 端局の部分集合 <math>K\,</math>の中のあらゆる2端局間が通信できる確率である <math>K\,</math> 端局信頼度, などがある. 回線枝の故障確率が与えられたとき, 各信頼性尺度を評価する問題はいずれも NP 完全問題となるが, 効率的に評価する多くの方法が与えられている.

ネットワーク構造 (ANPの)

2007-07-12T18:39:16Z

211.9.162.254:

【ねっとわーくこうぞう (network structure)】

ANPにおいて対象<math>i\,</math>が<math>j\,</math>を評価するとき(つまり超行列の<math>(i,j)\,</math>要素が非ゼロのとき)そしてそのときに限り, 点<math>i\,</math>から点<math>j\,</math>への矢線をもつ有向グラフが得られるが, これをこのANPのネットワーク構造と呼ぶ. このグラフ構造の特徴, 例えば強連結とかサイクルの長さの最大公約数の値とかの特徴が超行列の行列としての性質に密接に関連していて, それがANPの解析を特徴づける.

任意抽出定理

2007-07-12T18:37:58Z

211.9.162.254:

【にんいちゅうしゅつていり (optional sampling theorem)】

<math>(\Omega, {\mathcal F}, P)\,</math>を確率空間, <math>\{ {\mathcal F}_t \}\,</math>を<math>\mathcal F\,</math>の増大する部分<math>\sigma\,</math>--集合体族とし, <math>\{ X_t \}\,</math>を<math>\{ {\mathcal F}_t \}\,</math>に適合したマルチンゲールとする. このとき, <math>\tau, \sigma\,</math>が有界な停止時で, 確率1で<math>\sigma \leq \tau\,</math>を満たすならば, <br><br><center>
<math>
E(X_\tau | {\mathcal F}_{\sigma}) = X_{\sigma}
\,</math></center><br>
が成立する. これを, 任意抽出定理と呼ぶ.

2レベル計画問題

2007-07-12T18:33:38Z

211.9.162.254:

【にれべるけいかくもんだい (bilevel programming problem)】

与えられたパラメータ<math>y=(y_1,\dots,y_m)\,</math>に対して, 変数<math>x=(x_1,\dots,x_n)\,</math> をもつ数理計画問題<math>\min_{x}\{\theta(x,y)\;|\;x \in \Omega(y)\}\,</math>の解集合を<math>S(y)\,</math>とするとき, 変数 <math>x=(x_1,\dots,x_n)\,</math>と<math>y=(y_1,\dots,y_m)\,</math>をもつ次の数理計画問題を2レベル計画問題という.

<table border = 0>
<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)\,</math>, <math>(x,y) \in X \subseteq {\mathbf R}^{n+m}\,</math></td></tr>
</table>

入力率

2007-07-12T18:22:02Z

211.9.162.254:

【にゅうりょくりつ (input rate)】

連続時間の流体近似モデルにおいて, 時刻<math>0\,</math>から<math>t\,</math>までの入力の累積を<math>A_t\,</math>としたとき, <math>A_t\,</math>がある確率過程<math>X_t\,</math>の時間積分<math>\int_{0}^t X_s\mbox{d}s\,</math>で表されるとき, <math>X_s\,</math>を時刻<math>s\,</math>における入力率と呼ぶ. 穴あきバケツモデルでは, 注ぎ込まれる単位時間当りの入力量のこと.

入力密度

2007-07-12T18:20:32Z

211.9.162.254:

【にゅうりょくみつど (traffic intensity)】

待ち行列モデルにおいて, 単位時間当たりにシステムに到着する仕事量の平均, すなわち, システムへのサービス要求量の平均. 例えば, 到着率が<math>\lambda\,</math>で, 個々の客の仕事量の平均が<math>\overline{S}\,</math>ならば, <math>\lambda \overline{S}\,</math>が入力密度である. また, 客が<math>1,2,\ldots,I\,</math>のクラスに分かれていて, クラス<math>i\,</math>の客の到着率が<math>\lambda_i\,</math>で, クラス<math>i\,</math>の個々の客の仕事量の平均が<math>\overline{S}_i\,</math>ならば, <math>\lambda_1 \overline{S}_1 + \lambda_2 \overline{S}_2 + \cdots + \lambda_I \overline{S}_I\,</math>が入力密度である. 標準的な待ち行列モデルでは, 入力密度を窓口数で割ると利用率が得られる.

ニュートン法

2007-07-12T18:17:38Z

211.9.162.254:

【にゅーとんほう (Newton's method)】

制約なし最適化問題 min <math>f(x)\,</math>(ただし <math>\ f:{\mathbf R}^n\to {\mathbf R}\,</math>)を解くための勾配法の1つである. 連立1次方程式 <math>\nabla^2f(x_k)d_k=-\nabla f(x_k)\,</math> の解 <math>d_k\,</math> を探索方向に選び, <math>x_{k+1} := x_k +d_k\,</math> によって近似解の点列 <math>\{x_k\}\,</math> を生成する. この解法は, 解の十分近くから出発すれば2次収束する.

2部グラフ

2007-07-12T18:16:15Z

211.9.162.254:

【にぶぐらふ (bipartite graph)】

グラフ<math>G\,</math>の点集合<math>V\,</math>のある2分割<math>\{U,W\}\,</math>が存在して, 各枝が<math>U\,</math>の点と<math>W\,</math>の点を結ぶとき, このグラフ<math>G\,</math>を2部グラフという. <math>U\,</math>と<math>W\,</math>の点の数がそれぞれ<math>m\,</math>と<math>n\,</math>であって, <math>U\,</math>の各点と<math>W\,</math>の各点を結ぶ枝が丁度1本存在するとき, この2部グラフを完全2部グラフといい, <math>{\rm K}_{m,n}\,</math>のように表す.

2部グラフ

2007-07-12T18:15:27Z

211.9.162.254:

【にぶぐらふ (bipartite graph)】

グラフ<math>G\,<math>の点集合<math>V\,</math>のある2分割<math>\{U,W\}\,</math>が存在して, 各枝が<math>U\,</math>の点と<math>W\,</math>の点を結ぶとき, このグラフ<math>G\,</math>を2部グラフという. <math>U\,</math>と<math>W\,</math>の点の数がそれぞれ<math>m\,</math>と<math>n\,</math>であって, <math>U\,</math>の各点と<math>W\,</math>の各点を結ぶ枝が丁度1本存在するとき, この2部グラフを完全2部グラフといい, <math>{\rm K}_{m,n}\,</math>のように表す.

2のべき乗方策

2007-07-12T18:13:37Z

211.9.162.254:

【にのべきじょうほうさく (power of two policy)】

経済発注量モデルで得られる最小費用を実現する発注間隔は任意の正の実数を許すが, 実務上の時間単位との整合性の関係から, 最適な発注間隔をそのまま用いることは難しい. そこで, 最小発注間隔<math>T_{L}\,</math>が存在し, 発注間隔<math>T\,</math>は<math>T_{L}\,</math>に2のべき乗をかけたものでなければならないとする方策. <math>T=2^{k}T_{L}, k\in\{0, 1, \ldots\}\,</math>と仮定し適切に<math>k\,</math>を選ぶことで, 最適な発注間隔に比べて最大約 6\% の過剰コストで済む.

2人交渉問題

2007-07-12T18:12:01Z

211.9.162.254:

【ににんこうしょうもんだい (two-person bargaining problem)】

協力実現可能集合 <math>S\subseteq R^{2}\,</math>と基準点 <math>d\in S\,</math> の組 <math>(S,d)\,</math> による2人交渉ゲームの記述. 集合 <math>S\,</math> は2人の協力により実現可能な利得ベクトルの集合で,妥結点の候補を示す. 点 <math>d\,</math> は交渉決裂時の2人の利得を表す. 各プレイヤーに基準点以上の利得を与える集合 <math>S\,</math> の部分を交渉領域という.各プレイヤーが交渉領域で獲得できる最大利得の組は理想点という. 所与の交渉問題に妥結点を与える関数を交渉解といい, ナッシュ解, カライ・スモルディンスキー解, 均等解等がある.

2次割当問題

2007-07-12T18:10:54Z

211.9.162.254:

【にじわりあてもんだい (quadratic assignment problem (QAP))】

目的関数が2次式となる割当問題のこと. 設置予定の工場<math>P_1, \ldots, P_n\,</math>とその場所候補<math>L_1, \ldots, L_n\,</math>が与えられており, 工場<math>P_i\,</math>, <math>P_k\,</math>間の輸送量が<math>q_{ik}\,</math>, 場所<math>L_j\,</math>, <math>L_{\ell}\,</math>間の距離が<math>d_{j \ell}\,</math>とするとき, 輸送の量と距離の積の総和を最小化する問題は, <math>P_i\,</math> を <math>L_j\,</math> に設置する際に1となる0-1変数 <math>x_{ij}\,</math> を導入すると, 割当問題の制約に対して目的関数は2次式<math>\sum_{i,j,k,\ell = 1}^n q_{ik} d_{j \ell} x_{ij} x_{k \ell}\,</math>となる. 巡回セールスマン問題や施設配置問題などの多くのNP困難な問題が, 2次割当問題に帰着できる.

二者択一定理

2007-07-12T18:07:02Z

211.9.162.254:

【にしゃたくいつていり (theorem of alternatives)】

一対の方程式・不等式系に対して, そのどちらかは必ず成立し, しかも両方が成立することはないことを主張する定理. 代表的なものに, 与えられた行列 <math>A\,</math> とベクトル <math>b\,</math> によって定義される不等式系の対 <b>(I)</b> <math>Ax \le 0, \ b^T x > 0\,</math> と <b>(II)</b> <math>A^T y = b, \ y \ge 0\,</math> に対するファーカスの定理がある.

二者択一定理

2007-07-12T18:01:26Z

211.9.162.254:

【にしゃたくいつていり (theorem of alternatives)】

一対の方程式・不等式系に対して, そのどちらかは必ず成立し, しかも両方が成立することはないことを主張する定理. 代表的なものに, 与えられた行列 <math>A\,</math> とベクトル <math>b\,</math> によって定義される不等式系の対 (I) <math>Ax \le 0, \ b^T x > 0\,</math> と (II) <math>A^T y = b, \ y \ge 0\,</math> に対するファーカスの定理がある.

2次錐計画

2007-07-12T17:59:38Z

211.9.162.254:

【にじすいけいかく (second-order cone programming)】

等質自己双対錐上の線形計画問題の1つ. <math>n+1\,</math> 次元空間の2次錐は<br><center>
<math>
K(n+1)=\left\{ x \in {\mathbf R}^{n+1} :
x_0 \geq \sqrt{\sum_{i=1}^n x_i^2} \right\}
\,</math></center><br>
で定義される. 2次錐 <math>K(n+1)\,</math> に対して,<math>-\log(x^2_0 - \sum_{i=1}^n x_i^2)\,</math>が<math>2\,</math>--自己整合障壁関数になることが知られている.2次錐計画は<br><center>
<math>
\mathop{min.}_x \sum_{i=1}^N (c^i)^T x^i \,</math> <math>s.t.\,</math><math>
\sum_{i=1}^N A_i x^i = b, x^i \in K(n_i)
\,</math></center><br>
で表される. ここで <math>A_i\in {\mathbf R}^{m\times n_i}\,</math>, <math>b\in {\mathbf R}^m\,</math>,<math>c^i \in {\mathbf R}^{n_i}\,</math>, <math>i=1,\ldots,N\,</math> である.

2次錐計画

2007-07-12T17:58:17Z

211.9.162.254:

【にじすいけいかく (second-order cone programming)】

等質自己双対錐上の線形計画問題の1つ. <math>n+1\,</math> 次元空間の2次錐は<br><center>
<math>
K(n+1)=\left\{ x \in {\mathbf R}^{n+1} :
x_0 \geq \sqrt{\sum_{i=1}^n x_i^2} \right\}
\,</math></center><br>
で定義される. 2次錐 <math>K(n+1)\,</math> に対して,<math>-\log(x^2_0 - \sum_{i=1}^n x_i^2)\,</math>が<math>2\,</math>--自己整合障壁関数になることが知られている.2次錐計画は<br><center>
<math>
\mathop{min.}_x \sum_{i=1}^N (c^i)^T x^i \,</math> <math>s.t.\,</math>
<math>
\sum_{i=1}^N A_i x^i = b, x^i \in K(n_i)
\,</math></center><br>
で表される. ここで <math>A_i\in {\mathbf R}^{m\times n_i}\,</math>, <math>b\in {\mathbf R}^m\,</math>,<math>c^i \in {\mathbf R}^{n_i}\,</math>, <math>i=1,\ldots,N\,</math> である.

2次計画問題

2007-07-12T17:46:43Z

211.9.162.254:

【にじけいかくもんだい (quadratic programming problem)】

連続変数 <math>x=(x_1,\dots,x_n)\,</math> をもつ数理計画問題
\[
\begin{array}{lll}
\min. & f(x) & \\
\mbox{\rm{s.t.}} & g_i(x) \le 0 & (i=1,\dots,m) \\
& h_j(x) = 0 & (j=1,\dots,l)
\end{array}
\]
で, 目的関数 <math>f\,</math>が2次関数, 制約関数 <math>g_i\,</math>, <math>h_j\,</math> が1次関数で与えられているもの.

2項分布

2007-07-12T17:44:58Z

211.9.162.254:

【にこうぶんぷ (binomial distribution)】

自然数 <math>n\,</math> と実数 <math>p \in (0,1)\,</math> をパラメータとして, <math>0,\ldots,n\,</math> の値をとる離散型分布で, 確率関数が<br><br><center>
<math>
f(k) = {n \choose k} p^k (1-p)^{n-k}, \quad k=0,1,\ldots,n
\,</math></center><br>
で与えられる分布. 例えば,表が出る確率が $p$, 裏が出る確率が $1-p$ の貨幣を $n$ 回投げたときに, 表が出る回数がしたがう分布が2項分布となる.

2-3木

2007-07-12T17:42:41Z

211.9.162.254:

【にーさんぎ (2-3 tree)】

平衡二分探索木のデータ構造の一種で, (1) すべての内点は子供を2つか3つもつ, (2) 根から葉へのどのパスの長さも同じ, という2つの条件を満たす. 2-3木ではすべてのデータは葉に記憶される. 頂点数 <math>n\,</math> の2-3木は, 再平衡化により, 要素の挿入・削除・ある要素が含まれるかの確認を O<math>(\log n)\,</math> 時間で行う. また, 再平衡化と似た技法により, 任意の位置での木の分割・2つの木の合併を O<math>(\log n)\,</math> 時間で行う.

ナップサック問題

2007-07-12T17:41:10Z

211.9.162.254:

【なっぷさっくもんだい (knapsack problem)】

重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題.
\begin{center}
\begin{tabular}{ll}
目的関数 & $\displaystyle{\sum_{i=1}^n \: c_ix_i }\; \to \; 最大化 $\\
制約条件 & $\displaystyle{\sum_{i=1}^n \: a_ix_i }\leq b,\; x_i:\;$非負整数
\end{tabular}
\end{center}
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.

ドロネー図

2007-07-12T17:32:21Z

211.9.162.254:

【どろねーず (Delaunay diagram)】

2次元の点<math>p_i=(x_i,y_i)\,</math> <math>(i=1,\cdots,n)\,</math>に対して, 新たに<math>z\,</math>軸を考え, 3次元の点<math>(x_i,y_i,x_i^2+y_i^2)\,</math>の3次元の凸包の<math>z\,</math>軸に関する下側境界を<math>(x,y)\,</math>平面に正射影したものを, <math>p_i\,</math> <math>(i=1,\ldots,n)\,</math>のドロネー図という. ドロネー三角形分割ともいわれる. ボロノイ図は, ドロネー図の双対グラフである. ドロネー図は, 各三角形の外接円が他の点を内部に含まない三角形分割であり, 平面で最小角最大, 一般次元でも最大最小包含円最小など最適化基準を満たす.

凸多面体

2007-07-12T17:30:31Z

211.9.162.254:

【とつためんたい (convex polyhedron, convex polytope)】

有限個の閉半空間の共通部分を凸多面体と呼ぶ. すなわち, <math>n\,</math>次元実線形空間<math>{\mathbf R}^n\,</math>内の凸多面体<math>P\,</math>は, 適当な<math>m \times n\,</math>実行列<math>A\,</math>と<math>m\,</math>次元ベクトル<math>b\,</math>を用いて<br><center>
<math>
P = \{ x \in {\mathbf R}^n \mid A x \leq b \}
\,</math><br></center>
と表現できる. 特に有界な凸多面体は, convex polytope と英語では区別して呼ばれ, 有限個の点からなる集合の凸包であり, 逆も成り立つ.

凸錐

2007-07-12T17:25:43Z

211.9.162.254:

【とつすい (convex cone)】

ベクトル空間の部分集合 <math>S\,</math> で次の条件を満たすものを錐という.<br><br><center>
<math>
x \in S, \alpha \ge 0
\Longrightarrow \alpha x \in S
\,</math></center><br>
特に凸集合であるような錐を凸錐という. 錐 <math>S\,</math> に対して<math> S^* := \{ y \, | \, x^{\top} y \le 0, \ \forall \, x \in S \}\,</math>で定義される凸錐 <math>S^*\,</math> を <math>S\,</math> の極錐という. 凸錐および極錐は, 非線形計画問題の最適性条件を特徴付ける際に基本的な役割を果たす.

凸集合

2007-07-12T17:22:25Z

211.9.162.254:

【とつしゅうごう (convex set)】

ベクトル空間の部分集合 <math>S\,</math> で次の条件を満たすもの. <br><br><center>
<math>
x, y \in S, \alpha \in (0,1)
\Longrightarrow \alpha x + (1-\alpha) y \in S
\,</math></center><br>
有限個の半空間の共通部分として表される凸集合を特に凸多面体という. 凸集合や凸多面体は線形計画をはじめ, 数理計画の様々な分野において最も基本的な役割を果たす.

凸集合

2007-07-12T17:21:06Z

211.9.162.254:

【とつしゅうごう (convex set)】

ベクトル空間の部分集合 <math>S\,</math> で次の条件を満たすもの. <br><br>
<math><center>
x, y \in S, \alpha \in (0,1)
\Longrightarrow \alpha x + (1-\alpha) y \in S
\,</center></math><br><br>
有限個の半空間の共通部分として表される凸集合を特に凸多面体という. 凸集合や凸多面体は線形計画をはじめ, 数理計画の様々な分野において最も基本的な役割を果たす.

凸ゲーム

2007-07-12T17:12:43Z

211.9.162.254:

【とつげーむ (convex game)】

提携形ゲーム<math>(N,v)\,</math>において, 任意の<math>i \in N\,</math>,<math>i \in S \subset T \subseteq N\,</math>について,<math>v(S) -v(S \setminus \{ i \} ) \le v(T) -v(T \setminus \{ i \} )\,</math>が成り立つとき, このゲームを凸ゲームと呼ぶ.凸ゲームは提携の規模が大きくなるにつれて, それに対するプレイヤーの貢献度が大きくなるようなゲームである. 凸ゲームにおいては,交渉集合がコアおよび安定集合と一致し, シャープレイ値はコアの重心になる. また, カーネルは仁と一致する.

凸計画問題

2007-07-12T17:09:00Z

211.9.162.254:

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

連続変数 <math>x=(x_1,\dots,x_n)\,</math> をもつ数理計画問題
\[
\begin{array}{lll}
\min. & f(x) & \\
\mbox{\rm{s.t.}} & g_i(x) \le 0 & (i=1,\dots,k) \\
& h_j(x) = 0 & (j=1,\dots,l)
\end{array}
\]
で, 目的関数 <math>f\,</math> と制約関数 <math>g_i\,</math> がすべて凸で, <math>h_j\,</math> がすべてアフィン関数 (1次関数) であるようなもの.

凸関数

2007-07-12T17:05:33Z

211.9.162.254:

【とつかんすう (convex function)】

空間 <math>{\mathbf R}^n\,</math> 上で定義された拡張実数値関数 <math>f : {\mathbf R}^n \to [-\infty,+\infty]\,</math> で, そのエピグラフ<math>\mbox{epi}\, f := \{ (x,\mu) \in {\mathbf R}^{n+1} \, | \,f(x) \le \mu \}\,</math> が凸集合であるようなもの. 特に, <math>f(x) = -\infty\,</math> となる点 <math>x\,</math> が存在せず, さらに恒等的に <math>f(x) \equiv +\infty\,</math> ではないようなものを真凸関数という. 真凸関数は様々の好ましい性質をもち, 最適化問題に現れる最も基本的な関数のクラスを構成する. 凸関数に関しては, 凸解析と呼ばれる美しい理論体系が整備されている.

独立増分過程

2007-07-12T17:02:20Z

211.9.162.254:

【どくりつぞうぶんかてい (process with independent increment)】

重ならない時間区間 <math>(t_{2i-1}, t_{2i}], \; i=1,\ldots,n\,</math> における確率過程 <math>\{ X(t), t \in \mathbf R \}\,</math> の増分 <math>X(t_{2i})-X(t_{2i-1}), \; i=1,\ldots, n\,</math> が互いに独立となる確率過程. 代表的なものに, ブラウン運動やポアソン過程がある.

独立増分過程

2007-07-12T16:59:42Z

211.9.162.254:

【どくりつぞうぶんかてい (process with independent increment)】

重ならない時間区間 <math>(t_{2i-1}, t_{2i}], \; i=1,\ldots,n\,</math> における確率過程 <math>\{ X(t), t \in \mbox{{\mathbf R}} \}\,</math> の増分 <math>X(t_{2i})-X(t_{2i-1}), \; i=1,\ldots, n\,</math> が互いに独立となる確率過程. 代表的なものに, ブラウン運動やポアソン過程がある.