next up previous
次へ: 3 探索方向 上へ: 半正定値計画問題に対する主双対内点法 戻る: 1 半正定値計画問題


2 主双対内点法

以下では、SDP問題に対する主双対内点法の枠組み について簡単に述べる。 SDP問題(1)と(2)には 実行可能内点解が存在することを仮定する。 このとき双対定理により、SDPの主問題(1)と 双対問題(2)の 最適解は以下の式を満たす。

\begin{displaymath} \left. \begin{array}{ll} \mbox{\boldmath$A$}_{i} \bullet \m... ...\mbox{\boldmath$Z$}= \mbox{\boldmath$O$}. \end{array}\right\} \end{displaymath} (3)

SDP問題に対する主双対内点法は線形計画問題に対する主双対内点法と同様に、 中心パス $ {\cal P} $ に沿って進みながら最適解に収束する反復解法である。 ここで、中心パス $ {\cal P} $ は以下のように定義される。
\begin{displaymath} {\cal P} = \left\{ \begin{array}{c\vert ll} & \mbox{\boldm... ...Z$}= \mu \mbox{\boldmath$I$}\ (\mu > 0). \end{array}\right\}. \end{displaymath} (4)

ただし、 $\mbox{\boldmath$I$}$は単位行列を表す。 任意の$\mu > 0$に対し、中心パス$ {\cal P} $上の点が 一意に存在することが知られている。 また、中心パス$ {\cal P} $はSDP問題の実行可能内点解の集合の内部の滑らかな曲線と なっており、 $\mu \rightarrow 0$ のときSDP問題の最適解に収束することも 知られている[5]。 主双対内点法は、 中心パス $ {\cal P} = \{ \mbox{\boldmath$X$}_{\mu},\mbox{\boldmath$y$}_{\mu},\mbox{\boldmath$Z$}_{\mu} ~\vert~ \mu > 0 \}$ に沿って$\mu$が$0$となる方向に進み、 最適解に近づいていく反復解法である。 アルゴリズムの概略を以下で示した。 終了条件などについては、[3]などを参照してもらいたい。



主双対内点法
   
Step 0: 初期反復点 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$}) \in \mbox{${\cal S}$}^n_{++}\times \Re^m \times \mbox{${\cal S}$}^n_{++}$ と，パラメータ$\mu > 0$，定数 $0<\sigma<1.0$ を選ぶ．
Step 1: もし，現在の反復点 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$ が終了条件を満たしていたならば， 反復を終了する．
Step 2: 中心パス上の点 $(\mbox{\boldmath$X$}_{\mu},\mbox{\boldmath$y$}_{\mu},\mbox{\boldmath$Z$}_{\mu})$ に近づくような， 探索方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\... ...{\boldmath$Z$}})\in \mbox{${\cal S}$}^n \times \Re^m \times \mbox{${\cal S}$}^n$ を計算する．
Step 3: 次の反復点 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$}) + \alpha (\mbox{$... ...ace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$が，領域 $\mbox{${\cal S}$}^n_{++}\times \Re^m \times \mbox{${\cal S}$}^n_{++}$ に留まるような ステップサイズ $\alpha$ を計算する．
Step 4: 反復点 $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$})$と，パラメータ$\mu$を更新し， Step 1 に戻る．
  $(\mbox{\boldmath$X$},\mbox{\boldmath$y$},\mbox{\boldmath$Z$}) := (\mbox{\boldma... ...ath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}}),~~~ \mu := \sigma \mu. $
   



多項式時間での収束性を証明する際は、 探索方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$，ステップサイズ$\alpha$，定数$\sigma$の ３点をどう決定するかが重要なポイントとなる。 しかしながら、 定数$\sigma$は$0.01$から$0.1$程度と、 理論的に推奨される値に構わず貪欲に取る方が、 ほとんどの場合主双対内点法の反復回数を減少させる。 よって、実装するときは，そのような値に設定するとよい。 探索方向 $(\mbox{$d$\hspace{-0.21em}\mbox{\boldmath$X$}},\mbox{$d$\hspace{-0.11em}\mbox{\boldmath$y$}},\mbox{$d$\hspace{-0.16em}\mbox{\boldmath$Z$}})$に関しては3章で、 ステップサイズ$\alpha$に関しては4章で詳しく説明する。