次へ:
1 半正定値計画問題
上へ:
TOP PAGE
大規模SDP問題を解く研究について
中田 和秀(東京工業大学 社会理工学研究科)
概要:
大規模なSDP問題を実用的な計算資源や時間で解くためには, 解く問題の性質を利用し, 内点法の枠組みをできるだけ維持しながら, 効率の良い計算を行う必要がある. あるいは,近年目覚ましい普及を遂げつつあるPCクラスタ上での並列計算 も有効である. ここでは, 我々が提案してきたそれらの手法について,個別に解説をする.
1 半正定値計画問題
2 内点法
3 入力データの疎性の利用
3.1 疎性に基づく係数行列の計算
3.2 共役勾配法の適用
3.3 行列補完理論の導入
3.4 ブロック対角な構造の利用
4 並列計算
4.1 係数行列の計算の並列化
4.2 Cholesky分解の並列化
5 その他
5.1 数値演算ライブラリの利用
5.2 問題の前処理
5.3 計算誤差について
参考文献