2 内点法

本節では，大規模なSDP問題を内点法で解く際 ボトルネックとなる探索方向の計算について述べる． 内点法についての詳しい説明は， [2,19,20] などを参考にして頂きたい．

これまで様々な探索方向に対する， 理論的な収束性について研究がなされてきた． しかし経験上，内点法の実際の反復回数には大した違いはない． そのため，効率よく計算できる探索方向を用いるのが実用的である． 現在，SDP問題を解くソフトウェアの多くは， HKM方向[10,13,14]あるいは NT方向[18]を採用している． 以下では，我々が開発したソフトウェアSDPA[21]が 採用しているHKM方向について述べる．

HKM方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$を得るためには， 次の線形方程式系（この方程式系をSchur方程式と呼ぶ）を解く必要がある．

$$\mbox{\boldmath$B$}\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}= \mbox{\boldmath$s$}.$$ (3)

なお，係数行列 $\mbox{\boldmath$B$}\in \mbox{$\cal{S}$}^m$ と右辺ベクトル $\mbox{\boldmath$s$}\in \Re^m$は， 次の計算で得られるものである．

$$B_{ij} := \mbox{\boldmath$A$}_j \bullet \mbox{\boldmath$X$}\mbox{\boldmath$A$}_i \mbox{\boldmath$Z$}^{-1} ~~~~~ (i,j = 1,2,\ldots,m),$$ (4)

$$s_i := [\mbox{\boldmath$r$}_p]_i - \mbox{\boldmath$A$}_i \bullet (\mbox{... ...mbox{\boldmath$R$}_d) \mbox{\boldmath$Z$}^{-1} ~~~~~ (i = 1,2,\ldots,m)%\notag$$ (5)

Schur方程式(3)を解き $\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}$が得られれば， 次式の代入で残りの行列変数を求めればよい．

$$\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}} := \mbox{\boldmath$R$}_d - \sum_{j=1}^m \mbox{\boldmath$A$}_j \mbox{$d$\hspace{-0.06em}$y$}_j,$$ (6)

$$% \notag \\ \mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}' := (\mbox{\boldmath$R$}_c - \mbox{\boldmath$X$}\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}) \mbox{\boldmath$Z$}^{-1},$$ (7)

$$\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}} := (\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'+\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'^T)/2.% \notag$$ (8)

つまり，まず行列 $\mbox{\boldmath$B$}$ の各要素を計算し，その行列を係数行列とする 線形方程式系を解くことにより $\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}$ を計算する． その後， $\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}$， $\widehat{\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}}$， $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}$ を順次計算する． この場合，線形方程式系の 係数行列 $\mbox{\boldmath$B$}$が正定値行列になっていることを付け加えておく． これらの中で， 計算時間の大部分を消費するのは （つまり内点法の計算時間の大部分を消費するのは），

• Schur方程式の係数行列 $\mbox{\boldmath$B$}$の計算 $\cdots$  (4)式の部分
• Schur方程式を解いて $\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}$を求める $\cdots$  (3)式の部分
• $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'$の計算 $\cdots$  (7)式の部分

の3つの計算部分である．

また大規模なSDP問題を解く場合，メモリの確保がボトルネックとなる場合も多い． 多くのメモリを必要とする部分は，以下の2つに分類できる．

• 行列変数 $\mbox{\boldmath$X$},\ \mbox{\boldmath$Z$}$や逆行列 $\mbox{\boldmath$Z$}^{-1}$などの$n \times n$行列の保持
• Schur方程式の係数行列 $\mbox{\boldmath$B$}$である$m \times m$行列の保持

これら5つの部分で必要とする計算量やメモリ使用量を， 行列変数 $\mbox{\boldmath$X$}$や $\mbox{\boldmath$Z$}$のサイズ$n$と主問題(1)の 線形制約の数$m$を使ってオーダー表記したのが， 表1の``SDP''の列である． これらは， 次章以下の各節で説明する手法の効率性を議論するときにも使う．

表 1: 計算量とメモリ使用量

	SDP	SOCP	LP
係数行列 $\mbox{\boldmath$B$}$の計算	$\mathcal{O}(n^3m+n^2m^2)$	$\mathcal{O}(nm^2)$	$\mathcal{O}(nm^2)$
Schur方程式の求解	$\mathcal{O}(m^3)$	$\mathcal{O}(m^3)$	$\mathcal{O}(m^3)$
$\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'$の計算	$\mathcal{O}(n^3)$	$\mathcal{O}(n)$	$\mathcal{O}(n)$
変数などの保持	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	$\mathcal{O}(n)$
係数行列 $\mbox{\boldmath$B$}$の保持	$\mathcal{O}(m^2)$	$\mathcal{O}(m^2)$	$\mathcal{O}(m^2)$

これまで説明した内点法の枠組みは，2次錐計画(Second-Order Cone Programming; SOCPと略)問題やLP問題にも適用できる． $n$次元のベクトルを変数とし， 線形制約の数が$m$であるSOCP問題やLP問題を内点法で解いた場合の， 計算量とメモリ使用量についても 表1に掲載した． 何を基準に比較するかという議論もあるが， SDP問題を解くのは他の2つを解くよりも難しいことは確かであろう． これらの差が生じる原因は， SDP問題が行列を取り扱う問題であるのに対し， SOCP問題やLP問題はベクトルを取り扱う問題であるから， というのが一つの説明である．

さらに付け加えると， SOCP問題やLP問題を解く内点法では， 入力データの疎性を利用した計算が容易である． その場合，理想的な状況を仮定して全体の計算量を大雑把に見積もると， それぞれ $\mathcal{O}(n+m^2)$, $\mathcal{O}(n+m)$程度になる． しかしながら，SDP問題に対する内点法の場合は， それほど簡単には入力データの疎性を利用した計算ができない． それを解決する手法については次章で述べる．