Karmarkar's algorithmとは何？わかりやすく解説 Weblio辞書

カーマーカー法

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

「OR事典」の他の用語

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

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

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

(Karmarkar's algorithm から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 07:28 UTC 版)

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

[続きの解説]

「カーマーカーのアルゴリズム」の続きの解説一覧

>> 「Karmarkar's algorithm」を含む用語の索引
Karmarkar's algorithmのページへのリンク

Karmarkar's algorithmとは？わかりやすく解説

カーマーカー法

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

「Karmarkar's algorithm」の関連用語


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのカーマーカーのアルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

Karmarkar's algorithmとは？ わかりやすく解説

カーマーカー法

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

「Karmarkar's algorithm」の関連用語

Karmarkar's algorithmとは？わかりやすく解説