アクティブセット法

数理最適化において、アクティブセット法は、不等式制約の集合の中から有効な制約を特定するために使用されるアルゴリズムである。特定された有効な制約は等式制約として表現され、それによって不等式制約問題がより単純な等式制約部分問題に変換される。

最適化問題は、最小化または最大化する目的関数と一連の制約条件を用いて定義されます。

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

実行可能領域、つまり最適解を探索するすべてのxの集合を定義する。${\displaystyle x}$実行可能領域では、制約

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

アクティブと呼ばれる${\displaystyle x_{0}}$もし${\displaystyle g_{i}(x_{0})=0}$、そして非アクティブ${\displaystyle x_{0}}$もし${\displaystyle g_{i}(x_{0})>0.}$等式制約は常に有効です。有効なセットは${\displaystyle x_{0}}$それらの制約から成り立っている${\displaystyle g_{i}(x_{0})}$現在活動しているもの（Nocedal & Wright 2006 、p. 308）。 

アクティブセットは、最適化理論において特に重要です。なぜなら、どの制約条件が最適化の最終結果に影響を与えるかを決定するからです。例えば、線形計画問題を解く場合、アクティブセットは解点で交差する超平面を示します。二次計画問題では、解が必ずしも境界多角形の辺上にあるとは限らないため、アクティブセットを推定することで、解を探索する際に監視すべき不等式のサブセットが得られ、探索の複雑さを軽減できます。

実行可能集合の境界をたどるアクティブセット法は、常に実行可能集合の内部にとどまろうとする内点法とは対照的である。

一般的に、アクティブセットアルゴリズムは以下の構造を持つ。

実行可能な出発点を見つける

「十分最適」 になるまで繰り返す

アクティブセットによって定義される等式問題を（近似的に）解く

アクティブセットのラグランジュ乗数を計算する

負のラグランジュ乗数を持つ制約条件のサブセットを削除する

非アクティブな制約の中から実行不可能な制約を探し出し、問題に追加する

繰り返し終了

この手法の動機は、最適解付近では通常、すべての制約のうちごく一部しか拘束力を持たないこと、そして解決ステップにかかる時間が制約の数に対して超線形時間となることにある。そのため、等式制約付き問題を連続的に解くことで、改善時に違反していないものの、改善の妨げとなる制約（負のラグランジュ乗数）を削除し、現在の解が違反している制約を追加していくことで、真の解に収束させることができる。最後の問題の最適解は、等式制約付き問題ソルバーが初期値を必要とする場合に、初期推定値として利用できることが多い。

アクティブセット法と表現できる方法には、次のものがあります。^{[ 1 ]}

• 逐次線形計画法（SLP）
• 逐次二次計画法（SQP）
• 逐次線形二次計画法（SLQP）
• 縮小勾配法（RG）
• 一般化縮小勾配法（GRG）

線形制約付き凸二次計画問題を考えてみましょう。妥当な仮定（問題が実行可能であり、制約系がすべての点で正則であり、二次目的関数が強凸である）の下では、アクティブセット法は有限ステップで終了し、問題の全体解が得られます。理論的には、アクティブセット法はシンプレックス法のように、mに対して指数関数的な反復回数を実行する可能性があります。しかし、実際の動作は通常、はるかに優れています。^{[ 2 ]：第9.1節}

• Murty, KG (1988).線形相補性、線形計画法と非線形計画法. シグマ応用数学シリーズ. 第 3巻. ベルリン: Heldermann Verlag. pp.  xlviii+629 pp. ISBN 3-88538-403-5. MR 0949214 . 2010年4月1日にオリジナルからアーカイブされました。2010年4月3日に取得。 
• ノセダル、ホルヘ；ライト、スティーブン J. (2006).数値最適化（第 2 版）. ベルリン、ニューヨーク：シュプリンガー・フェルラーク. ISBN 978-0-387-30303-1。