- Active set
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 in the feasible region, a constraint :is called active at if and inactive at if Equality constraints are always active. The active set at is made up of those constraints 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 hyperplanes that intersect at the solution point. Inquadratic 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 (approximately)::"compute" the
Lagrange multipliers of the active set::"remove" a subset of the constraints with negative Lagrange multipliers::"search" for infeasible constraints:end repeatReferences
*.
Wikimedia Foundation. 2010.