Active-set method: Difference between revisions

Revision as of 21:21, 1 October 2018

Revision as of 23:28, 1 July 2019

Line 3:

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

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

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}}.

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

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]]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.

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}}.

==Active set methods==

In general an active set algorithm has the following structure:

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]]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.

:Find a feasible starting point

:'''repeat until''' "optimal enough"

::''solve'' the equality problem defined by the active set (approximately)

::''compute'' the [[Lagrange multipliers]] of the active set

::''remove'' a subset of the constraints with negative Lagrange multipliers

::''search'' for infeasible constraints

:'''end repeat'''

==Active -set methods==

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

In general an active -set algorithm has the following structure:

: Find a feasible starting point

: '''repeat until''' "optimal enough"

:: ''solve'' the equality problem defined by the active set (approximately)

:: ''compute'' the [[Lagrange multipliers]] of the active set

:: ''remove'' a subset of the constraints with negative Lagrange multipliers

:: ''search'' for infeasible constraints

: '''end repeat'''

Methods that can be described as '''active -set methods''' include:<ref>{{harvnb|Nocedal|Wright|2006|pp=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 ⟶ 38:

==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=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 |dead-url=yes |df=}}

* {{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:Optimization algorithms and methods]]