主双対内点法

【しゅそうついないてんほう (primal-dual interior point method)】

線形計画問題の主問題, 双対問題それぞれの中心パスを, ニュートン法を用いて同時に追跡して最適解を求める内点法. 多様な多項式時間解法を含む. 線形計画問題の最適性の条件の内, 相補性条件について要素ごとに正のパラメータを 導入した近似方程式系の解を追跡する解法として捉えることができる. 現在もっとも 普及している内点法であり, 相補性問題, 半正定値問題といった, より広いクラスの 問題群に拡張されている.