詳細情報
- 半正定値計画問題に対する主双対内点法
半正定値計画問題に対する主双対内点法の紹介をする。
ただし、多項式時間での収束性など理論的な面には一切触れず、実際のアルゴリズムについてなるべく具体的な説明を行う。
なお、主双対内点法の中には様々なタイプのアルゴリズムが存在するが、 ここで紹介するのはパス追跡法の一番原始的なバージョンである。
- 大規模SDP問題を解く研究について
大規模なSDP問題を実用的な計算資源や時間で解くためには,解く問題の性質を利用し,効率の良い計算を行う必要がある.
あるいは,近年目覚ましい普及を遂げつつあるPCクラスタ上での並列計算も有効である.
ここでは,我々が提案してきたそれらの手法について,個別に解説をする.
- 最適化ソフトウェアSDPA
本稿では,筆者等が現在進行形で開発中の最適化ソフトウェアSDPAについて述べる.SDPAは対称錐計画問題を主双対内点法によって解く.応用上現れるような大規模な対称錐計画問題を,現実的な計算資源でできる限り効率良く解く研究もさかんに行われている.SDPAはこれらの研究の成果を数多く実装している.
「応用数理」18巻1号に掲載された原稿です。著作権は応用数理学会に帰属しています。
- 対称錐計画問題に対する主双対内点法
線形計画問題の解法であった主双対内点法は、近年の研究により対称錐計画問題の解法として発展した。このアルゴリズムは、多項式時間内で最適解が得られるという素晴らしい特徴を有している。対称錐計画問題に対する主双対内点法の紹介をスライドで行う。
トップページに戻る