Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 38 · Constrained Optimization and Lagrange

Inequality Constraints and Active Sets

Handle constraints of the form g(x) ≤ 0: active versus inactive, sign rules for multipliers and complementary slackness, with a brute-force active-set solver.

Equality constraints force you onto a curve. Inequality constraints only fence you in: you may be strictly inside the region or exactly on its boundary. The question "which fences actually matter at the solution?" is the heart of constrained optimization, and answering it leads to the famous KKT conditions in chapter 5. This lesson builds the intuition.

Two cases for each constraint

Consider minimize f(x) subject to g(x) ≤ 0. At the optimum x* there are exactly two possibilities.

  1. Inactive. g(x*) < 0. The solution is strictly inside the region. The constraint is irrelevant locally, as if it were not there, so x* is an ordinary unconstrained minimizer: ∇f(x*) = 0.
  2. Active. g(x*) = 0. The solution sits on the boundary. Locally this acts like an equality constraint, but with a sign restriction: the gradient of f must push into the wall, not pull away from it.

The sign restriction is the new ingredient. With the Lagrangian L = f + μ g, the conditions at an active boundary are

Text
∇f(x*) + μ ∇g(x*) = 0,    with  μ ≥ 0

A non-negative μ means: the negative gradient (the downhill direction) points outward, through the wall, so the wall is what stops you. If μ came out negative, the downhill direction would point into the feasible region and you could still improve by moving away from the wall; then the constraint was not truly active.

Complementary slackness

Both cases can be written with one equation:

Text
μ · g(x*) = 0

Either the multiplier is zero (inactive) or the constraint holds with equality (active). This is complementary slackness.

Example: a constraint that matters, and one that does not

Minimize f(x) = (x - 3)² subject to x ≤ 5. The unconstrained minimum x = 3 satisfies x ≤ 5, so the constraint is inactive and μ = 0. Now change it to x ≤ 1. The unconstrained minimum is infeasible, the solution is the boundary x* = 1, and at it f'(1) = -4. The condition f' + μg' = -4 + μ·1 = 0 gives μ = 4 ≥ 0.

Python Active and inactive constraints

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The product μ·g is zero in every row, and the multiplier grows as the wall is pushed deeper into the wanted region: tightening the constraint costs more.

Several constraints: the active-set idea

With many inequalities the difficulty is combinatorial: you must guess which subset is active. Once you guess a set S, you solve an equality-constrained problem with only the constraints in S, using the method of the previous lesson. Then verify two things: the solution is feasible for the unused constraints, and all multipliers are ≥ 0.

For a small problem you can simply try every subset. Take: minimize (x - 3)² + (y - 2)² subject to x + y ≤ 4, x ≥ 0, y ≥ 0. Write the constraints as A z ≤ b.

Python A brute-force active-set solver

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note the sign convention: with L = f + μᵀ(Az - b) and stationarity ∇f + Aᵀμ = 0, the solver above writes 2(z - target) + Aₛᵀμ = 0, which matches. Only the correct active set survives both tests. The surviving set is the single constraint x + y ≤ 4 with multiplier 1, and the answer (2.5, 1.5) agrees with the geometric result from the first chapter.

A picture of the situation

Python Level curves meeting a wall

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best level curve that still touches the feasible triangle is the circle through (2.5, 1.5), which just kisses the wall x + y = 4.

Summary of the sign rules

Case Condition Multiplier
Inactive g(x*) < 0 ∇f(x*) = 0 locally μ = 0
Active g(x*) = 0 ∇f + μ∇g = 0 μ ≥ 0

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A constraint g(x) ≤ 0 is inactive at x* when

    Strictly inside the region, the constraint does not touch the solution.
  2. 2. Complementary slackness says

    Either the multiplier is zero or the constraint is tight.
  3. 3. For an inequality constraint at an active boundary, the multiplier must satisfy

    A non-negative multiplier means the wall is what prevents further decrease of f.
  4. 4. The active-set method

    Correct guesses pass both checks; wrong guesses fail one of them.

Summary

  • Each inequality constraint is either inactive (multiplier 0) or active (a boundary that acts like an equality).
  • At an active constraint the multiplier must be non-negative.
  • Complementary slackness μ g(x*) = 0 captures both cases.
  • Active-set methods search for the right set of tight constraints.

Next: Projected Gradient Descent