カーマーカー法
【英】:Karmarkar's algorithm
1984年にカーマーカーが提案した, 初めての内点法. 「 (は行列, , は 要素がすべてのベクトル)」の線形計画問題に対して, 「(1) の階数は, (2), (iii)最適値は」の仮定の下で, 初期点 から最適解に収束する点列 を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.
非線形計画: | NP困難 エラーバウンド カルーシュ・キューン・タッカー条件 カーマーカー法 ダンツィク・ウルフ分解法 ニュートン法 フェンシェルの双対性 |
線形計画: | 2次錐計画 NP困難 アフィン変換法 カーマーカー法 シンプレックス法 ポテンシャル関数 中心パス |
カーマーカーのアルゴリズム
(カーマーカー法 から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/30 07:28 UTC 版)
カーマーカーのアルゴリズム(英: Karmarkar's algorithm)とは1984年、ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法(英: Karmarkar's method)とも呼ばれる。また、このアルゴリズムを発明とする特許が米国や日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。
- 1 カーマーカーのアルゴリズムとは
- 2 カーマーカーのアルゴリズムの概要
- 3 計算量
- 4 特許論争
- 5 脚注
- 6 関連項目
- カーマーカー法のページへのリンク