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

線形相補性問題

2007-07-13T17:34:33Z

124.144.188.143:

'''【せんけいそうほせいもんだい (linear complementarity problem)】'''

<math>n\times n \,</math>行列<math>M \,</math>と<math>n \,</math>次元ベクトル<math>q \,</math>が与えられているとき, 任意の<math>i \,</math> (<math>i=1, \dots, n \,</math>)に対して,

<math>
x_i \ge 0, \ (Mx+q)_{i} \ge 0, \ x_i (Mx+q)_{i} = 0
\quad (i=1,\dots,n)
\,</math>

となる点<math>x\in \mathbf{R}^n \,</math>を求める問題. 双行列ゲーム, 2次計画問題などの重要な問題が線形相補性問題に帰着できる.

線形合同法

2007-07-13T17:32:57Z

124.144.188.143:

'''【せんけいごうどうほう (linear congruential method)】'''

一様乱数を作る方法として, 1948年頃にレーマーによって提案されたもの.漸化式

<math>
X_n=aX_{n-1}+c \ \ \ (\mathrm{mod}\ m), \quad n=1, 2, \cdots
\,</math>

を使って, 集合 <math>\{0,1,2,\cdots,m-1\} \,</math>上の乱数 <math>\{X_n\} \,</math>を作る.

線形計画問題

2007-07-13T17:30:19Z

124.144.188.143:

'''【せんけいけいかくもんだい (linear programming problem)】'''

最適化問題(数理計画問題)

<math>
\mbox{max.} f(x) \ \,</math> (あるいは, <math>\min. \ f(x) \,</math>)

<math>
\mbox{s.t.} x = (x_1,x_2,\ldots,x_n) \in F,
\,</math>

において, 目的関数 <math>f \,</math> が線形であり, かつ, 実行可能集合 <math>F \,</math> が線形等式と線形不等式を用いて表現されている問題.この問題への定式化, および, 解法を含めて線形計画と呼ぶ.

線形行列不等式

2007-07-13T17:27:46Z

124.144.188.143:

'''【せんけいぎょうれつふとうしき (linear matrix inequality)】'''

実対称行列 <math>A_0,\ldots,A_m \,</math> が与えられたときに,

<math>
A_0 + \sum_{i=1}^m x_i A_i
\,</math>

が(半)正定値になるようなベクトル <math>x\in \mathbf{R}^m \,</math> を見つける問題のこと.制御理論で現れる.半正定値計画とほぼ同値であり, 内点法を用いて効率よく解を見つけることができる.

漸近解析

2007-07-13T17:26:34Z

124.144.188.143:

'''【ぜんきんかいせき (asymptotic analysis)】'''

システム特性を支配するあるパラメータをある極限値に近づけてそのシステム特性の振舞いを解析すること. 例えば, 待ち行列システムの待ち時間分布の裾<math>\mbox{P}(W>x) \,</math>の解析において, <math>x \,</math>を無限に増加させたときの<math>\mbox{P}(W>x) \,</math>の減衰率を調べることなどをいう.マルコフ過程で記述できない複雑な待ち行列に対して大偏差理論を用いた漸近解析が行われる.

積率母関数

2007-07-13T17:22:24Z

124.144.188.143:

'''【せきりつぼかんすう (moment generating function)】'''

確率分布関数 <math>F(x) \,</math> をもつ分布, または確率変数 <math>X \,</math>, に対して, 実数 <math>\theta \,</math> をパラメータとする関数 <math>\phi(\theta)=\mathrm{E}(\mathrm{e}^{\theta X})=\int \mathrm{e}^{\theta x} \mathrm{d}F(x) \,</math> を積率母関数と呼ぶ. 積率母関数が存在するためには, 任意の次数のモーメントが存在しなければならないが, よく使われるほとんどの分布は積率母関数をもつ. 積率母関数が存在する場合には, <math>\theta \,</math> に形式的に <math>\mbox{i}t \,</math> (<math>\mbox{i} \,</math>は虚数単位)を代入することで特性関数が得られる.

セービング法

2007-07-13T17:20:45Z

124.144.188.143:

'''【せーびんぐほう (saving method)】'''

運搬経路問題に対する古典的な近似解法であるが, 巡回セールスマン問題に対しても適用できる. 前者の場合, 2点 <math>i,j \,</math> 間の距離を <math>d_{ij} \,</math> , デポ(depot)を点 <math>0 \,</math> と記す. 点 <math>0 \,</math> 以外の点のペア <math>i,j \,</math> に対して, セービング値 <math>s_{ij} \,</math> を <math>s_{ij} = d_{i0}+d_{0j}-d_{ij} \,</math> と定義する. すべての点を通過する前に閉路ができたり, 点の次数が <math>2 \,</math> を超えないように, <math>s_{ij} \,</math> の大きい順に枝 <math>(i,j) \,</math> を加えていくことによって運搬経路を構築する.

制約なし最適化

2007-07-13T17:19:06Z

124.144.188.143:

'''【せいやくなしさいてきか (unconstrained optimization)】'''

