カーマーカーのアルゴリズム
カーマーカーのアルゴリズム(英: Karmarkar's algorithm)とは1984年、ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法(英: Karmarkar's method)とも呼ばれる。また、このアルゴリズムを発明とする特許が米国や日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。
カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間アルゴリズムで初めての実用的なものである。楕円体法も多項式時間アルゴリズムであるが、実用上の効率は良くない。
カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解を実行可能領域の境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解(optimal solution)に収束する[1]。
アルゴリズム
行列 以下の線形計画問題を考える。
一般 | |
---|---|
微分可能 |
凸縮小化 | |||||||
---|---|---|---|---|---|---|---|
線型 および 二次 |
|
系列範例 (Paradigms) | |||||
---|---|---|---|---|---|
グラフ理論 |
| ||||
ネットワークフロー (最大流問題) |
|