Active-set method

In mathematical <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a>, the active-set method is an algorithm used to identify the active <a href="/facts/Constraint_(mathematics)/QLFIFlFX">constraints</a> in a set of <a href="/facts/Inequality_(mathematics)/qkze4zdI">inequality</a> 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 <a href="/facts/Feasible_region/cJUKNCmM">feasible region</a>, 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 <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> problem, the active set gives the <a href="/facts/Hyperplane/2s2ycYYd">hyperplanes</a> that intersect at the solution point. In <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic programming</a>, 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.

Active-set method open-in-new

Active-set method