next up previous
Next: 強相補性条件 Up: 内点法 Previous: Dikinステップ法の意味


Newton法に基づく内点法の一般的なアルゴリズム

本節では, Newton法に基づく内点法のアルゴリズムについて簡単に述べる。

2.4.2節の結果から, 主問題と双対問題を解くことは, 問題

$\displaystyle {\rm {(SP)}}\quad \min \left \{ \vec{q}^T \vec{\xi}: \vec{M} \vec{\xi} + \vec{q} \geq \vec{0}, \vec{\xi} \geq \vec{0} \right \}$

を解くことに帰着されることがわかっている。 ここに, $ \vec{M}$は歪対称行列であり, $ \vec{q}$は各成分が非負のベクトルである。 そこで, 本節では(SP)を出発点とする。





Shigeru HANBA
平成15年11月16日