楕円体法

提供: ORWiki
2007年7月20日 (金) 11:15時点におけるOrsjwiki (トーク | 投稿記録)による版 ("楕円体法" を保護しました。 [edit=sysop:move=sysop])
ナビゲーションに移動 検索に移動

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

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