「楕円体法」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("楕円体法" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 11:15時点における版

【だえんたいほう (ellipsoid method)】

楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「 次元空間における楕円体を用いた2分探索」のような解法である.