実数値関数 <math>f:\mathbf{R}^n\to \mathbf{R} \,</math> が与えられたとき, <math>f(x) \,</math> を変数 <math>x\in \mathbf{R}^n \,</math> について最小化もしくは最大化する問題を制約なし最適化問題という. このとき <math>f(x) \,</math> は目的関数と呼ばれる.

制約想定

2007-07-13T17:17:08Z

124.144.188.143:

'''【せいやくそうてい (constraint qualification)】'''

(1) 非線形計画問題の実行可能解 <math>\bar{x} \,</math> について, 実行可能領域 <math>\{x:\, g_j(x)\leq 0\ (j=1,\dots,m),\ \ h_k(x)=0\ (k=1,\dots,\ell)\} \,</math> の, 点 <math>\bar{x} \,</math> における線形化錐 <math>\{y:\,\nabla g_j(\bar{x})y\leq 0\ (j\in I(\bar{x})),\ \nabla h_k(\bar{x})y=0\ (k=1,\dots,\ell)\} \,</math> が, 実行可能領域の十分よい近似になっていることを保証する条件. ただし, <math>I(\bar{x})=\{j:\, g_j(\bar{x})=0 \} \,</math>.

(2) 非線形計画問題に対する最適性必要条件を導く際,
目的関数のラグランジュ乗数がゼロにならないことを保証する条件.

正則三角形分割

2007-07-13T17:13:34Z

124.144.188.143:

'''【せいそくさんかくけいぶんかつ (regular triangulation)】'''

高次元正則三角形分割は, 点集合 <math>S \,</math>に対して新たなもう1次元方向を考え, その方向に各点にそれぞれの高さを与えてもち上げた点集合の凸包の下側境界を, 元の空間に正射影することにより得られるものである. 2次元でも正則でない三角形分割は存在する. ドロネー三角形分割は正則であり, 正則三角形分割は高次元の場合も任意の2つの正則三角形分割は一般化対角変形で変換することができ, 正則三角形分割全体は2次凸多面体という凸多面体構造をもつ.

整数多面体

2007-07-13T17:12:46Z

124.144.188.143:

'''【せいすうためんたい (integral polyhedron)】'''

凸多面体 <math>P=\{\mathbf{x} \mid \mathbf{A} \mathbf{x} \leq b\} \,</math> において, <math>P_I \,</math> を, 凸多面体 <math>P \,</math> に含まれる整数ベクトルの集合の凸包とする. このとき <math> P = P_I \,</math> となる <math>P \,</math> を整数多面体という. 任意のコストベクトル <math>\mathbf{c} \,</math> に対する整数多面体 <math>P = P_I \,</math> 上での整数計画問題は<math>P \,</math> 上での線形計画問題として解くことができる.

整数計画アプローチ (スケジューリング問題の)

2007-07-13T17:10:33Z

124.144.188.143:

'''【せいすうけいかくあぷろーち (integer programming approach to scheduling problem)】'''

スケジューリング問題は0-1変数を用いて整数計画問題として定式化することができる. 1つの仕事あるいは作業はある時点においてある1台の機械でしか処理できず, また機械はある時点において1つの作業しか処理できないことをはじめとするスケジュールに対する各種の条件を, 0-1変数を含む数式によって表現する. 例えば, 一機械問題の場合には, 仕事<math>i \,</math>を<math>j \,</math>番目に処理するとき<math>x_{ij}=1 \,</math>とし, その他の場合を<math>0 \,</math>とする.

先行関係

2007-07-13T16:51:51Z

124.144.188.143:

'''【せんこうかんけい (preference relation)】'''

結果の集合<math>X \,</math>の中から2つの結果<math>x,y\in X \,</math>を取り出して, 意思決定者が<math>x \,</math>は<math>y \,</math>と同程度にまたはそれ以上に好ましいと考えているとき<math>x\displaystyle{\mathop{\succ}_\sim} y \,</math>と書くことにする. <math>x\displaystyle{\mathop{\succ}_\sim} y \,</math>を満たすすべての組<math>(x,y) \,</math>の集合<math>R \,</math>を考えると, <math>R \,</math>は意思決定者の<math>X \,</math>上の好みを表す関係なので選好関係と呼ばれる. <math>R \,</math>は二項関係(binary relation) の一種である. また, 結果の集合<math>X \,</math>が選好関係<math>\displaystyle{\mathop{\succ}_\sim} \,</math>をもつ構造を<math>(X,\displaystyle{\mathop{\succ}_\sim} ) \,</math>と表し, これを<math>X \,</math>上の選好構造と呼ぶ.

全双対整数性

2007-07-13T16:49:44Z

124.144.188.143:

'''【ぜんそうついせいすうせい (totally dual integrality (TDI))】'''

線形不等式システム <math>\mathbf{A} \mathbf{x} \leq \mathbf{b} \,</math> が線形計画問題 <math> \max \{\mathbf{c} \mathbf{x} \mid \mathbf{A} \mathbf{x} \leq \mathbf{b} \} \,</math> が有界であるような任意の整数ベクトル <math>\mathbf{c} \,</math> に対して, その双対問題 <math> \min\{ \mathbf{b} \mathbf{y} \mid \mathbf{y} \mathbf{A} = \mathbf{c}, \mathbf{y} \geq \mathbf{0} \} \,</math>が, 整数の最適解 <math>\mathbf{y}^* \,</math> をもつならば, 全双対整数的 (totally dual integral, TDI) であるという.

