3.3 行列補完理論の導入

本節では，行列変数のサイズ$n$が 大きなSDP問題を効率よく解く手法について説明する． 入力データ行列が疎である場合でも， 主問題(1)の変数行列 $\mbox{\boldmath$X$}$が密となることは既に述べた． このため，変数行列 $\mbox{\boldmath$X$}$などサイズ$n$の密行列の保持や， それらの行列に関する演算がボトルネックとなる． 本節では，この問題点を解決するため，行列補完理論を導入する．

まず， 入力データ行列 $\mbox{\boldmath$A$}_i ~(i=0,1,\ldots,m)$に対し， 統合疎パターンを定義する． $V$を $n \times n$ 対称行列の行や列の 添字の集合 $\{1,2,\ldots,n\}$とする． このとき，入力データ行列に対する 統合疎パターン$E$とは，以下で定義される集合である．

$$E = \{ (\alpha,\beta) \in V \times V: i \not=j, \ [\mbox{\... ...{\alpha\beta} \not= 0, \ \exists i \in \{0,1,2,\ldots,m\} \}.$$

このとき，$V$ を頂点の集合とし $E$ を枝集合とすると，$(V,E)$は 一つのグラフを導く． 次に，拡張疎パターンについて述べる． 拡張疎パターン $F$とは，統合疎パターン$E$のスーパーセットであり， $V$と$F$から導かれるグラフ$(V,F)$がコーダルグラフとなるような集合である．

内点法の反復点 $\mbox{\boldmath$X$}\in \mbox{$\cal{S}$}^{n}_{++}$において， 拡張疎パターン$F$に含まれない部分つまり $\{X_{\alpha\beta} : (\alpha,\beta) \notin F\}$は， SDPの主問題(1)の目的関数 $\mbox{\boldmath$A$}_0 \bullet \mbox{\boldmath$X$}$や 線形制約 $\mbox{\boldmath$A$}_{i} \bullet \mbox{\boldmath$X$}= b_{i}$ $(i = 1,2,\ldots,m)$には 全く関係しない． つまり， それらの要素は半正定値条件 $\mbox{\boldmath$X$}\in \mbox{$\cal{S}$}_{+}^{n}$にのみ影響を与える ことになる． それ故， 反復点 $\mbox{\boldmath$X$}\in \mbox{$\cal{S}$}^{n}_{++}$の中で拡張疎パターン$F$に 含まれない部分 $\{X_{\alpha\beta} : (\alpha,\beta) \notin F\}$ に適当な値を与え正定値行列 $\widehat{\mbox{\boldmath$X$}}$となるならば， その行列 $\widehat{\mbox{\boldmath$X$}} \in \mbox{$\cal{S}$}^n_{++}$を反復点として採用出来る． この適当な値を定めて正定値行列にすることを，正定値補完と呼ぶ． 行列補完理論によると，$(V,F)$がコーダルグラフの場合， 行列式の値を最大にするように正定値補完をした行列 $\widehat{\mbox{\boldmath$X$}}$は 以下の疎分解ができる[8]．

$$\widehat{\mbox{\boldmath$X$}} = \mbox{\boldmath$M$}^{-T} \mbox{\boldmath$M$}^{-1}.$$

ここで， $\mbox{\boldmath$M$}$は 拡張疎パターン$F$の部分にのみ非ゼロ要素を持つ疎行列であり， さらに下三角行列を行と列を適当に置換した行列となっている． また，双対問題(2)の行列変数 $\mbox{\boldmath$Z$}$は，

$$\mbox{\boldmath$Z$}= \mbox{\boldmath$N$}\mbox{\boldmath$N$}^{T}$$

という形に疎Cholesky分解することができる． ここで， $\mbox{\boldmath$N$}$は 拡張疎パターン$F$の部分にのみ非ゼロ要素を持つ疎行列であり， 下三角行列を適当に行と列を置換した行列となっている．

密行列となる $\mbox{\boldmath$X$}$や $\mbox{\boldmath$Z$}^{-1}$の代わりに この疎行列 $\mbox{\boldmath$M$}$や $\mbox{\boldmath$N$}$を保持し，この疎性を活かしながら 内点法の反復を繰り返す手法を筆者等は提案している． その結果，サイズ$n$の密行列の保持や取り扱いを完全に回避することができた． そのためには，効率のよいSchur方程式の係数行列 $\mbox{\boldmath$B$}$の計算や， 非直線探索で反復点を更新するなど内点法の枠組み自身も少し 修正しなければならないが， 詳細については [8,15]を参照されたい．

この手法の効率性は，拡張疎パターンの疎性（行列 $\mbox{\boldmath$M$}$や $\mbox{\boldmath$N$}$の疎性） だけでなく入力データ行列の構造にも依存する． 多くの仮定をすることにより， 拡張疎パターンの疎性 $$\alpha = \frac{\vert F\vert}{n^2} \in [0,1]$$ のみでオーダーを見積もると， 大体次のような効率化が期待できる．

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