アフィン変換法

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

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

「構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{min.} \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0 \,} ($A\,$は$m\times n\,$行列, $b\in \mathbf {R} ^{m}\,$, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c \in \mathbf{R}^n \,} )」

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

「構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x \rightarrow (X^k)^{-1}x \,} (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X^k \,} は$x^{k}\,$の各要素を対角要素にもつ対角行列)」

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