Does the algorithm know the correct active set beforehand?

Usually not; identifying or refining it is a central part of the method.

Can a previously active constraint become inactive?

Yes. Releasing a working-set constraint may permit improvement, and changing problem data can alter the final active set.

Why are warm starts useful?

Related problems may share similar binding constraints, reducing the work needed to locate a good working set, although large changes can remove that advantage.

AI Glossary / Mathematics and optimization / Intermediate

Active-set method

Definition

An active-set method is an optimization approach that works with a changing subset of constraints believed to be tight at the solution. A tight inequality holds with equality, such as using exactly the allowed capacity. The algorithm solves simpler subproblems using a working set, then updates that set as it searches for an optimum.

What it means

A constrained problem can contain many limits, but only some may directly restrict the best solution. A production plan might exhaust one machine's capacity while leaving another partly unused. Active-set methods try to identify the boundaries that matter locally and use them to organize the calculation. The active set at a point is a mathematical property of that point; the working set is the algorithm's current selection. They are closely related but need not always be identical, especially with redundant or degenerate constraints.

How it works

In a typical feasible primal method for a quadratic program with linear constraints, start at a feasible point and choose a working set of tight constraints. Compute a search direction by treating those constraints as equalities. Move along that direction until reaching the subproblem solution or another inequality boundary. A newly blocking constraint may join the working set. If the subproblem gives no improving movement, inspect multiplier conditions; a constraint may need to leave the working set to allow further improvement. Stop when feasibility and appropriate optimality conditions hold within tolerances. Dual and other variants organize these steps differently, so this is a representative pattern rather than a universal pseudocode recipe.

Three practical examples

A factory planning model minimizes a quadratic deviation from preferred production quantities while respecting capacity limits and non-negative output.
A constrained least-squares routine holds some coefficients at zero while fitting the others, as in an active-set approach to non-negative least squares.
A controller repeatedly solves related constrained quadratic problems. The previous working set can provide a useful warm start when operating conditions change only slightly.

Think of it this way

Think of moving toward a preferred spot inside a fenced area. Once a fence blocks direct movement, you can search along that boundary until another fence or the best reachable point is encountered. The analogy captures active boundaries, but real optimization can involve thousands of dimensions, equality constraints and numerical degeneracy rather than a simple visible enclosure.

Worked example

Minimize (x − 3)² + (y − 2)² subject to x ≥ 0, y ≥ 0 and x + y ≤ 4. The unconstrained best point, (3, 2), violates the capacity limit because its coordinates sum to 5. Suppose the capacity boundary is in the working set. Substitute y = 4 − x: the objective becomes (x − 3)² + (2 − x)². Differentiating gives 4x − 10 = 0, so x = 2.5 and y = 1.5. The objective is 0.25 + 0.25 = 0.5. Both non-negativity bounds are slack. For the constraint written x + y − 4 ≤ 0, the objective gradient at this point is (−1, −1); adding multiplier 1 times the constraint gradient (1, 1) gives zero. Feasibility and these optimality conditions confirm the unique optimum for this strictly convex problem. This checks the final active set, not a mandatory sequence of solver iterations.

Illustrative case study

In a fictional scheduling project, Bay Workshop adjusts a continuous allocation model every hour. Most capacity limits remain unchanged, so its solver reuses information about the previous working set. A sudden equipment outage changes which limits bind, and the team verifies that the solver can revise that set instead of freezing it. They inspect feasibility residuals and termination status before applying the proposed allocation. The example illustrates warm-start use without claiming a particular runtime improvement or real operational result.

Common misconceptions and mistakes

An active constraint is tight, not violated. A constraint can be tight with a zero multiplier, so tightness alone does not establish a positive marginal value for relaxing it. The optimum need not be a corner: the worked example lies on the interior of an edge. Active-set methods do not generally enumerate every possible constraint subset, and they do not always beat interior-point methods. Global optimality claims depend on the problem class; a nonconvex problem may yield only a local solution or stationary point.

Business use

When comparing solvers, consider the number and structure of constraints, availability of good starting points, repeated-solve patterns and required tolerances. Log the objective, constraint residuals and termination reason rather than accepting a returned vector as automatically optimal. Poor scaling and nearly dependent constraints can make working-set calculations numerically difficult. If a model requires integer decisions, a continuous active-set subproblem solver alone does not enforce integrality. Keep mathematical feasibility separate from whether the model adequately represents the real operation.

Check your understanding

In the worked example, x and y are both positive and x + y equals 4. Which inequality is active?

Answer: The capacity inequality x + y ≤ 4. The lower bounds are inactive because neither variable equals zero. This identifies the tight boundary, not a violated condition.

Related terms

Constrained optimization
Quadratic programming
Interior-point method
KKT conditions
Lagrange multiplier
feasible region

Learn next

change the preferred point in the worked example and determine when the capacity limit stops binding. Then add an upper bound on x and compare the resulting active sets. Observe that the best solution can move between an interior, an edge and a corner.

Sources

Sources: Forsgren, Gill and Wong, Primal and Dual Active-Set Methods for Convex Quadratic Programming, introduction and optimality conditions, https://arxiv.org/pdf/1503.08349 ; Stanford Systems Optimization Laboratory, constrained optimization algorithms, https://web.stanford.edu/group/SOL/research_application_constrained_optimization.html . The numerical problem above is an original convex example.

Previous: Active learning agent Next: Activity Bias