OR事典

同次自己双対内点法

読み方：どうじじこそうついないてんほう
【英】：homogeneous self-dual interior point method

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

「OR事典」の他の用語

線形計画：

単体法  双対問題  双対定理  同次自己双対内点法  基底解  多項式時間解法  実行可能多面体