以下では、SDP問題に対する主双対内点法の枠組み
について簡単に述べる。
SDP問題(1)と(2)には
実行可能内点解が存在することを仮定する。
このとき双対定理により、SDPの主問題(1)と
双対問題(2)の
最適解は以下の式を満たす。
(3) |
主双対内点法 | |
Step 0: | 初期反復点 と,パラメータ,定数 を選ぶ. |
Step 1: | もし,現在の反復点 が終了条件を満たしていたならば, 反復を終了する. |
Step 2: | 中心パス上の点 に近づくような, 探索方向 を計算する. |
Step 3: | 次の反復点 が,領域 に留まるような ステップサイズ を計算する. |
Step 4: | 反復点 と,パラメータを更新し, Step 1 に戻る. |
多項式時間での収束性を証明する際は、 探索方向 ,ステップサイズ,定数の 3点をどう決定するかが重要なポイントとなる。 しかしながら、 定数はから程度と、 理論的に推奨される値に構わず貪欲に取る方が、 ほとんどの場合主双対内点法の反復回数を減少させる。 よって、実装するときは,そのような値に設定するとよい。 探索方向 に関しては3章で、 ステップサイズに関しては4章で詳しく説明する。