カーマーカー法

【かーまーかーほう (Karmarkar's algorithm)】

1984年にカーマーカーが提案した, 初めての内点法. 「$\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0$ ($A$は$m \times n$行列, $c \in \mboxテンプレート:\bf R^n$, $e \in \mboxテンプレート:\bf R^n$は 要素がすべて$1$のベクトル)」の線形計画問題に対して, 「(1) $A$の階数は$m$, (2)$A(e/n)=0$, (iii)最適値は$0$」の仮定の下で, 初期点 $x^0 =e/n$ から最適解に収束する点列 $\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\}$ を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.