全体合理性

2007-07-13T16:45:48Z

124.144.188.143:

'''【ぜんたいごうりせい (total group rationality)】'''

提携形ゲーム<math>(N,v) \,</math>において, 利得ベクトル<math>x=(x_1, x_2, ..., x_n) \,</math>が条件<math>\sum_{ i \in N }x_i = v(N) \,</math>を満たすとき, 全体合理性を満たすといわれる.この条件はプレイヤー全員で提携を形成し, 総利得<math>v(N) \,</math>を分配する際に満たすべき基本的な条件の1つである. 全体合理性を満たす利得ベクトルの集合は実現可能集合<math>\{ x \in \mathbf{R}^n | \sum_{i \in N} x_i \le v(N) \} \,</math>におけるパレート最適な利得ベクトルの集合に一致する.

全体効率性

2007-07-13T16:44:28Z

124.144.188.143:

'''【ぜんたいこうりつせい (overall efficiency)】'''

着目DMU <math>J \,</math>のBCCモデルにおける効率値(BCC)はCCRモデルの効率値(CCR)以上になる. そこで<math>\theta_J \,</math> (CCR)を全体効率性, <math>\theta_J \,</math> (BCC)を技術効率性と考え, その差異は規模の効率性によるものと考え, <math>\{ \,</math>全体効率性<math>\theta_J \,</math> (CCR) <math>= \,</math> 技術効率性<math>\theta_J \,</math> (BCC) <math>\times \,</math>規模の効率性 <math>\} \,</math>と考えることができる. また, コスト効率性を全体効率性<math>\theta_J \,</math> (cost)と考えると, 全体技術効率性<math>\theta_J \,</math> (CCR)との差異をマネジメント効率性と捉えることもできる.

全ユニモジュラ性

2007-07-13T16:41:54Z

124.144.188.143:

'''【ぜんゆにもじゅらせい (total unimodularity)】'''

行列 <math>\mathbf{A} \,</math> が全ユニモジュラ行列 (totally unimodular matrix) であるとは, <math>\mathbf{A} \,</math> の任意の部分正方行列の行列式が <math>1,-1 \,</math>, または <math>0 \,</math> となることである. 全ユニモジュラ性とは, 全ユニモジュラ行列により決定される凸多面体を扱った数学的な特徴づけのことをいう. 全ユニモジュラ行列の例として, 2部グラフの接続行列, 有効グラフの接続行列などがある.

相関係数

2007-07-13T16:39:36Z

124.144.188.143:

'''【そうかんけいすう (correlation coefficient)】'''

解析の対象に対して測定される2つの変数(特性)の線形関係の程度を示す指標. 2変数の共分散を2変数の標準偏差の積で除した値を相関係数といい, <math>-1 \,</math>から<math>+1 \,</math>までの値をとる. 2変数の値を平面にプロットするとき, 1つの直線の近くに分布していると, <math>1 \,</math>または<math>-1 \,</math>に近い値をとり, その符号は, 直線の傾きの符号と一致する. なお, 2次元正規分布の特性値の1つとしての相関係数は, 分布の共分散を分布の2つの標準偏差の積で除した値である.

双行列ゲーム

2007-07-13T16:38:11Z

124.144.188.143:

'''【そうぎょうれつげーむ (bimatrix game)】'''

<math>i \,</math>行<math>j \,</math>列に要素<math>(a_{ij},b_{ij}) \,</math>をもつ<math>m \,</math>行<math>n \,</math>列の双行列で2人戦略形ゲームを表したもの. ただし<math>a_{ij},\ b_{ij} \,</math>はプレイヤー1が純戦略<math>i \,</math>, プレイヤー2が純戦略<math>j \,</math>をとったときのプレイヤー1, 2の利得である.<math>a_{ij}+b_{ij}=0 \,</math>となる2人ゼロ和ゲームは, 一方のプレイヤーの利得,例えば<math>a_{ij} \,</math>を記述しておけば十分なので, 行列ゲームと呼ばれる.

双線形行列不等式

2007-07-13T16:36:52Z

124.144.188.143:

'''【そうせんけいぎょうれつふとうしき (bilinear matrix inequality)】'''

実対称行列 <math>A_{ij},i=0,\ldots,m,j=0,\ldots,n \,</math> が与えられたときに,

<math>
\sum_{i=1}^m\sum_{j=1}^n x_i y_i A_{ij} + \sum_{i=1}^m x_i A_{i0}
+ \sum_{j=1}^n y_i A_{0i} + A_{00}
\,</math>

が(半)正定値になるようなベクトル <math>(x,y)\in \mathbf{R}^{n+m} \,</math> を見つける問題のこと.制御理論で現れる.一般に凸計画問題ではなく, NP困難であることが知られている.

