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

提供: ORWiki
ナビゲーションに移動 検索に移動
("楕円体法" を保護しました。 [edit=sysop:move=sysop])
2行目: 2行目:
  
 
楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.
 
楕円体法は, 微分不可能な凸計画に対する解法として,1976年にユーディン・ネミロフスキー (Yudin--Nemirovski\u\i) によって提案された. その後 1979年にカチヤン (Khachiyan) によって線形計画に適用され,線形計画が多項式時間で解けることが初めて示された. 楕円体法は, 実用面においては単体法や内点法に比べて非常に効率が悪い一方で, 線形, 非線形, 組合せなどの最適化問題に対して様々な理論的な結果を残している. 「<math>n</math> 次元空間における楕円体を用いた2分探索」のような解法である.
 +
 +
詳しくは[[《楕円体法》|基礎編:楕円体法]]を参照.

2007年8月8日 (水) 20:21時点における版

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

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

詳しくは基礎編:楕円体法を参照.