カーマーカー法
【英】:Karmarkar's algorithm
1984年にカーマーカーが提案した, 初めての内点法. 「 (
は
行列,
,
は 要素がすべて
のベクトル)」の線形計画問題に対して, 「(1)
の階数は
, (2)
, (iii)最適値は
」の仮定の下で, 初期点
から最適解に収束する点列
を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.
非線形計画: | NP困難 エラーバウンド カルーシュ・キューン・タッカー条件 カーマーカー法 ダンツィク・ウルフ分解法 ニュートン法 フェンシェルの双対性 |
線形計画: | 2次錐計画 NP困難 アフィン変換法 カーマーカー法 シンプレックス法 ポテンシャル関数 中心パス |
- かーまーかーほうのページへのリンク