双線形計画問題

2007-07-13T16:35:38Z

124.144.188.143:

'''【そうせんけいけいかくもんだい (bilinear programming problem)】'''

2種類の変数<math>\mathbf{x} = (x_1, \ldots, x_n) \,</math>,<math>\mathbf{y} = (y_1, \ldots, y_m) \,</math>の一方の値を固定すると線形計画問題になる2次の最適化問題:

<math>
\begin{array}{lll}
\mbox{min.} & \mathbf{c}^{\top} \mathbf{x} - \mathbf{x}^{\top} \mathbf{Q} \mathbf{y} + \mathbf{d}^{\top} \mathbf{y} \\
\mbox{s.t.} & \mathbf{x} \in X, & \mathbf{y} \in Y.
\end{array}
\,</math>

ただし, <math>\mathbf{c} \in \mathbf{R}^n \,</math>, <math>\mathbf{d} \in \mathbf{R}^m \,</math>, <math>Q \in \mathbf{R}^{n \times m} \,</math>で<math>X \subset \mathbf{R}^n \,</math>, <math>Y \subset \mathbf{R}^m \,</math>は凸多面体. 2次の凹最小化問題は, 行列<math>\mathbf{Q} \,</math>が正方, 対称正定値な双線形計画問題に等価である.

双対問題 (線形計画の)

2007-07-13T16:30:49Z

124.144.188.143:

'''【そうついもんだい (dual problem)】'''

線形計画問題

<math>
\begin{array}{lll}
\mbox{max.} & \displaystyle \sum_{j=1}^{n}c_jx_j & \\
\mbox{s.t.} & \displaystyle \sum_{j=1}^na_{ij}x_j\leq b_i & (i=1,2,\ldots,m), \\
& x_j \geq 0\ & (j=1,2,\ldots,n)
\end{array}
\,</math>

に対して, 以下の線形計画問題を双対問題と呼ぶ. 元の問題を主問題と呼ぶ.

<math>
\begin{array}{lllll}
\mbox{min.} & \displaystyle \sum_{i=1}^{m}b_i y_i & \\
\mbox{s.t.} & \displaystyle \sum_{i=1}^na_{ij}y_i\geq c_j & (j=1,2,\ldots,n), \\
& y_i \geq 0 & (i=1,2,\ldots,m).
\end{array}
\,</math>

相補性定理

2007-07-13T16:29:31Z

124.144.188.143:

'''【そうほせいていり (complementarity slackness theorem)】'''

線形計画問題

<math>
\begin{array}{llllllll}
\mbox{max.} & \displaystyle \sum_{j=1}^{n}c_jx_j & \\
\mbox{s.t.} & \displaystyle \sum_{j=1}^na_{ij}x_j\leq b_i & (i=1,2,\ldots,m), \\
& x_j \geq 0 & (j=1,2,\ldots,n)
\end{array}
\,</math>

の実行可能解 <math>(x_1,\ldots,x_n) \,</math> と双対問題の実行可能解 <math>(y_1,\ldots,y_m) \,</math>がそれぞれの問題の最適解であるための必要十分条件は,(1) <math>(c_j-\sum_{i=1}^{m}a_{ij}y_i)x_j=0 \ (j=1,2,\ldots,n) \,</math>, かつ(2)<math>(\sum_{j=1}^{n}a_{ij}x_j-b_i)y_i =0 \ (i=1,2,\ldots,m) \,</math> が成り立つことである. この主張を相補性定理と呼ぶ.

相補性問題

2007-07-13T16:28:15Z

124.144.188.143:

'''【そうほせいもんだい (complementarity problem)】'''

変数 <math>x=(x_1,\dots,x_n) \,</math> と同じ次元をもつベクトル値関数 <math>F(x)=(F_1(x),\dots,F_n(x)) \,</math> に対して,

<math>
x_i \ge 0, \ F_i(x) \ge 0, \ x_i F_i(x) = 0
\quad (i=1,\dots,n)
\,</math>

を満たす <math>x \,</math> を求める問題. 特に<math>F_{i} \,</math>がすべて1次関数のとき線形相補性問題, そうでないとき非線形相補性問題と呼ぶ.

ゾーン

2007-07-13T16:26:43Z

124.144.188.143:

'''【ぞーん (zone)】'''

<math>d \,</math>次元の<math>n \,</math>個の超平面のアレンジメントにおいて, 新たに1つ超平面<math>h \,</math>を加え, <math>h \,</math>と交わる各セルのフェイスの集合をゾーンと呼ぶ. ゾーン定理は, アレンジメントの基本定理であり, 種々の応用がある. 代数曲面のアレンジメントにおいても, ほぼ超平面の場合と同じゾーン定理が成立する. そのように一般化した際には, ゾーンは超曲面アレンジメントの1つのセルとみなせる.

ゾーン定理

2007-07-13T16:25:34Z

124.144.188.143:

'''【ぞーんていり (zone theorem)】'''

