有効制約法

有効制約法（ゆうこうせいやくほう、英: active-set method）とは、数理最適化において不等式制約の中から有効な制約式を特定するために用いられる解法である。有効な制約式を等式制約式として問題を扱うことで、不等式制約付き最適化問題は単純な等式制約付き最適化子問題へと変換される。

ある目的関数を最大化、最小化する最適化問題において各制約は

${\displaystyle g_{1}(x)\geq 0,\dots ,g_{k}(x)\geq 0}$

と表され、最適解を探索する ${\displaystyle x}$ の集合は実行可能領域と呼ばれる。実行可能領域の点 ${\displaystyle x}$ に関して、制約は

${\displaystyle g_{i}(x)\geq 0}$

を満たしており、解 ${\displaystyle x_{0}}$ に対して ${\displaystyle g_{i}(x_{0})=0}$ を満たす制約式を有効な制約式 (active)、${\displaystyle g_{i}(x_{0})>0}$を満たす制約式を有効でない制約式 (inactive) という。等式制約式は常に有効な制約式となる。${\displaystyle x_{0}}$ における有効制約（集合）は、現在の点においての有効な制約式 ${\displaystyle g_{i}(x_{0})}$ から構成される^[1]。

特に最適化理論においてどの制約が最適化の結果の決定に影響を与えるかを判別できる観点から有効制約は重要な概念である。具体的には、線形計画問題では最適解上で有効制約は超平面を成している。また二次計画問題では最適解が必ずしも多面体の境界上であるとは限らないことから、有効制約を推定することで解の探索で考慮すべき不等式制約を減らすことで、一探索でかかる計算量を減らすことができる。

有効制約法

一般的に有効制約法は以下の手続きに従った解法である:

実行可能解を見つける

繰り返す "解が最適性の条件を満たすまで"

解く 有効制約に対して等式制約下最適化問題

計算する 有効制約に対応するラグランジュ乗数

除去 ラグランジュ乗数が負となる制約の集合を一つ

繰り返し終了

有効制約法に該当する解法は以下のものが挙げられる^[2]:

• 逐次線形計画法 (SLP)
• 逐次二次計画法 (SQP)
• 逐次線形二次計画法 (SLQP)
• 簡約勾配法 (RG)
• 一般化簡約勾配法 (GRG)

性能

線形制約付き凸二次計画問題について議論する。ある仮定の下（実行可能な問題かつ制約行列が任意の点において正則となり、目的関数の二次の行列が正定値行列である場合）、有効制約法は有限回の反復で終了し、問題の大域的最適解を得ることができる。理論的には、有効制約法は単体法と同様に、反復に要する回数が最悪の場合制約式の数mの指数オーダーとなる。しかしながら、実際のほとんどの問題に対しては反復回数はそれほど多くかからずに終了する^[3](Sec.9.1)。