next up previous
次へ: 3.3 行列補完理論の導入 上へ: 3 入力データの疎性の利用 戻る: 3.1 疎性に基づく係数行列の計算

3.2 共役勾配法の適用

本節では， SDPの主問題(1)の線形制約の数$m$が大きくなる問題 ( $m = \Theta(n^2)$)を効率よく解く手法について説明する． このような問題を解く場合， 表1から確認できるように， 計算量の観点からは， 係数行列 $\mbox{\boldmath$B$}$の計算と Schur方程式の求解（係数行列 $\mbox{\boldmath$B$}$のCholesky分解）， メモリ量の観点からは， 大きさが$m$の係数行列 $\mbox{\boldmath$B$}$の保持が困難となる．

この困難を解決するため， Schur方程式(3)の求解に共役勾配法の適用を試みる． 共役勾配法を用いた場合，係数行列を陽に計算し保持する必要が無く， 係数行列と任意のベクトルとの乗算さえできればよい． よって，係数行列の計算と保持に伴う問題点は消滅する． また，係数行列とベクトルとの乗算は， 入力データ行列の疎性と$m \gg n$という性質を十分に利用して， $\mathcal{O}(n^3)$の浮動小数点演算で可能である[16]． その結果，以下のような効率化が期待できる．

  元   新　
係数行列 $\mbox{\boldmath$B$}$の計算 $\mathcal{O}(n^3m+n^2m^2)$ $\Longrightarrow$ 無し
Schur方程式の求解 $\mathcal{O}(m^3)$ $\Longrightarrow$ $\mathcal{O}(n^3)$ $\times $ 共役勾配法の反復回数
$\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'$の計算 $\mathcal{O}(n^3)$    
変数などの保持 $\mathcal{O}(n^2)$    
係数行列 $\mbox{\boldmath$B$}$の保持 $\mathcal{O}(m^2)$ $\Longrightarrow$ 無し

計算時間は，共役勾配法の反復回数に比例するため， なるべく早く反復を終了させたい．ただし，あまりよい近似解が得られない 場合は内点法に不都合が生じる． このトレードオフを制御するような共役勾配法の終了条件について説明する． 共役勾配法によって得られた近似解を $\widetilde{\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}}}$とする． この近似解を元に，直行射影による補正などを行い，一つの 近似探索方向 $(\widetilde{\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}},\widetilde{\mbox{$d$... ...mbox{\boldmath$y$}}},\widetilde{\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}})$ を得ることができる． この近似探索方向が以下の条件を満たすとき， 共役勾配法を終了させる．

\begin{displaymath} \begin{array}{ll} \Vert \mbox{\boldmath$H$}(\mbox{\boldmath... ...oldmath$X$}\mbox{\boldmath$Z$}) \Vert _{F} &. \\ \end{array} \end{displaymath} (9)

ただし， $\Vert \mbox{\boldmath$A$}\Vert _F$はFrobeniusノルムで $\sqrt{\mbox{\boldmath$A$}\bullet \mbox{\boldmath$A$}}$を意味し， $\mbox{\boldmath$H$}:\Re^{n \times n} \rightarrow \mbox{$\cal{S}$}^{n}$ は $ \mbox{\boldmath$H$}(\mbox{\boldmath$A$}) \equiv \big( \mbox{\boldmath$Z$}^{1/2... ...{\boldmath$Z$}^{1/2}\mbox{\boldmath$A$}\mbox{\boldmath$Z$}^{-1/2})^{T} \big)/2 $ で定義される関数である． この条件を満たすような近似探索方向 $(\widetilde{\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}},\widetilde{\mbox{$d$... ...mbox{\boldmath$y$}}},\widetilde{\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}})$ は，適当な条件の下で 多項式時間での収束性が保証されている[12]． 不等式の評価自体は，工夫すると 少ない計算量で行うことが可能である[16]．

共役勾配法を適用した内点法の 典型的な振る舞いを， 図1で確認しよう． 図では， Schur方程式をCholesky分解や共役勾配法で解いたときの， 内点法の双対残差の対数と累積計算時間の関係をプロットしている．

図 1: Cholesky分解や共役勾配法の採用による双対残差 - 累積計算 グラフ
\includegraphics[bb=70 420 540 730,width=11cm,clip]{graph.ps}

Cholesky分解を用いた場合， 双対残差の対数と累積計算時間はほぼ比例しているが， 共役勾配法を用いた場合， 双対残差の対数にたいして累積計算時間は指数的に増えている． これは，最適解に近づくにつれ，共役勾配法 の反復回数が指数的に増えているからである． 結論として， 精度の悪い近似最適解を高速に求めるには， 共役勾配法を採用すれば良く， 高精度の最適解が必要なときは， （少なくても計算時間の観点では）Cholesky分解を採用した方が良い． 本節の手法の詳細については[16]を参照されたい．