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


中心パス

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

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

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

$\displaystyle \vec{s}=\vec{M}\vec{\xi}+\vec{q}, \quad \vec{s}\vec{\xi}=\mu \vec{1}$ (79)

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



Shigeru HANBA
平成16年3月19日