next up previous
Next: アフィンスケーリング方向と中心化方向 Up: Newton法に基づく内点法の一般的なアルゴリズム Previous: 強相補性条件


中心パス

ここで, 中心パスという概念を導入しておく。 $ \vec{1}$をすべての要素が1のベクトルとし, $ \mu$を正の定数として,

$\displaystyle \vec{s}\vec{\xi}=\mu \vec{1}$ (50)

なる等式を考える。ここでは証明を省くが, (SP)の制約条件を満たす領域が内点を持つ(開集合を含む)とき, (53)と(SP)の制約条件を連立させた非線形連立方程式

\begin{displaymath}\begin{split}\vec{s}&=\vec{M}\vec{\xi}+\vec{q},  \vec{s}\vec{\xi}&=\mu \vec{1} \end{split}\end{displaymath} (51)

$ \vec{\xi}$について解くと, 与えられた$ \mu$に対して制約領域の内点にある $ \vec{\xi}(\mu)$が一意的に定まることが言える。 さらに, 次の事実が成り立つ。 これらの事実から, 軌道 $ \vec{\xi}(\mu)$(これを中心パスと呼ぶ)を追跡する ことにより強相補性条件を満たす解が求められる ことがわかる。中心パスは, 制約条件を満たす領域の内部を通って最適解に 到達する, 幾何学的に性質の良い軌道である。



Shigeru HANBA
平成15年11月16日