ゾーン定理とは, 「<math>d \,</math>次元空間内の<math>n \,</math>個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は<math>\mathrm{O}(n^{d-1}) \,</math>である」というもので, アレンジメントの基本定理である. その応用は多く, 例えば <math>d \,</math>次元の<math>n \,</math>超平面のアレンジメントのセルの集合を <math>\mathcal{C} \,</math>, 各セル<math>c\in \mathcal{C} \,</math>のファセットの数を<math>d(c) \,</math>としたとき, <math> \sum_{c\in \mathcal{C}}d(c)^2= \mathrm{O}(n^d) \,</math> が成り立つ. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる.

ソロー条件

2007-07-13T16:22:07Z

124.144.188.143:

'''【そろーじょうけん (Solow's condition)】'''

産業連関表によって計算される生産額が非負であるための, ホーキンス・サイモン条件が成立するための十分条件として次式のソローの条件が知られている.

<math>
\sum_{i=1}^{n}a_{i,j}<1,\ \ j=1,2,...,n
\,</math>

左辺は投入係数の <math>j \,</math>列の和であるからこの式は自動的に成立する. それゆえ, 生産額Xが非負であるという条件は自然に成立している.

大域的最適化

2007-07-13T16:19:56Z

124.144.188.143:

'''【たいいきてきさいてきか (global optimization)】'''

最適化問題:

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

において <math>f \,</math>か <math>D \,</math>の一方, あるいは両方が凸でなければ, 一般に値の異なる複数の局所的最適解が存在する. その中から大域的最適解, つまり

<math>
f(\mathbf{x}^*) \leq f(\mathbf{x}), \quad \mathbf{x} \in D
\,</math>

を満たす実行可能解 <math>\mathbf{x}^* \,</math>を求めることをいう.

大域的最適解

2007-07-13T16:17:35Z

124.144.188.143:

'''【たいいきてきさいてきかい (global optimal solution)】'''

数理計画問題:

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

において, 次の条件を満たす点 <math>x^* \in S \,</math> のこと.

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

通常は単に最適解ということが多いが, 非凸計画問題や組合せ最適化問題において局所的最適解との区別を強調するときしばしば大域的という形容詞を付ける.

大域的収束性

2007-07-13T16:16:19Z

124.144.188.143:

'''【たいいきてきしゅうそくせい (global convergence)】'''

反復法で生成される近似解の点列 <math>\{ x_k\} \,</math> が, 任意の初期点から出発しても, 有限回の反復で解集合に到達するか, もしくは, 無限点列 <math>\{x_k\} \,</math> が解集合に何らかの意味で収束するとき, この反復法は大域的収束性をもつという. この用語に対比するものとして局所的収束性がある. これは, 解の十分近くに初期点を選べば点列が収束することを意味する.

大域平衡方程式

2007-07-13T16:15:28Z

124.144.188.143:

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

確率過程の平衡状態において, 各状態へ入る率と出る率が等しいことを表す方程式. マルコフ過程では, 大域平衡方程式により定常分布が決まる. 例えば, 離散的な状態空間 <math>S \,</math>をもつ連続時間マルコフ連鎖の推移率を <math>q(i,j) \,</math>, 定常状態確率を <math>\pi(i) \,</math>とすると, 大域平衡方程式は,

<math>
\pi(i) \sum_{j \in S-\{i\}} q(i,j) = \sum_{j \in S-\{i\}} \pi(j) \, q(j,i), \ i \in S,
\,</math>

により与えられる.

対数最小二乗法 (AHPの)

2007-07-13T16:13:21Z

124.144.188.143:

'''【たいすうさいしょうじじょうほう (logarithmic least squares method)】'''

AHPにおいて一対比較行列から重要度を算出する方法の1つ. 一対比較のモデルとして, <math>a_{ij} = (w_i / w_j) \varepsilon_{ij} \,</math>を仮定し, 誤差の対数<math>\log \varepsilon_{ij} \,</math>の二乗和を最小化する<math>\{\omega_i \} \,</math>を重要度とする方法である. ここで, 誤差<math>\varepsilon_{ij} \,</math>の分布として互いに独立で平均1, 分散<math>\sigma^2 \,</math>の対数正規分布を仮定すると, 行列<math>\mathbf{A} \,</math>の行の要素の幾何平均は最尤推定量になり, 幾何平均法と同じである.

対数障壁関数

2007-07-13T16:12:19Z

124.144.188.143:

'''【たいすうしょうへきかんすう (log barrier function)】'''

不等式制約条件をもつ制約付き最適化問題<math>\min\ \{f(x)\ | \ g_i(x) \leq 0\ (i=1,...,m) \} \,</math> に対して<math>F_\nu (x) := f(x) - \nu \sum_i \log[ - g_i(x)] \,</math>で定義される関数. 正のパラメータ<math>\nu \,</math>を含み, <math>F_\nu \,</math> の(無制約)最小点の集合は, <math>\nu \,</math>を0に近づけたとき, 適当な条件の下で, 元の制約付き問題の最適解に至る曲線になる. この曲線を中心曲線といい, それをホモトピー法で追跡するのが内点法である.

大数の法則

2007-07-13T16:11:23Z

