Content deleted Content added
m fixed typo where using 'x' instead of 'x_0' |
|||
Line 23:
:: ''compute'' the [[Lagrange multipliers]] of the active set
:: ''remove'' a subset of the constraints with negative Lagrange multipliers
:: ''search'' for infeasible constraints among the inactive constraints and add them to the problem
: '''end repeat'''
The motivations for this is that near the optimum usually only a small number of all constraints are binding and the solve step usually takes superlinear time in the amount of constraints. Thus repeated solving of a series equality constrained problem, which drop constraints which are not violated when improving but are in the way of improvement (negative lagrange multipliers) and adding of those constraints which the current solution violates can converge against the true solution. The optima of the last problem can often provide an initial guess in case the equality constrained problem solver needs an intital value.
Methods that can be described as '''active-set methods''' include:<ref>{{harvnb|Nocedal|Wright|2006|pp=467–480}}</ref>
Line 35 ⟶ 37:
<!-- ? Method of feasible directions (MFD) -->
<!-- ? Gradient projection method - alt: acc. to "Optimization - Theory and Practice" (Forst, Hoffmann): Projection method -->
== Performance ==
Consider the problem of Linearly Constrained Convex Quadratic Programming. Under reasonable assumptions (the problem is feasible, the system of constraints is regular at every point, and the quadratic objective is strongly convex), the active-set method terminates after finitely many steps, and yields a global solution to the problem. Theoretically, the active-set method may perform a number of iterations exponential in ''m'', like the [[simplex method]]. However, its practical behaviour is typically much better.<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}}</ref>{{Rp|___location=Sec.9.1}}
| |||