3.4 ブロック対角な構造の利用

本節では，ブロック対角な構造を持ったSDP問題を 効率よく解く手法について説明する． ブロック対角な構造を持ったSDP問題とは， 入力データ行列 $\mbox{\boldmath$A$}_{i}~(i=0,1,\ldots,m)$が

$$\mbox{\boldmath$A$}_{i} = \left(\begin{array}{llll} \mbox{\... ...}& \cdots & \mbox{\boldmath$A$}_{i}^{r} \\ \end{array}\right)$$

のように，小さな行列 $\mbox{\boldmath$A$}_{i}^{1},\mbox{\boldmath$A$}_{i}^{2},\ldots,\mbox{\boldmath$A$}_{i}^{r}$ が対角部分に並んで構成されている問題のことである． なお， 各入力データ行列の$k$番目の行列 （ $\mbox{\boldmath$A$}_0^{k}, \mbox{\boldmath$A$}_{1}^{k},\ldots,\mbox{\boldmath$A$}_{m}^{k}$） は全て同じサイズでなければならず， その大きさを$n_k$としよう． このような問題では，行列変数 $\mbox{\boldmath$X$}$も同様の構造を持った ブロック対角行列のみを考えれば十分である． もっとも， SDP問題を 対称錐計画問題の一つとして捉えると， 対象とするベクトル空間として， $\mbox{$\cal{S}$}^n$ではなく $\mbox{$\cal{S}$}^{n_1}\times \mbox{$\cal{S}$}^{n_2} \times \ldots \times \mbox{$\cal{S}$}^{n_r}$ を選んでいるという解釈の方が自然である． 内点法の多くの演算は内部の行列ごとに独立して計算できる． 例えば，(4)式のSchur方程式の係数行列 $\mbox{\boldmath$B$}$は，

$$\displaystyle B_{ij} := \sum_{k=1}^{r} \mbox{\boldmath$A$}_j... ..._i^k (\mbox{\boldmath$Z$}^k)^{-1} ~~~~~ (i,j = 1,2,\ldots,m)$$ (10)

という計算でよい． これにより，次に述べる２つの利点が生じる．

(a)

Schur方程式の係数行列 $\mbox{\boldmath$B$}$の計算や $\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}}'$の計算などで， 内部の行列ごとに独立して計算をする． もし，均等な大きさの$r$個の行列に分解されるならば， 計算量やメモリ使用量は次のように減少する．

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

(b)

入力データ行列 $\mbox{\boldmath$A$}_i$はゼロ行列では無いため （もしそうならば線形制約として意味がない）， 基本的に式(4)で定義される$B_{ij}$はゼロとはならない． しかし， $\mbox{\boldmath$A$}_i$はゼロ行列でなくても， 内部の行列 $\mbox{\boldmath$A$}_{i}^{k} ~(k=1,2,\ldots,r)$の中には ゼロ行列が多いかもしれない． その場合， (10)式で計算される$B_{ij}$はゼロとなる可能性がある． 実際，ブロック数が非常に多いSDP問題では， 係数行列 $\mbox{\boldmath$B$}$の中にゼロ要素が多数含まれることがある．
このような場合，疎Cholesky分解を実行することにより， Schur方程式を高速に解くことができる． その場合，充填(fill-in)がなるべく起らないように， 行や列を並べ替えることも重要となる．
今，係数行列 $\mbox{\boldmath$B$}$の疎性を $\beta \in [0,1]$とし， 充填については考えない． 3.1節の手法も同時に利用することにより， 次のような効率化が期待できる．

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