「アフィン変換法」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
 
'''【あふぃんへんかんほう (affine scaling method)】'''
 
'''【あふぃんへんかんほう (affine scaling method)】'''
  
−
カーマーカー法の簡略化を目的として提案された内点法の一種.主アフィン変換法は, 標準形の線形計画問題「<math> \mbox{min.} \  c^{\top}x  \  \mbox{s.t.} \ Ax = b, \ x \geq 0 \,</math>(<math>A \,</math>は<math>m \times n \,</math>行列, <math>b \in \mathbf{R}^m \,</math>, <math>c \in \mathbf{R}^n \,</math>)」に対して, <math>\{x^k : \ Ax^k=b, \ x^k > 0\} \,</math>である点列を生成し,探索方向は「<math>x \rightarrow (X^k)^{-1}x \,</math>(<math>X^k \,</math>は<math>x^k \,</math>の各要素を対角要素にもつ対角行列)」の変換後の空間で決定する.正領域に許容解をもつ線形計画問題に対して大域的収束性が保証されている.
+
カーマーカー法の簡略化を目的として提案された内点法の一種.主アフィン変換法は, 標準形の線形計画問題
 +
 
 +
「<math> \mbox{min.} \  c^{\top}x  \  \mbox{s.t.} \ Ax = b, \ x \geq 0 \,</math>(<math>A \,</math>は<math>m \times n \,</math>行列, <math>b \in \mathbf{R}^m \,</math>, <math>c \in \mathbf{R}^n \,</math>)」
 +
 
 +
に対して, <math>\{x^k : \ Ax^k=b, \ x^k > 0\} \,</math>である点列を生成し,探索方向は
 +
 
 +
「<math>x \rightarrow (X^k)^{-1}x \,</math>(<math>X^k \,</math>は<math>x^k \,</math>の各要素を対角要素にもつ対角行列)」
 +
 
 +
の変換後の空間で決定する.正領域に許容解をもつ線形計画問題に対して大域的収束性が保証されている.
 +
 
 +
[[Category:線形計画|あふぃんへんかんほう]]

2008年11月6日 (木) 13:12時点における最新版

【あふぃんへんかんほう (affine scaling method)】

カーマーカー法の簡略化を目的として提案された内点法の一種.主アフィン変換法は, 標準形の線形計画問題

「(は行列, , )」

に対して, である点列を生成し,探索方向は

「(はの各要素を対角要素にもつ対角行列)」

の変換後の空間で決定する.正領域に許容解をもつ線形計画問題に対して大域的収束性が保証されている.

「https://orsj-ml.org/orwiki/wiki/index.php?title=アフィン変換法&oldid=10103」から取得