有効制約法#

読み: ゆうこうせいやくほう
英名: Active Set Method

有効制約法とは，不等式制約のある最適化問題を解く際用いられる手法である．特に二次計画問題を解く際によく用いられる．有効制約法には主有効制約法と双対制約法がある．ここでは主有効制約法について説明する．

主有効制約法は，暫定解によりアクティブになっている制約式（アクティブセット）を用いて，元の問題を等式制約のみの二次計画問題に近似する．この二次計画問題の最適解が元の問題の KKT 条件を満たせばアルゴリズムは終了する．もしそうでなければ，解とアクティブセットを更新し，再び等式制約のみの二次計画問題を解く．

二次計画問題においては一般的に内点法より有効制約法の方が速いとされている．ただし，制約式の数が増えて，変数の数と同程度になると，内点法が速度的に有利になる．