5.2 問題の前処理

与えられたSDP問題をそのまま扱うのではなく， より解きやすい問題に変換することを前処理と言う． 適切な前処理を施すことにより， 内点法の計算の効率性や数値安定性などが劇的に向上する場合もある． 詳細には触れないが，これまで提案した前処理として次の3つがある．

• ある正則行列 $\mbox{\boldmath$P$}$に対し，入力データ行列を $\mbox{\boldmath$P$}^T\mbox{\boldmath$A$}_{i}\mbox{\boldmath$P$}~(i=0,1,\ldots,m)$ に変換したSDP問題を生成する． その問題を解いて得た最適解 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$に対し， $(\mbox{\boldmath$P$}\mbox{\boldmath$X$}\mbox{\boldmath$P$}^{T},\mbox{\boldmath$y$},\mbox{\boldmath$P$}^{-T}\mbox{\boldmath$Z$}\mbox{\boldmath$P$}^{-1})$が元問題の最適解となる． うまく，正則行列 $\mbox{\boldmath$P$}$を選ぶことにより，入力データ行列 の疎性が向上する場合がある[8]．

• 主問題に自由変数がある，あるいは 双対問題に等式制約がある場合， 標準形(1)や(2)への変換の仕方により， 内点法の計算効率や得られる最適解の精度が異なる． それらがなるべく良くなるような 標準形に変換する[11]．

• 3.3節では行列補完理論を導入して，密行列に対し疎分解を導いた． 行列補完理論を別の形で適用することにより， ブロック対角な構造を持ったSDP問題に変換し， 3.4節の手法を利用して計算効率を上げることもできる[6]．