有効制約法のソースを表示

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

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

: <math>g_1(x) \ge 0, \dots, g_k(x) \ge 0</math>

と表され、最適解を探索する ''x'' の集合は[[実行可能領域]]と呼ばれる。実行可能領域の点 <math>x</math> に関して、制約は

: <math>g_i(x) \ge 0</math>

を満たしており、解 <math>x_0</math> に対して <math>g_i(x_0) = 0</math> を満たす制約式を有効な制約式 (active)、<math>g_i(x_0) > 0</math>を満たす制約式を有効でない制約式 (inactive) という。等式制約式は常に有効な制約式となる。<math>x_0</math> における有効制約（集合）は、現在の点においての有効な制約式 <math>g_i(x_0)</math> から構成される{{sfn|Nocedal|Wright|2006|p=308}}。

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

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

: 実行可能解を見つける
: '''繰り返す''' "解が[[KKT条件|最適性の条件]]を満たすまで"
:: ''解く'' 有効制約に対して等式制約下最適化問題
:: ''計算する'' 有効制約に対応する[[ラグランジュ乗数]]
:: ''除去'' ラグランジュ乗数が負となる制約の集合を一つ
: '''繰り返し終了'''

有効制約法に該当する解法は以下のものが挙げられる<ref>{{harvnb|Nocedal|Wright|2006|pp=467–480}}</ref>:
* [[逐次線形計画法]] (SLP) <!-- acc. to: Leyffer... - alt: acc. to "MPS glossary", http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page: Successive approximation -->
* [[逐次二次計画法]] (SQP) <!-- acc. to: Leyffer... - alt: acc. to "MPS glossary", http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page: Successive approximation  -->
* {{仮リンク|逐次線形二次計画法|en|Sequential linear-quadratic programming}} (SLQP) <!-- acc. to: Leyffer... - alt: acc. to "MPS glossary", http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page: Successive approximation  -->
* [[簡約勾配法]] (RG) <!-- acc. to: MPS glossary, http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page - alt: acc. to "Optimization - Theory and Practice" (Forst, Hoffmann): Projection method -->
* [[一般化簡約勾配法]] (GRG) <!-- acc. to: MPS glossary, http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page - alt: acc. to "Optimization - Theory and Practice" (Forst, Hoffmann): Projection method -->

== 性能 ==
線形制約付き凸二次計画問題について議論する。ある仮定の下（実行可能な問題かつ制約行列が任意の点において正則となり、目的関数の二次の行列が正定値行列である場合）、有効制約法は有限回の反復で終了し、問題の大域的最適解を得ることができる。理論的には、有効制約法は[[単体法]]と同様に、反復に要する回数が最悪の場合制約式の数''m''の指数オーダーとなる。しかしながら、実際のほとんどの問題に対しては反復回数はそれほど多くかからずに終了する<ref name=":0">{{Cite web |last=Nemirovsky and Ben-Tal |date=2023 |title=Optimization III: Convex Optimization |url=http://www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf |access-date=2025-02-17 }}</ref>{{Rp|at=Sec.9.1}}。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite book |last=Murty |first=K. G. |title=Linear complementarity, linear and nonlinear programming |series=Sigma Series in Applied Mathematics |volume=3 |publisher=Heldermann Verlag |location=Berlin |year=1988 |pages=xlviii+629 pp |isbn=3-88538-403-5 |url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/ |mr=949214 |access-date=2010-04-03 |archive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/ |archive-date=2010-04-01 |url-status=dead }} 
* {{Cite book |last1=Nocedal |first1=Jorge |last2=Wright |first2=Stephen J. |title=Numerical Optimization |publisher=[[Springer-Verlag]] |location=Berlin, New York |edition=2nd |isbn=978-0-387-30303-1 |year=2006 |ref=harv }}

{{最適化アルゴリズム}}

{{DEFAULTSORT:ゆうこうせいやくほう}}
[[Category:数学に関する記事]]
[[Category:最適化アルゴリズムとメソッド]]