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

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

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

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

「 ${\mbox{min.}}\ c^{\top }x\ {\mbox{s.t.}}\ Ax=b,\ x\geq 0\,$ ( $A\,$ は $m\times n\,$ 行列, $b\in \mathbf {R} ^{m}\,$ , $c\in \mathbf {R} ^{n}\,$ )」

に対して, $\{x^{k}:\ Ax^{k}=b,\ x^{k}>0\}\,$ である点列を生成し,探索方向は

「 $x\rightarrow (X^{k})^{-1}x\,$ ( $X^{k}\,$ は $x^{k}\,$ の各要素を対角要素にもつ対角行列)」

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

@@ 1行目: / 1行目: @@
 '''【あふぃんへんかんほう (affine scaling method)】'''
-カーマーカー法の簡略化を目的として提案された内点法の一種.主アフィン変換法は, 標準形の線形計画問題「$ \mbox{min.} \  c^{\top}x  \  \mbox{s.t.} \ Ax = b, \ x \geq 0$($A$は$m \times n$行列, $b \in \mbox{{\bf R}}^m$, $c \in \mbox{{\bf R}}^n$)」に対して, $\{x^k : \ Ax^k=b, \ x^k > 0\}$である点列を生成し,探索方向は「$x \rightarrow (X^k)^{-1}x$($X^k$は$x^k$の各要素を対角要素にもつ対角行列)」の変換後の空間で決定する.正領域に許容解をもつ線形計画問題に対して大域的収束性が保証されている.
+カーマーカー法の簡略化を目的として提案された内点法の一種.主アフィン変換法は, 標準形の線形計画問題
+「<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時点における最新版

案内メニュー

検索