Constrained optimization: from Lagrange to KKT · Advanced Calculus Topics

§10.7's Lagrange multipliers optimized a function subject to an equality constraint, g(x,y)=c — a curve to stay exactly on. Real optimization problems, including the support vector machines that motivated much of this theory, more often need inequality constraints — a region to stay within, not a curve to stay on. This closing lesson of the module extends Lagrange's method to inequalities, adding exactly one new idea: complementary slackness.

The constrained problem

$\text{minimize }f(x)\quad\text{subject to}\quad g(x)\le0$

Two genuinely different situations can occur at the true minimum:

Case 1: the constraint is inactive. If the unconstrained minimum of f already satisfies g(x)\le0, the constraint changes nothing — the constrained and unconstrained minima coincide, and the boundary g(x)=0 plays no role at all.

Case 2: the constraint is active. If the unconstrained minimum violates g(x)\le0, the constrained minimum gets pushed to sit exactly on the boundary, g(x)=0 — at that point, the problem reduces to §10.7's equality-constrained Lagrange multipliers exactly, since the optimal point genuinely lives on that boundary curve.

The KKT conditions

The Karush-Kuhn-Tucker (KKT) conditions unify both cases into one system, using a multiplier \mu\ge0 (the direct inequality-constraint analogue of §10.7's \lambda):

Stationarity: \nabla f+\mu\nabla g=\vec0 — the same parallel-gradients condition as §10.7's Lagrange multipliers.
Primal feasibility: g(x)\le0 — the solution must actually satisfy the original constraint.
Dual feasibility: \mu\ge0 — a genuinely new requirement, absent from equality-constrained Lagrange multipliers, discussed below.
Complementary slackness: \mu\cdot g(x)=0 — either \mu=0 (Case 1: the constraint is inactive, "slack") or g(x)=0 (Case 2: the constraint is active, "tight"), or both.

Complementary slackness is the single new idea this lesson adds. It encodes both cases from above in one equation: if the constraint isn't binding at the optimum (g(x)<0, strictly inside the feasible region), its multiplier must be exactly 0 — that constraint contributed nothing to pushing the solution around, so it shouldn't appear in the stationarity condition at all; if the multiplier is nonzero, the constraint must be exactly tight.

Why \mu\ge0

For an equality constraint, \lambda can have either sign — the boundary can be approached from either side. For an inequality g(x)\le0, the constraint only pushes the solution back in one direction — away from the infeasible side (g(x)>0) — so its multiplier is restricted to be nonnegative, ensuring \nabla f=-\mu\nabla g points into the feasible region rather than out of it. This sign restriction is exactly the extra structure that distinguishes an inequality constraint from an equality one.

Doing it in Python

Minimizing f(x,y)=x^2+y^2 subject to x+y\ge2 (written as g(x,y)=2-x-y\le0) — the unconstrained minimum (0,0) violates the constraint (0+0=0<2), so the constraint must be active:

import sympy as sp

x, y, mu = sp.symbols('x y mu')
f = x**2 + y**2
g = 2 - x - y   # constraint: g <= 0, i.e. x+y >= 2

f_x, f_y = sp.diff(f, x), sp.diff(f, y)
g_x, g_y = sp.diff(g, x), sp.diff(g, y)

# assume the constraint is active (Case 2): solve stationarity + g=0
system = [sp.Eq(f_x + mu*g_x, 0), sp.Eq(f_y + mu*g_y, 0), sp.Eq(g, 0)]
solution = sp.solve(system, [x, y, mu])
print(f"solution: {solution}")
print(f"mu >= 0 (dual feasibility): {solution[mu] >= 0}")

f_at_solution = f.subs({x: solution[x], y: solution[y]})
print(f"minimum value: {f_at_solution}")

Confirming the inactive-constraint case: the same f, but a constraint the unconstrained minimum already satisfies:

import sympy as sp

x, y = sp.symbols('x y')
f = x**2 + y**2

# constraint: x + y >= -2, i.e. g(x,y) = -2-x-y <= 0
unconstrained_min = (0, 0)
g_value = -2 - unconstrained_min[0] - unconstrained_min[1]
print(f"g at the unconstrained minimum = {g_value}")
print(f"constraint satisfied (g <= 0): {g_value <= 0}")
print("constraint is inactive -- mu=0, and the unconstrained minimum IS the constrained minimum")

Verifying complementary slackness holds at the active-constraint solution found above:

import sympy as sp

x_val, y_val, mu_val = 1, 1, 2
g_val = 2 - x_val - y_val

print(f"g(x,y) at solution = {g_val}")
print(f"mu = {mu_val}")
print(f"mu * g(x,y) = {mu_val * g_val}   (complementary slackness: should be 0)")

Worked example

Minimize f(x,y)=x^2+y^2 subject to x+y\ge2.

Write the constraint as g(x,y)=2-x-y\le0.

Check whether the constraint is active: the unconstrained minimum of f is at (0,0) (where \nabla f=\vec0), but g(0,0)=2-0-0=2>0 — violates the constraint. So the constraint must be active: g(x,y)=0, i.e. x+y=2.

Stationarity: \nabla f=\langle2x,2y\rangle, \nabla g=\langle-1,-1\rangle.

$\langle2x,2y\rangle+\mu\langle-1,-1\rangle=\vec0\ \Longrightarrow\ 2x=\mu,\ 2y=\mu\ \Longrightarrow\ x=y$

Combined with x+y=2: x=y=1.

$\mu=2x=2$

Check dual feasibility: \mu=2\ge0 ✓.

$\boxed{(x,y)=(1,1),\qquad f(1,1)=2}$

Sanity check. The unconstrained minimum f(0,0)=0 is smaller, but infeasible; the constrained minimum f(1,1)=2 is the smallest value f can achieve while staying in the feasible region x+y\ge2 — and geometrically, (1,1) is exactly the point on the line x+y=2 closest to the origin (§9.3's projection idea: the closest point on a line to an external point lies along the perpendicular), which is precisely what minimizing x^2+y^2 (squared distance from the origin) subject to that line should produce. The positive multiplier \mu=2 confirms the constraint is genuinely pushing the solution outward, away from the unconstrained (infeasible) minimum. ✓

Your turn

1. Minimize f(x,y)=x^2+y^2 subject to x+y\ge-5. Without solving the full system, determine whether the constraint is active or inactive (check the unconstrained minimum first).

2. Minimize f(x)=(x-3)^2 subject to x\le1 (a one-variable problem — find the unconstrained minimum first, then decide whether the constraint binds).

3. True or false: complementary slackness, \mu\cdot g(x)=0, means \mu and g(x) must both be zero simultaneously.

Solutions

1. Unconstrained minimum: (0,0), where g(0,0)=-5-0-0=-5\le0 — satisfies the constraint already.

$\boxed{\text{inactive; }\mu=0\text{; the constrained minimum is just }(0,0),\ f=0}$

2. Unconstrained minimum of (x-3)^2 is at x=3 (where f'=0), but 3\le1 is false — infeasible. So the constraint is active: x=1.

$\boxed{\text{constrained minimum: }x=1,\ f(1)=(1-3)^2=4}$

(Confirm dual feasibility: f'(x)=2(x-3), g(x)=x-1, g'(x)=1. Stationarity: 2(x-3)+\mu(1)=0 at x=1: 2(-2)+\mu=0\Rightarrow\mu=4\ge0 ✓.)

3. False. Complementary slackness requires their product to be zero, which happens whenever at least one of them is zero — not necessarily both simultaneously. The two cases are: \mu=0 (with g(x) possibly nonzero, specifically negative — an inactive constraint) or g(x)=0 (with \mu possibly nonzero, specifically positive — an active constraint). Both being zero at once is a boundary edge case, not the general rule.

Check yourself in code

Minimize f(x,y)=x^2+y^2 subject to x+y\ge2 using the KKT conditions (assuming the constraint is active).

Print exactly this:

solution: {mu: 2, x: 1, y: 1}
minimum value: 2

import sympy as sp

x, y, mu = sp.symbols('x y mu')
f = x**2 + y**2
g = 2 - x - y

f_x, f_y = sp.diff(f, x), sp.diff(f, y)
g_x, g_y = sp.diff(g, x), sp.diff(g, y)

system = [sp.Eq(f_x + mu*g_x, 0), sp.Eq(f_y + mu*g_y, 0), sp.Eq(g, 0)]
solution = sp.solve(system, [x, y, mu])
print("solution: ...")

f_at_solution = f.subs({x: solution[x], y: solution[y]})
print("minimum value: ...")

import sympy as sp

x, y, mu = sp.symbols('x y mu')
f = x**2 + y**2
g = 2 - x - y

f_x, f_y = sp.diff(f, x), sp.diff(f, y)
g_x, g_y = sp.diff(g, x), sp.diff(g, y)

system = [sp.Eq(f_x + mu*g_x, 0), sp.Eq(f_y + mu*g_y, 0), sp.Eq(g, 0)]
solution = sp.solve(system, [x, y, mu])
print(f"solution: {solution}")

f_at_solution = f.subs({x: solution[x], y: solution[y]})
print(f"minimum value: {f_at_solution}")

The KKT conditions extend §10.7's Lagrange multipliers from equality to inequality constraints by adding complementary slackness, \mu\cdot g(x)=0: either the constraint is inactive (\mu=0, and the unconstrained minimum already satisfies it) or active (g(x)=0, and the problem reduces to an ordinary equality-constrained Lagrange problem with the extra requirement \mu\ge0, ensuring the constraint pushes the solution the correct direction). This framework — checking whether the unconstrained optimum is already feasible, and solving on the boundary when it isn't — is exactly the mathematics underlying support vector machines and much of convex optimization theory.

That closes this module's tour of the calculus underneath machine learning — gradient descent, convexity, Jacobians and Hessians, backpropagation, automatic differentiation, matrix calculus, and constrained optimization, all built directly on Modules 2–4 and 10. Next, and last: a step back from applications entirely, to the rigorous foundations — limits, continuity, and completeness — that this whole course has been resting on since Module 1.

17. Constrained optimization: from Lagrange to KKT