内点法

【ないてんほう (interior point method)】

線形計画問題に対するカーマーカー法によって触発され,発展した制約付き最適化問題の反復解法の総称. 実行可能領域の内部を通って最適解へ近づくのでこう呼ばれる.特に大規模問題に有効とされ, 凸計画問題, 半正定値計画問題等へも拡張されている. 主問題または双対問題のどちらか一方の実行可能領域に点列を生成する内点法を主内点法, 主問題および双対問題の双方の実行可能領域に点列を生成する内点法を主双対内点法と呼ぶ.