124.144.188.143:

'''【たいすうのほうそく (law of large numbers)】'''

互いに独立な確率変数列 <math>X_1, X_2, \ldots \,</math> があり, 平均 <math>\mathrm{E}(X_i)= \mu \,</math> は一定で有限とする. <math>X_1, X_2, \ldots \,</math> の算術平均 <math>S_n=(X_1+ \ldots +X_n)/n \,</math> が1点 <math>\mu \,</math> に概収束または確率収束するとき, それぞれ大数の強法則, 大数の弱法則が成立するという. 分布が同一の場合はどちらも成立する.

ダイナマイゼーション

2007-07-13T16:09:54Z

124.144.188.143:

'''【だいなまいぜーしょん (dynamization)】'''

与えられた対象物の集合<math>S \,</math>に対して, 質問<math>Q \,</math>が与えられたとき, <math>Q \,</math>とある種の条件を満たす<math>S \,</math>の要素を列挙する問題は探索問題と呼ばれている. 同一の台集合<math>S \,</math>に対して, 問い合わせが繰り返し行われることも多いので, 台集合に前処理を施して問い合わせに高速に応答できるようにデータ構造で表現する. ここで, 台集合が挿入や削除によって更新される場合には, データ構造の方も動的に変化させなければならない. このための技術をダイナマイゼーションという.

大偏差理論

2007-07-13T16:08:32Z

124.144.188.143:

'''【だいへんさりろん (large deviation theory)】'''

次の性質を満たす可測空間<math>(\mathcal{X}, \mathcal{B}) \,</math>上の確率測度の列<math>\{\mu_n\} \,</math>に関する理論で, 稀な確率事象の漸近解析に使われる. 性質とは, 任意の<math>\Gamma \in \mathcal{B} \,</math>に対して

<math>
\begin{array}{lll}
\limsup_{n\rightarrow \infty} v(n)^{-1}\log \mu_n (\Gamma )&\leq&
-\inf_{x\in \bar{\Gamma}} I(x),\\
\liminf_{n\rightarrow \infty} v(n)^{-1}\log \mu_n (\Gamma )&\geq&
-\inf_{x\in \Gamma^{o}} I(x)
\end{array}
\,</math>

である. ここで, <math>\{v(n)\} \,</math>は無限大に発散する増加数列, <math>\bar{\Gamma} \,</math>は<math>\Gamma \,</math>の閉包, <math>\Gamma^{o} \,</math>は<math>\Gamma \,</math>の開核である. <math>I(x) \,</math>はレート関数(rate function)と呼ばれる.

楕円体

2007-07-13T16:05:27Z

124.144.188.143:

'''【だえんたい (ellipsoid)】'''

楕円体は, 2次元空間における楕円の概念を, <math>n \,</math> 次元空間において一般化したものである. 1つのベクトル<math>x_* \in \mathbf{R}^n \,</math> および <math>n \times n \,</math> 正定値対称行列 <math>B \,</math> を用いて,

<math>
E = \{x \in \mathbf{R}^n \mid
(x - x_*)^{\top} B^{-1}(x - x_*) \leq 1\}
\,</math>

と表される集合が楕円体である. ここで, <math>x_* \,</math> は楕円体 <math>E \,</math> の中心と呼ばれる. <math>B = J J^{\top} \,</math> と分解されるとき,<math>E = \{x_* + J y \mid \|y\| \leq 1\} \,</math>と表される. したがって, 楕円体 <math>E \,</math> は単位球をアフィン変換 <math>y \mapsto x_* + J y \,</math>により写した像である.

多項式時間アルゴリズム

2007-07-13T16:02:36Z

124.144.188.143:

'''【たこうしきじかんあるごりずむ (polynomial time algorithm)】'''

どんな入力に対しても, 入力の長さの多項式時間で解を出力するアルゴリズム. 例えば入力の長さ<math>n \,</math>に対して, <math>n^2 \,</math>や<math>n^{100} \,</math>は多項式であるが, <math>2^n \,</math>や<math>n^{\log n} \,</math>や<math>\log n^{\log n} \,</math>は多項式ではない. ある問題に対して多項式時間アルゴリズムが存在しないことが示せれば, その問題は「手に負えない」といってよい. しかし入力の長さの1000乗に比例する時間で問題を解く多項式時間アルゴリズムが存在しても, 現実には使い物にならないであろう.

多次元正規分布

2007-07-13T16:00:44Z

124.144.188.143:

'''【たじげんせいきぶんぷ (multivariate normal distribution)】'''

代表的な多次元分布. 平均ベクトルを <math>\mathbf{\mu} =(\mathrm{E}(X_1), \ldots, \mathrm{E}(X_n)) \,</math>, (分散)共分散行列を <math>\mathbf{\Sigma}=(\mathrm{Cov}(X_i,X_j))_{i,j=1,\ldots,n} \,</math> とすると, <math>n \,</math> 次の多次元正規分布の確率密度関数は <math>\mathbf{x}=(x_1,\cdots,x_n) \,</math> として

