アフィン変換法

【あふぃんへんかんほう (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 \,$ の各要素を対角要素にもつ対角行列)」

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