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