next up previous
Next: 強相補性条件 Up: 内点法の詳細 Previous: 線形計画問題(SP)の意味


内点法のアルゴリズムの一般形

本節では, 内点法のアルゴリズムの一般形について簡単に述べる。

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

$\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
平成16年3月19日