同次自己双対内点法

【どうじじこそうついないてんほう (homogeneous self-dual interior point method)】

線形計画問題の最適性の条件に新たに$2$つのパラメータを導入することによって, 定数ベクトルが$0$ (同次), 主問題と双対問題が同形(自己双対), かつ最適解をもつ 人工的な線形計画問題を生成し, これに主双対内点法を適用する多項式時間解法である. 人工問題の最適解から, 元の問題の最適解の有無や最適解が得られる. 大きな値の初期点を必要としない点で, 非許容初期点内点法 より数値的に安定しているといわれている.