Search Results for “active set method”

Source: Active-set method

In mathematical optimization, the active-set method is an algorithm used to identify the active constraints in a set of inequality constraints. The active constraints are then expressed as equality constraints, thereby transforming an inequality-constrained problem into a simpler equality-constrained subproblem.
An optimization problem is defined using an objective function to minimize or maximize, and a set of constraints

g

1

(
x
)
≥
0
,
…
,

g

k

(
x
)
≥
0

{\displaystyle g_{1}(x)\geq 0,\dots ,g_{k}(x)\geq 0}

that define the feasible region, that is, the set of all x to search for the optimal solution. Given a point

x

{\displaystyle x}

in the feasible region, a constraint

g

i

(
x
)
≥
0

{\displaystyle g_{i}(x)\geq 0}

is called active at

x

0

{\displaystyle x_{0}}

if

g

i

(

x

0

)
=
0

{\displaystyle g_{i}(x_{0})=0}

, and inactive at

x

0

{\displaystyle x_{0}}

if

g

i

(

x

0

)
>
0.

{\displaystyle g_{i}(x_{0})>0.}

Equality constraints are always active. The active set at

x

0

{\displaystyle x_{0}}

is made up of those constraints

g

i

(

x

0

)

{\displaystyle g_{i}(x_{0})}

that are active at the current point (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. 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.