Constrained Optimization & Duality
Lagrange multipliers, KKT conditions, and weak/strong duality — the SVM's engine.
On this page
Beginner: a constrained optimization problem asks you to minimize something subject to rules you're not allowed to break — "minimize cost, subject to using at least this much material." Lagrange multipliers are a trick for turning such a problem into an easier-to-analyze unconstrained one, by attaching a "price" to each constraint.
Intermediate: the geometric intuition for an equality constraint is concrete: at the constrained optimum, the gradient of the objective must be parallel to the gradient of the constraint. If it weren't, you could slide a little along the constraint surface and keep improving the objective — so "parallel gradients" is the only way to be genuinely stuck.
Advanced: for inequality constraints, this generalizes into the KKT (Karush-Kuhn-Tucker) conditions — primal feasibility, dual feasibility, complementary slackness, and the same stationarity/parallel-gradient condition — which together characterize an optimum. This sets up the dual problem, built from the same Lagrangian, and a crucial practical distinction: weak duality always holds (the dual always gives a valid lower bound on the primal optimum), while strong duality (the dual exactly equals the primal — zero gap) holds only under extra conditions, typically convexity plus a mild feasibility regularity condition (Slater's condition). When strong duality holds, solving the dual gives you the exact primal answer — and this is precisely the machinery the SVM module later in this chapter is built on.
The Lagrangian for "minimize f(x) subject to gᵢ(x) ≤ 0 and hⱼ(x) = 0," and weak duality — the dual function is always a lower bound on the true constrained optimum.
Part 1 — closest point on a line to the origin. Minimize f(x,y) = x²+y² subject to x+y=1. Form the Lagrangian ℒ(x,y,ν) = x²+y²+ν(x+y−1) and set every partial derivative to zero:
The first two give x = y = −ν/2. Substituting into the third, −ν/2 − ν/2 − 1 = 0 ⟹ ν = −1, so x = y = 1/2. This matches the obvious geometric answer — the closest point on the line to the origin — as a sanity check that the machinery works.
Part 2 — weak duality, in general. For any point x that satisfies the constraints (feasible) and any λ ≥ 0:
This holds because λᵢgᵢ(x) ≤ 0 (feasibility gives gᵢ(x)≤0, and λᵢ≥0, so their product is ≤ 0), and νⱼhⱼ(x) = 0 exactly (since hⱼ(x)=0 for a feasible point). Now take the minimum over ALL x′ (not just the feasible one we picked):
Since this chain holds for every feasible x, it holds in particular for the true optimum x*: d(λ,ν) ≤ f(x*) — the dual function value is always a valid lower bound on the true constrained minimum, for any choice of λ≥0. This is weak duality, and the proof used nothing beyond the sign of λᵢgᵢ(x) and the definition of a minimum.
Where this is used: this is exactly the machinery behind SVM training (a later module in this chapter). The SVM's margin-maximization problem is convex and satisfies Slater's condition, so strong duality holds — which is why SVMs are trained by solving the DUAL problem instead of the original primal formulation, and why "support vectors" turn out to be exactly the training points with nonzero Lagrange multipliers: complementary slackness is precisely why every other point ends up with a multiplier of exactly zero.
Drag the red point along the green constraint line and watch the blue (objective gradient) and green (constraint normal) arrows — they point in the same direction only at (0.5, 0.5), exactly where the derivation says they must.
import numpy as np
# Part 1: solve the 3x3 linear system from the Lagrange-multiplier derivation
# (2x + nu = 0, 2y + nu = 0, x + y - 1 = 0) for [x, y, nu].
A = np.array([
[2, 0, 1],
[0, 2, 1],
[1, 1, 0],
], dtype=float)
b = np.array([0, 0, 1], dtype=float)
x, y, nu = np.linalg.solve(A, b)
print(f"x={x:.3f} y={y:.3f} nu={nu:.3f} (expect x=y=0.5)")
print("constraint satisfied:", np.isclose(x + y, 1.0))
# Part 2: numerically verify weak duality for minimize x^2 subject to x >= 1,
# i.e. g(x) = 1 - x <= 0. The Lagrangian is L(x, lam) = x^2 + lam*(1-x).
# Minimizing over x for fixed lam: dL/dx = 2x - lam = 0 => x = lam/2.
def dual(lam):
x_star = lam / 2
return x_star ** 2 + lam * (1 - x_star)
true_optimum = 1.0 # the true constrained minimum of x^2 s.t. x>=1 is at x=1, f=1
for lam in [0.0, 0.5, 1.0, 1.5, 2.0, 3.0]:
d = dual(lam)
print(f"lambda={lam:.1f} dual={d:.3f} <= true optimum {true_optimum}? {d <= true_optimum + 1e-9}")- Support Vector Machines (a later module) train by solving a convex constrained QP via its dual — the flagship real use of everything derived in this lesson.
- Portfolio optimization in finance: minimize risk subject to a minimum expected return and a budget constraint — a classical constrained quadratic program.
- Resource allocation problems throughout operations research are almost always posed and solved exactly this way.
- Physics-informed optimization enforces conservation laws (energy, mass, momentum) as hard equality constraints using this same Lagrangian machinery.
- Regularization as an implicit constraint: ridge regression's L2 penalty (Module 1's MLE/MAP lesson) can be shown, via duality, to be equivalent to a hard constraint
‖θ‖² ≤ tfor a matchingt— a satisfying full-circle connection back to the very first module of this chapter.
- Assuming strong duality holds for every optimization problem — it's specifically a convexity-plus-regularity result; non-convex problems can have a real, nonzero duality gap where the dual severely underestimates the true optimum.
- Misreading complementary slackness: a nonzero multiplier means its constraint is active (binding) at the optimum; a zero multiplier means it isn't — getting this backwards leads to misreading which constraints actually matter.
- Treating KKT conditions as sufficient for optimality in a general non-convex problem — they're only guaranteed to be necessary there. Sufficiency requires convexity (the previous module's Convex Optimization Basics lesson).
Going deeper
The duality gap — the primal optimal value minus the dual optimal value — is itself a useful practical quantity even outside pure theory. Many convex solvers use it as a natural, certifiable stopping criterion: stop once the gap is provably below some tolerance, which gives a guaranteed bound on how far the current solution is from optimal — something first-order methods without duality generally can't offer as cleanly.
In the diagram, why do the objective-gradient and constraint-normal arrows only point in the same direction at exactly one spot on the line?
Because the stationarity condition of the Lagrangian requires ∇f(x) to be a scalar multiple of the constraint's gradient — the two must be parallel. Anywhere else on the line, moving a little further along the line would still change f(x), meaning you haven't reached a point where the constraint direction is 'orthogonal to further improvement' — so you're not yet at a critical point of the constrained problem. Only at (0.5, 0.5) does sliding along the line in either direction fail to decrease x²+y² any further.
Lagrange multipliers and duality turn "minimize subject to these rules" into a related, often more tractable, unconstrained problem, with a provable (weak duality) or exact (strong duality, under convexity) relationship between the two. The next and final lesson of this module, EM as optimization, tackles a different obstacle entirely — an objective that's hard to maximize directly because of a hidden variable, not because of a constraint.