<math>
f(\mathbf{x})=
\displaystyle{\frac{1}{(2\pi)^{n/2} \sqrt{|\mathbf{\Sigma}|}} \mathrm{exp}
\left[ - \frac{1}{2}
(\mathbf{x}-\mathbf{\mu}) \mathbf{\Sigma}^{-1}
(\mathbf{x}-\mathbf{\mu})^{\top} \right] }
\,</math>

で与えられる. ただし, <math>\mathbf{x}^{\top} \,</math> はベクトル <math>\mathbf{x} \,</math> の転置, <math>|\mathbf{\Sigma}| \,</math> は行列式を表す. 統計学における多変量解析などで中心的な役割を果たす.

多次元分布

2007-07-13T15:56:01Z

124.144.188.143:

'''【たじげんぶんぷ (multivariate distribution)】'''

<math>n \,</math> 個の実数値確率変数 <math>X_1, \ldots, X_n \,</math> を確率ベクトル<math>\mathbf{X}=( X_1, \ldots, X_n) \,</math> と考えたときの <math>\mathbf{R}^n \,</math> 上の分布. <math>F(x_1,\ldots,x_n)=\mathrm{P}(X_1 \leq x_1,\ldots, X_n \leq x_n) \,</math> を多次元確率分布関数と呼ぶ. この多次元分布を <math>X_1, \ldots, X_n \,</math> の同時分布とも呼ぶ. これに対して <math>X_i \,</math> の分布 <math>F_i(x) = P(X_i \leq x) \,</math> を<math>X_i \,</math> の周辺分布と呼ぶ.

多重積分の解法

2007-07-13T15:54:05Z

124.144.188.143:

'''【たじゅうせきぶんのかいほう (solution of multiple integral)】'''

多重積分を累次(繰り返し)積分で解くこと:

<math>
\displaystyle{ \int_Df(x)\mbox{d}x = }
\displaystyle{\int_{D_{1}} \int_{D_{2}(x_1)} \cdots
\int_{D_{N}(x_{1}, x_{2}, \cdots , x_{N-1})} }
\displaystyle{f(x_{1}, x_{2}, \cdots , x_{N})
\mbox{d}x_N \cdots \mbox{d}x_2\mbox{d}x_1 }
\,</math>

は <math> f = f_N \,</math> から始まる後向きの再帰(漸化)式

<math>
\displaystyle{ f_{n-1}(x_{1}, \cdots , x_{n-1}) = }
\displaystyle{\int_{D_{n}(x_{1}, \cdots , x_{n-1})}
f_n(x_{1}, \cdots , x_{n})\mbox{d}x_n, \ 1 \le n \le N}
\,</math>

を解くことに他ならない.

多重和の解法

2007-07-13T15:52:39Z

124.144.188.143:

'''【たじゅうわのかいほう (solution of multiple summation)】'''

一般に, 多重和問題

<math>
\displaystyle{\sum \{g(x_{1}, x_{2}, x_{3}, \ldots , x_{N+1})}
\displaystyle{\mid (x_{2}, x_{3}, \ldots , x_{N+1}) \in X^{N} \} }
\,</math>

は次の後向き再帰式で解ける:

<math>
\begin{array}{l}
\displaystyle{w_{N+1}(x^{N+1}) = g(x^{N+1}), \quad x^{N+1} \in X^{N+1} } \\
\displaystyle{ w_{n}(x^{n}) = \sum_{y \in X}w_{n+1}(x^{n}, y), }
\ \ \ \ \displaystyle{x^{n} \in X^{n},~ 1 \le n \le N. }
\end{array}
\,</math>

ただし, <math> x^{n} = (x_{1}, x_{2}, \ldots , x_{n}). \,</math>

多数決投票

2007-07-13T15:51:29Z

124.144.188.143:

'''【たすうけつとうひょう (majority voting)】'''

<math>m \,</math>個の選択対象の中から<math>k \,</math>(<math>1 \leq k \leq m \,</math>)個を選ぶための投票において, 1つの選択肢のみ(<math>k=1 \,</math>)を当選とする選挙の場合, 各投票者は1個の選択肢を選択して投票し, 最も多くの得票を得た選択肢を当選とする. 総投票数の過半数を得たか否かについては問題としない. <math>k \geq 2 \,</math>とすると, 各投票者は<math>k \,</math>個の選択肢を選択して投票し, 獲得票数に応じて選択肢を順位付けし, 上位<math>k \,</math>個の選択肢を当選とする.

たたみ込み

2007-07-13T15:50:00Z

124.144.188.143:

'''【たたみこみ (convolution)】'''

2つの独立な確率変数 <math>X \,</math> と <math>Y \,</math> の確率分布関数をそれぞれ <math>F_X(x) \,</math>, <math>F_Y(y) \,</math> とすると, それらの和 <math>S=X+Y \,</math> の確率分布関数は, <math>F_S(x)=\int F_X(x-y) \mathrm{d} F_Y(y) \,</math> で与えられる. この操作を, たたみ込みという. <math>X \,</math> と <math>Y \,</math> がともに離散的な確率変数, あるいはともに確率密度関数をもつ場合には, 類似の計算によって <math>S \,</math> の確率関数, あるいは確率密度関数を求めることができる.

