本節では,行列変数のサイズが 大きなSDP問題を効率よく解く手法について説明する. 入力データ行列が疎である場合でも, 主問題(1)の変数行列 が密となることは既に述べた. このため,変数行列 などサイズの密行列の保持や, それらの行列に関する演算がボトルネックとなる. 本節では,この問題点を解決するため,行列補完理論を導入する.
まず,
入力データ行列
に対し,
統合疎パターンを定義する.
を 対称行列の行や列の
添字の集合
とする.
このとき,入力データ行列に対する
統合疎パターンとは,以下で定義される集合である.
内点法の反復点
において,
拡張疎パターンに含まれない部分つまり
は,
SDPの主問題(1)の目的関数
や
線形制約
には
全く関係しない.
つまり,
それらの要素は半正定値条件
にのみ影響を与える
ことになる.
それ故,
反復点
の中で拡張疎パターンに
含まれない部分
に適当な値を与え正定値行列
となるならば,
その行列
を反復点として採用出来る.
この適当な値を定めて正定値行列にすることを,正定値補完と呼ぶ.
行列補完理論によると,がコーダルグラフの場合,
行列式の値を最大にするように正定値補完をした行列
は
以下の疎分解ができる[8].
密行列となる や の代わりに この疎行列 や を保持し,この疎性を活かしながら 内点法の反復を繰り返す手法を筆者等は提案している. その結果,サイズの密行列の保持や取り扱いを完全に回避することができた. そのためには,効率のよいSchur方程式の係数行列 の計算や, 非直線探索で反復点を更新するなど内点法の枠組み自身も少し 修正しなければならないが, 詳細については [8,15]を参照されたい.
この手法の効率性は,拡張疎パターンの疎性(行列 や の疎性) だけでなく入力データ行列の構造にも依存する. 多くの仮定をすることにより, 拡張疎パターンの疎性 のみでオーダーを見積もると, 大体次のような効率化が期待できる.
元 | 新 | ||
係数行列 の計算 | |||
Schur方程式の求解 | |||
の計算 | |||
変数などの保持 | |||
係数行列 の保持 |