カーマーカー法

提供:ORWiki
移動: 案内, 検索

【かーまーかーほう (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 \mathbf{R}^n \,, e \in \mathbf{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\} \, を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.

個人用ツール