たたみ込み法

2007-07-13T15:48:39Z

124.144.188.143:

'''【たたみこみほう (convolution algorithm)】'''

ジャクソンネットワークなど, 積形式解をもつ閉鎖型ネットワークの定常分布の正規化定数を計算するためのアルゴリズム. 閉鎖型であるため, 系内人数の和が一定の状態だけをとりあげ, その積形式解の和を求める必要がある. ノード毎に, 要素が人数に応じた積形式解であるようなベクトルを用意し, これらのすべてについて, ベクトルのたたみ込み演算 <math>Z=X*Y \,</math>, すなわち <math>Z(n)=\sum_{i=0}^n X(i)Y(n-i), \ \ n=0,1,...,N \,</math>, を行い, 正規化定数を求める.

多面体理論

2007-07-13T15:46:25Z

124.144.188.143:

'''【ためんたいりろん (polyhedral theory)】'''

<math>d \,</math>次元上の凸多面体とは, <math>d \,</math>次元上の有限個の閉半空間の共通集合, すなわち <math> \{ \mathbf{x} \in \mathbf{R}^d \mid \mathbf{A} \mathbf{x} \leq \mathbf{b} \} \,</math>という線形不等式システムを満たすベクトルの集合である. <math>d \,</math>次元多面体は, 有限個の<math>d \,</math>次元凸多面体の和集合で書き表せるものをいう. 多面体理論とは, 上で定義した多面体を, 数学的諸理論を用いて解析すること, 或いは解析された結果をいう. オペレーションズ・リサーチの分野では, 1つの凸多面体 (convex polyhedron)について論じることがほとんどである.

ダルメジ・メンデルゾーン分解

2007-07-13T15:43:34Z

124.144.188.143:

'''【だるめじめんでるぞーんぶんかい (Dulmage-Mendelsohn decomposition)】'''

ダルメジとメンデルゾーンによって提案された, 2部グラフの一意的な分解. 略して DM 分解と呼ばれる.最小被覆族の構造に基づいた分解であり, 与えられた2部グラフは, 半順序構造を有する部分グラフの族へと分解される. DM 分解は, 連立1次方程式を解く際にも有用である. 係数行列から得られる2部グラフのDM分解に基づき, 係数行列をブロック三角化することにより, 計算時間を削減することができる.

単一評価系 (多段決定過程における)

2007-07-13T15:43:02Z

124.144.188.143:

'''【たんいつひょうかけい (simple criteria)】'''

多段逐次決定過程において各段評価 <math>r_{n} \,</math> と終端評価 <math>k \,</math> を用いて単一結合型演算で集積した評価基準. 次のような評価が用いられている:

(1) 加法型　<math> r_{1} + r_{2} + \cdots + r_{N} + k \,</math>

(2) 乗法型　<math> r_{1} r_{2} \cdots r_{N} k \,</math>

(3) 最大型(最小型)　<math> r_{1} \vee r_{2} \vee \cdots \vee r_{N} \vee k~~(r_{1} \wedge r_{2} \wedge \cdots \wedge r_{N} \wedge k) \,</math>

(4) 終端型　<math> k \,</math>

断続ポアソン過程

2007-07-13T15:40:36Z

124.144.188.143:

'''【だんぞくぽあそんかてい (interrupted Poisson process (IPP))】'''

環境にオンとオフの2つの状態があり, オン状態のときはパラメータ <math>\lambda \,</math>のポアソン過程にしたがって客が到着し, オフ状態のときは客が到着しないような到着過程. オン状態とオフ状態は交互に生じ, その継続時間は互いに独立でそれぞれパラメータ <math>\mu_{\mbox{on}}, \mu_{\mbox{off}} \,</math> の指数分布にしたがう. 断続ポアソン過程は, マルコフ変調ポアソン過程の特殊な場合と考えることもできる.

探知ポテンシャル

2007-07-13T15:38:48Z

124.144.188.143:

'''【たんちぽてんしゃる (sighting potential)】'''

径路上の目標探知確率を特性づける量. 距離<math> r \,</math>の瞬間探知率またはべっ見探知確率を <math> b(r) \,</math>, 時点 <math> t \,</math>の目標位置を <math>(x(t),y(t)) \,</math>とすれば, 径路 <math> C=\{ (x(t),y(t)), t_1 \leq t \leq t_n \} \,</math>上を動く目標物の探知ポテンシャルは次式で定義される.

<math>
F(C) = - \displaystyle{\sum_{i=1}^n \log \left\{ 1-b \left( \sqrt{x(t_i)^2+y(t_i)^2} \right)
\right\} ,}
\, </math>

(離散時点探索)

<math>
\ \ \ =
\displaystyle{\int_{t_1}^{t_n} b \left( \sqrt{x(t)^2+y(t)^2} \right) {\mbox{d}}t ,}
\,</math>

(連続時間探索)

このとき, 目標探知確率は <math>P(C)= 1 - \exp(-F(C)) \,</math> で求められる.