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

2レベル計画問題

2007-07-13T04:46:16Z

211.9.146.171:

【にれべるけいかくもんだい (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 align = center>
<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>

2次計画問題

2007-07-13T04:43:47Z

211.9.146.171:

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

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

<table align = center>
<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-13T04:43:00Z

211.9.146.171:

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

重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br>
<table align = center>
<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-13T04:39:54Z

211.9.146.171:

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

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

<table align = center>
<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-13T04:37:04Z

211.9.146.171:

【ふぃぼなっちひーぷ (Fibonacci heap)】

<math>F\,</math> ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O<math>(n)\,</math> となりうるが, <math>n\,</math> 回の挿入, <math>m\,</math> 回の最小値の取り出し, <math>k\,</math> 回の値の減少を行う合計の計算時間が O<math>(n+m+k\log n)\,</math> となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの <math>n\,</math> に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.

ファセット制約

2007-07-13T04:35:29Z

211.9.146.171:

【ふぁせっとせいやく (facet constraint)】

<math>P\,</math> を<math>d\,</math>次元凸多面とする. 任意の <math>x \in P\,</math> に対して <math>a x \leq b\,</math> が成り立つとき, <math> F = P \cap \{x \in {\mathbf R}^d \mid a x = b\} \,</math> を <math>P\,</math>のフェイス (face) という. フェイス <math>F\,</math> の次元が<math>P\,</math>の次元より丁度1小さいとき, <math>F\,</math>をファセット (facet) と呼び, ファセット <math>F\,</math> を定義する不等式を, ファセット制約という.

ファジィAHP

2007-07-13T04:29:54Z

211.9.146.171:

【ふぁじぃえいえいちぴー (fuzzy AHP)】

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

費用対効果分析

2007-07-13T04:28:01Z

211.9.146.171:

【ひようたいこうかぶんせき (cost-effectiveness analysis)】

選定対象とする代替案の費用が,その代替案のもたらす効果ないしは便益に値するか否かを評価する方法である.
<br>
<table>
<tr><td>(1)</td> <td>効果(便益)一定とする場合: 目標ないし目的を達成するのに必要な効果</td></tr>
<tr><td></td> <td>(便益)の水準に対して, 最小の費用で得られる代替案を選択する. </td></tr>
<tr><td>(2)</td> <td>費用一定とする場合: 目標ないし目的を達成するのに必要な費用の水準に</td></tr>
<tr><td></td> <td>対して, 最大の効果(便益)が得られる代替案を選択する.</td></tr>
</table>

被覆 (グラフ理論における)

2007-07-13T04:18:07Z

211.9.146.171:

【ひふく (cover)】

<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,</math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

被覆 (グラフ理論における)

2007-07-13T04:17:38Z

211.9.146.171:

【ひふく (cover)】

<math>G = (V, A)\,</math> を無向グラフとする. 頂点集合 <math>U \subseteq V\,</math> に対して, 任意の枝 <math>a \in A\,<math> の少なくとも一方の端点が <math>U\,</math> に含まれるとき, <math>U\,</math> を <math>G\,</math> の被覆と呼ぶ. 点被覆, 頂点被覆 (node cover, vertex cover) とも呼ばれる. 2部グラフにおいては最大マッチングと最小被覆の要素数が等しい, ということが知られている.

非凸計画問題

2007-07-13T04:16:22Z

211.9.146.171:

'''【ひとつけいかくもんだい (nonconvex programming problem)】'''

最適化問題:<br><center>
<math>\mbox{min.} f(\boldsymbol{x}) \quad \mbox{s.t.} \boldsymbol{x} \in D</math>
</center><br>
で, <math>f\,</math>か<math>D\,</math>の一方, あるいは両方が凸ではない問題. 一部の幾何計画問題や分数計画問題のように任意の局所的最適解が大域的最適解となる例もあるが, 一般には値の異なる複数の局所的最適解が存在するため, 真の最適解を求めるには大域的最適化が必要となる.

非線形相補性問題

2007-07-13T04:15:07Z

211.9.146.171:

【ひせんけいけいかくもんだい (nonlinear programming problem)】

連続変数 <math>x=(x_1,\dots,x_n)\,</math> をもつ数理計画問題<br><br>
<table align = center>
<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> と制約関数 <math>g_i\,</math>, <math>h_j\,</math> のなかに1次関数sでないものが含まれているようなもの.

P-メディアン問題

2007-07-13T04:06:55Z

211.9.146.171:

'''【ぴーめでぃあんもんだい (<math>p</math>-median problem)】'''

点集合と枝集合より構成されるグラフ内の点または枝上, または空間内の任意の点に顧客集合, 施設の配置可能地点が与えられており, さらに選択する施設の個数(<math>p</math>)が与えられたとき, 顧客から最も近い施設への距離の総和を最小化するように施設を配置する問題.

ヒープ

2007-07-13T04:06:16Z

211.9.146.171:

'''【ひーぷ (heap)】'''

値(キー)をもつ要素の集合 <math>A</math> が, 要素の追加, 削除により動的に変化するとする. <math>A</math> に対し, <math>A</math> を保持し, 最小値をもつ要素を見つける・最小値をもつ要素を削除する・新しい要素を追加する, という3種の機能をもつデータ構造をヒープという. 配列を使ったヒープはこれら3種の操作を1回あたり O<math>(\log |A|)</math> 時間で実行し, またメモリ使用量も O<math>(|A|)</math> である. ヒープは計算機に実装しても高速であり, コード化も容易なため, 実用的である.

PTAS

2007-07-13T04:04:38Z

211.9.146.171:

'''【ぴーてぃーえーえす (PTAS (polynomial time approximation scheme))】'''

最小値が<math>f(x^*)</math>であるような関数最小化問題において, 任意の<math>\alpha >0</math>に対して
<br><center>
<math>f(x)\leq (1+\alpha )f(x^*)</math>
</center><br>
となるような解<math>x</math>を(<math>\alpha</math>を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.

P-センター問題

2007-07-13T04:03:08Z

211.9.146.171:

'''【ぴーせんたーもんだい ($p$-center problem)】'''

点集合と枝集合より構成されるグラフ内の点または枝上, または空間内の任意の点に顧客集合, 施設の配置可能地点が与えられており, さらに選択する施設の個数(<math>p</math>)が与えられたとき, 顧客から最も近い施設への距離の最大値を最小化するように施設を配置する問題.

反復最適化

2007-07-13T04:01:54Z

211.9.146.171:

'''【はんぷくさいてきか (iterative optimization)】'''

多変数関数の同時最適化を1変数の最適化の反復で行なう立場は, 同じ多変数関数の重積分を累次積分で行なう立場と類似性があり, ともに再帰式(漸化式)が問題になる. 離散変数の場合も含め, 次の図式で示すことができる.
<br><br><center>
<table align = center>
<tr><td>連続変数の最適化</td><td><math>\Longleftrightarrow \,</math></td><td>多重積分</td><td></td></tr>
<tr><td><math>\Downarrow\,</math></td><td></td><td><math>\Downarrow \,</math></td><td>(離散化)</td></tr>
<tr><td>離散変数の最適化</td><td><math>\Longleftrightarrow \,</math></td><td>多重和</td><td></td></tr>
</table>
</center>

半正定値計画緩和

2007-07-13T03:51:23Z

211.9.146.171:

'''【はんせいていちけいかくかんわ (semidefinite programming relaxation)】'''

組合せ最適化問題または非凸2次計画問題を半正定値計画で緩和すること.典型的な例としては, 問題 <math>\mathop{\mbox{min.}} x^{\top}Qx\ \mbox{s.t.}\ x \in \{-1, 1\}^n</math>(<math>Q</math> は <math>n\times n</math> 行列)を <math>\mathop{\mbox{min.}}\ \mbox{trace}(QX)\ \mbox{s.t.}\ X=xx^{\top},\ x\in\{-1, 1\}^n</math> と表現し, この制約を <math>X</math> が実対称半正定値の行列で,対角成分が<math>1</math>以下というより緩い制約に置き換える. 置き換えた後の問題は半正定値計画となる.半正定値緩和は理論的にも有力な下界を与えることが知られている.

半正定値計画

2007-07-13T03:50:22Z

211.9.146.171:

'''【はんせいていちけいかく (semidefinite programming)】'''

線形計画を実対称行列の空間に拡張したもの.等質自己双対錐上の線形計画問題の1つでもある.半正定値計画は
<br><br>

<table align = center>
<tr><td><math>\mathop{min._X}\,</math></td> <td>trace<math>(CX)\,</math></td></tr>
<tr><td>s.t.</td> <td>trace<math>(A_i X) = b_i, i=1,\ldots,m,\,</math></td></tr>
<tr><td></td> <td><math>X\succeq0,\,</math></td></tr>
</table>

で表される.ただし, <math>C, A_i\ (i=1, \ldots, m), X</math> は <math>n\times n</math> 実対称行列,<math>\mbox{trace}(\cdot)</math> は行列のトレース,<math>X\succeq0</math> は <math>X</math> が半正定値であることを表す.

パレート支配

2007-07-13T03:35:40Z

211.9.146.171:

'''【ぱれーとしはい (Pareto domination)】'''

2つの利得ベクトル<math>x=(x_1,\ldots,x_n), y=(y_1,\ldots, y_n)</math>について,すべての<math>i = 1,\cdots, n</math>に対して<math>x_i>y_i</math>となるとき, <math>x</math>は<math>y</math>をパレート支配するといい,すべての<math>i</math>について<math>x_i \geq y_i</math>であり,少なくとも1つの<math>i</math>について<math>x_i>y_i</math>となるとき,<math>x</math>は<math>y</math>を弱い意味でパレート支配するという.利得ベクトル<math>x</math>がいかなる<math>y</math>によっても弱い意味でパレート支配されないとき, <math>x</math>はパレート最適であるといい, パレート支配されないとき, 弱パレート最適であるという.