Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Active set
From Wikipedia, the free encyclopedia
In optimization, a problem is defined using an objective function to minimize or maximize, and a set of constraints
that define the feasible region, that is, the set of all x to search for the optimal solution. Given a point x in the feasible region, a constraint
is called active at x if gi(x) = 0 and inactive at x if gi(x) > 0. The active set at x is made up of those constraints gi(x) that are active at the current point.
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 hyperplanes that intersect at the solution point. In quadratic programming, as the solution is not mandatorily 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.
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
- compute the lagrangians of the active set
- remove a subset of the constraints with negative lagrangians
- search for infeasible constraints
- end repeat
