有効制約法

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

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

${\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}$ を満たす制約式を有効な制約式 (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)。

脚注

参考文献

• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 3-88538-403-5. MR949214. オリジナルの2010-04-01時点におけるアーカイブ。. https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/ 2010年4月3日閲覧。 
• Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-30303-1 

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア