Karmarkar's algorithm

OR事典

カーマーカー法

読み方：かーまーかーほう
【英】：Karmarkar's algorithm

1984年にカーマーカーが提案した, 初めての内点法. 「 (は行列, , は 要素がすべてのベクトル)」の線形計画問題に対して, 「(1) の階数は, (2), (iii)最適値は」の仮定の下で, 初期点 から最適解に収束する点列 を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.

「OR事典」の他の用語

非線形計画：	NP困難  エラーバウンド  カルーシュ・キューン・タッカー条件  カーマーカー法  ダンツィク・ウルフ分解法  ニュートン法  フェンシェルの双対性
線形計画：	2次錐計画  NP困難  アフィン変換法  カーマーカー法  シンプレックス法  ポテンシャル関数  中心パス

ウィキペディア

カーマーカーのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/08 08:10 UTC 版)

カーマーカーのアルゴリズム（英: Karmarkar's algorithm）とは1984年、ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法（英: Karmarkar's method）とも呼ばれる。また、このアルゴリズムを発明とする特許が米国や日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。

カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間アルゴリズムで初めての実用的なものである。楕円体法も多項式時間アルゴリズムであるが、実用上の効率は良くない。

カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解を実行可能領域の境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解（optimal solution）に収束する^[1]。

アルゴリズム

行列 ${\displaystyle A}$

例解

以下の線形計画問題を考える。

maximize ${\displaystyle x_{1}+x_{2}}$

Optimization computes maxima and minima.

非線形（制約付き）

一般	バリア関数 ペナルティ関数法
微分可能	ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法

凸最適化

凸最小化	切除平面法 簡約勾配法 劣勾配法 近接勾配法
線形 および 二次	内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法
ネットワークフロー (最大流問題)	ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア

この項目は、応用数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

• 表示
• 編集

この項目は、法分野に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（P:法学/PJ:法学）。

• 表示
• 編集