next up previous
Next: 中心パス Up: Newton法に基づく内点法の一般的なアルゴリズム Previous: Newton法に基づく内点法の一般的なアルゴリズム


強相補性条件

行列$ \vec{M}$が歪対称であることから, 目的関数値は $ \vec{q}^T\vec{\xi}=\vec{s}^T\vec{\xi}$を 満たすxii)

さて, 問題(SP)は自明な最適解 $ \vec{\xi}=\vec{0}$を持つ。 しかし,第2.4.2で説明したように, 我々は$ \vec{\xi}$のある成分が収束する値が0であるか否かに 応じて主問題(P)と双対問題(D)の解の存在性の判定をするので, 自明な解は我々の望むものではない。 ところで, $ \vec{\xi}$が最適であり( $ \vec{s}^T \vec{x} =0$), かつ$ \vec{\xi}$の要素の中の零でないものがあったとしよう。 $ \vec{\xi} \geq \vec{0}$, $ \vec{s} \geq \vec{0}$であることを 思いだすと, $ \vec{\xi}$$ \vec{s}$の成分は,

という条件を満たすことがわかる。この条件を強相補性条件という。 強相補性条件は, より簡単に,

$\displaystyle \vec{s}+\vec{\xi} > \vec{0}$ (49)

とも書ける。 以上の議論により, 我々は問題(SP)の強相補性条件を満たす 最適解を(もしあれば)見付けなければならないことがわかる。



Shigeru HANBA
平成15年11月16日