本節では,大規模なSDP問題を内点法で解く際 ボトルネックとなる探索方向の計算について述べる. 内点法についての詳しい説明は, [2,19,20] などを参考にして頂きたい.
これまで様々な探索方向に対する, 理論的な収束性について研究がなされてきた. しかし経験上,内点法の実際の反復回数には大した違いはない. そのため,効率よく計算できる探索方向を用いるのが実用的である. 現在,SDP問題を解くソフトウェアの多くは, HKM方向[10,13,14]あるいは NT方向[18]を採用している. 以下では,我々が開発したソフトウェアSDPA[21]が 採用しているHKM方向について述べる.
HKM方向
を得るためには,
次の線形方程式系(この方程式系をSchur方程式と呼ぶ)を解く必要がある.
また大規模なSDP問題を解く場合,メモリの確保がボトルネックとなる場合も多い. 多くのメモリを必要とする部分は,以下の2つに分類できる.
これまで説明した内点法の枠組みは,2次錐計画(Second-Order Cone Programming; SOCPと略)問題やLP問題にも適用できる. 次元のベクトルを変数とし, 線形制約の数がであるSOCP問題やLP問題を内点法で解いた場合の, 計算量とメモリ使用量についても 表1に掲載した. 何を基準に比較するかという議論もあるが, SDP問題を解くのは他の2つを解くよりも難しいことは確かであろう. これらの差が生じる原因は, SDP問題が行列を取り扱う問題であるのに対し, SOCP問題やLP問題はベクトルを取り扱う問題であるから, というのが一つの説明である.
さらに付け加えると, SOCP問題やLP問題を解く内点法では, 入力データの疎性を利用した計算が容易である. その場合,理想的な状況を仮定して全体の計算量を大雑把に見積もると, それぞれ , 程度になる. しかしながら,SDP問題に対する内点法の場合は, それほど簡単には入力データの疎性を利用した計算ができない. それを解決する手法については次章で述べる.