Constrained Optimization & KKT
Most real ML problems are not unconstrained. SVMs enforce a margin, portfolio optimizers cap risk, and max-entropy models must respect probability normalization. The Lagrangian framework converts constrained problems into unconstrained ones, and KKT conditions tell you exactly when you've found the solution.
Equality constraints: Lagrangians
Problem: minimize subject to .
Introduce the Lagrangian, which folds the constraint into the objective using a scalar Lagrange multiplier (its value, solved for below, measures how hard the constraint pushes back):
At the constrained optimum , the gradients of and must be parallel — you cannot move along the constraint surface without increasing . Formally:
The scalar (the Lagrange multiplier) measures how much the optimal value of would improve if the constraint were relaxed.
Worked example
Minimize subject to .
Form the Lagrangian:
Stationarity conditions:
From the first two: . Substituting into the constraint: .
Solution: , , with .
Geometric check: the level curves of are circles centered at the origin. The constraint is the line . The smallest circle that touches the line is tangent to it — tangency means , exactly the stationarity condition.
from scipy.optimize import minimize
import numpy as np
# scipy verification
res = minimize(
fun=lambda v: v[0]**2 + v[1]**2,
x0=[0.0, 0.0],
constraints={'type': 'eq', 'fun': lambda v: v[0] + v[1] - 1}
)
print(f"x* = {res.x.round(4)}, f* = {res.fun:.4f}")
# x* = [0.5, 0.5], f* = 0.5
Inequality constraints
Problem: minimize subject to for .
Generalize the Lagrangian with dual variables :
The sign of must be non-negative because we want the Lagrangian penalty to push toward the feasible region (where ), not away from it.
Active vs inactive constraints
At the optimum:
- Active constraint: — the boundary is reached; can be positive.
- Inactive constraint: — the constraint is slack; (it doesn't bind).
This "on/off" behavior is captured by the complementary slackness condition.
KKT conditions
The Karush-Kuhn-Tucker (KKT) conditions are necessary (and under convexity, sufficient) for optimality. For the problem s.t. , :
| # | Condition | Meaning |
|---|---|---|
| 1 | Stationarity: gradient of Lagrangian is zero | |
| 2 | for all | Primal feasibility: constraints are satisfied |
| 3 | for all | Dual feasibility: dual variables non-negative |
| 4 | for all | Complementary slackness: inactive constraints have zero multiplier |
What the multiplier is worth
λ and the measured −df*/db agree at every budget, which is what “shadow price” means: relax the constraint by one unit and the objective improves by λ. Push b past 5 and the unconstrained optimum becomes feasible — λ drops to exactly 0 and stays there. A constraint that is not binding has no price, which is complementary slackness happening rather than being stated.
Minimise (x−3)² + (y−2)² inside the shaded feasible region x + y ≤ b, x, y ≥ 0. Rings are level sets of the objective; the white dot is the unconstrained optimum and the teal dot the constrained one. λ is read off the closed-form solution, and −df*/db beside it is a numerical derivative of the optimal value.
Condition 4 is the one that reads like bookkeeping and is actually the interesting one. Minimise inside and watch against a numerical derivative of the optimal value:
| measured | |||
|---|---|---|---|
| 2.0 | 4.50000 | 3.00000 | 3.00000 |
| 3.0 | 2.00000 | 2.00000 | 2.00000 |
| 4.0 | 0.50000 | 1.00000 | 1.00000 |
| 4.5 | 0.12500 | 0.50000 | 0.50000 |
| 5.0 | 0.00000 | 0.00000 | 0.00000 |
Exact at every budget. That is what makes a shadow price rather than an algebraic device: relax the constraint by one unit and the objective improves by . It is the number to quote when someone asks what another unit of budget is worth before you go and negotiate for it.
Push past and the unconstrained optimum becomes feasible: drops to exactly and stays there. A constraint that is not binding has no price — complementary slackness happening rather than being stated, and the reason is a condition rather than a coincidence. The dashed line from the constrained optimum back to is , and it stays perpendicular to the active constraint the whole time, which is condition 1 doing its work.
KKT sufficient conditions
For convex and convex inequality constraints (convex , affine ), the KKT conditions are also sufficient for global optimality. This is why the SVM dual derivation is exact — the primal SVM is convex.
Worked example: a linear program (LP)
Minimize subject to , , , .
Rewrite constraints as : , , , , .
The feasible region is a polygon, and a linear objective always attains its optimum at a vertex, so evaluate them all:
| Vertex | Objective | Active constraints |
|---|---|---|
| ← best |
Optimal point: , where and are active and the rest are slack. Now verify the KKT conditions there. Stationarity: , so we need , giving , ✅ (dual feasibility included). Complementary slackness: the slack constraints get zero multipliers, e.g. forces ✅. All four conditions hold — is confirmed optimal.
The SVM dual as KKT
The hard-margin SVM primal:
Write constraints as and form the Lagrangian:
with . Stationarity:
Substituting back into eliminates and , yielding the dual problem:
KKT complementary slackness:
This means either (the point is not a support vector) or (the point lies exactly on the margin — it is a support vector). The weight vector is determined entirely by the support vectors:
Why the dual matters
The dual objective depends on data only through inner products . Replacing these with a kernel extends SVMs to non-linear boundaries without ever computing high-dimensional feature maps — the kernel trick.
Duality gap
The weak duality theorem says the dual optimal value is always ≤ the primal optimal value:
Strong duality () holds when Slater's condition is satisfied: there exists a strictly feasible point ( for all inequality constraints).
The hard-margin SVM has constraints . Slater's condition holds whenever the data is linearly separable, which is the problem's premise. Therefore:
Solving the dual is exactly equivalent to solving the primal. The dual is often easier because it has variables () with simple box constraints, regardless of the input dimension.
Applications beyond SVM
Elastic net as dual of group lasso. The elastic net penalty can be derived as the dual of a group-sparse regularizer — the Lagrange multiplier connects the two perspectives.
Maximum entropy. Finding the distribution that maximizes subject to moment constraints is a constrained convex problem. Its KKT conditions give the Gibbs/Boltzmann distribution .
Portfolio optimization. Markowitz mean-variance: maximize expected return subject to variance and weights summing to 1. KKT gives the efficient frontier in closed form.
Exercise
At a constrained optimum, the Lagrange condition ∇f(x*) = λ∇g(x*) says what geometrically?
Need a hint?
The gradient of a function at a point is perpendicular to its level curves.
Exercise
KKT complementary slackness: μᵢ·gᵢ(x*) = 0 for each inequality constraint gᵢ(x) ≤ 0. If μᵢ > 0 at the solution, what does this imply about the constraint?
Need a hint?
If the product is zero and one factor is non-zero, what must the other be?
Exercise
In the SVM dual, why do only support vectors (points on the margin boundary) have non-zero dual variables αᵢ?
Need a hint?
Apply complementary slackness to the SVM margin constraints.
Common mistakes
- Forgetting the sign of . For constraints, the multiplier must satisfy . Flipping the constraint direction flips the sign requirement.
- Applying KKT to non-convex problems. KKT conditions are necessary for any smooth optimum, but only sufficient under convexity. A non-convex problem can satisfy KKT at a saddle point or local minimum that is not global.
- Ignoring complementary slackness. This condition is the one that tells you which constraints are active — skipping it leaves the system underdetermined.
- Assuming strong duality always holds. Slater's condition is the most common check. Without it (e.g., constraints that only touch but never strictly satisfy), the duality gap may be positive.
Key takeaways
- The Lagrangian converts equality-constrained problems into unconstrained ones; stationarity means at the optimum.
- Inequality constraints introduce dual variables with complementary slackness: inactive constraints have .
- KKT conditions (stationarity, primal feasibility, dual feasibility, slackness) are necessary + sufficient for convex problems.
- The SVM dual follows directly from KKT: ; only support vectors () matter.
- Strong duality (Slater's condition) guarantees solving the dual is equivalent to solving the primal.
Related concepts
- Maximum Margin Classification: the SVM primal and support vectors
- Convex Optimization: why convexity makes KKT sufficient