「楕円体法」の版間の差分
ナビゲーションに移動
検索に移動
| 1行目: | 1行目: | ||
'''【だえんたいほう (ellipsoid method)】''' | '''【だえんたいほう (ellipsoid method)】''' | ||
| − | 楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「 | + | 楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である. |
2007年7月16日 (月) 17:37時点における版
【だえんたいほう (ellipsoid method)】
楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「 次元空間における楕円体を用いた2分探索」のような解法である.
