アクティブセット法

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

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

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

実行可能領域、つまり最適解を探索するすべてのxの集合を定義する。実行可能領域内の 点が与えられた場合、制約条件は${\displaystyle x}$

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

は、の場合にはでアクティブ、の場合にはで非アクティブと呼ばれます。等式制約は常にアクティブです。におけるアクティブセットは、現在の時点でアクティブな制約で構成されます(Nocedal & Wright 2006, p. 308)。 ${\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})}$

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

アクティブセット法

一般に、アクティブセットアルゴリズムは次の構造を持ちます。

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

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

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

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

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

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

繰り返し終了

この理由は、最適解付近では通常、拘束力を持つ制約はごく少数であり、解を求めるステップは通常、制約の数に対して超線形な時間を要するためです。したがって、等式制約問題を繰り返し解くことで、改善時には違反しないものの、改善の妨げとなる制約（負のラグランジュ乗数）を削除し、現在の解が違反する制約を追加することで、真の解に収束することができます。等式制約問題ソルバーが初期値を必要とする場合、最後の問題の最適値は初期推定値となることがよくあります。

アクティブセット法として説明できる方法には以下のものがある: ^[1]

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

パフォーマンス

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

参考文献

1. ノセダル＆ライト 2006年、467～480頁
2. NemirovskyとBen-Tal (2023).「最適化III：凸最適化」（PDF） .

参考文献

• Murty, KG (1988). 線形相補性、線形および非線形計画法. シグマ応用数学シリーズ第3巻. ベルリン: Heldermann Verlag. pp. xlviii+629 pp. ISBN 3-88538-403-5. MR  0949214. 2010年4月1日時点のオリジナルよりアーカイブ。2010年4月3日閲覧。
• Nocedal, Jorge; Wright, Stephen J. (2006).数値最適化（第2版）. ベルリン、ニューヨーク: Springer-Verlag . ISBN 978-0-387-30303-1。