Active-set method: Difference between revisions

Revision as of 06:41, 24 January 2017

Revision as of 01:14, 13 February 2017

Line 1:

{{redirect|Active set|the band|The Active Set}}

In mathematical [[Optimization (mathematics)|optimization]], a problem is defined using an objective function to minimize or maximize, and a set of constraints

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

that define the [[feasible region]], that is, the set of all ''x'' to search for the optimal solution. Given a point <math>x</math> in the feasible region, a constraint

Line 9:

is called '''active''' at <math>x</math> if <math>g_i(x)=0</math> and '''inactive''' at <math>x</math> if <math>g_i(x)>0.</math> Equality constraints are always active. The '''active set''' at <math>x</math> is made up of those constraints <math>g_i(x)</math> that are active at the current point {{harv|Nocedal|Wright|2006|p=308}}.

The active set is particularly important in optimization theory as it determines which constraints will influence the final result of optimization. For example, in solving the [[linear programming]] problem, the active set gives the [[Hyperplane|hyperplaneshyperplane]]s that intersect at the solution point. In [[quadratic programming]], as the solution is not necessarily on one of the edges of the bounding polygon, an estimation of the active set gives us a subset of inequalities to watch while searching the solution, which reduces the complexity of the search.

==Active set methods==

Line 22:

:'''end repeat'''

Methods that can be described as '''active set methods''' include:<ref>{{harvnb|Nocedal|Wright|2006|ppp=467–480}}</ref>

* [[Successive linear programming]] (SLP) <!-- acc. to: Leyffer... - alt: acc. to "MPS glossary", http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page: Successive approximation -->

* [[Sequential quadratic programming]] (SQP) <!-- acc. to: Leyffer... - alt: acc. to "MPS glossary", http://glossary.computing.society.informs.org/ver2/mpgwiki/index.php/Main_Page: Successive approximation -->

Line 36:

==Bibliography==

* {{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/|ref=harv}} {{MR|MR=949214}}

* {{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 | postscript=<!--None-->}}.

[[Category:Mathematical optimization]]