Constrained Optimization & KKTOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

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 f(x)f(x) subject to h(x)=0h(x) = 0.

Introduce the Lagrangian, which folds the constraint into the objective using a scalar Lagrange multiplier λ\lambda (its value, solved for below, measures how hard the constraint pushes back):

L(x,λ)=f(x)+λh(x)\mathcal{L}(x, \lambda) = f(x) + \lambda h(x)

At the constrained optimum x∗x^*, the gradients of ff and hh must be parallel — you cannot move along the constraint surface without increasing ff. Formally:

∇xL=0⟺∇f(x∗)=−λ∇h(x∗)\nabla_x \mathcal{L} = 0 \quad \Longleftrightarrow \quad \nabla f(x^*) = -\lambda \nabla h(x^*)

The scalar λ\lambda (the Lagrange multiplier) measures how much the optimal value of ff would improve if the constraint were relaxed.

Worked example

Minimize f(x,y)=x2+y2f(x, y) = x^2 + y^2 subject to x+y=1x + y = 1.

Form the Lagrangian:

L(x,y,λ)=x2+y2+λ(x+y−1)\mathcal{L}(x, y, \lambda) = x^2 + y^2 + \lambda(x + y - 1)

Stationarity conditions:

∂L∂x=2x+λ=0  ⟹  x=−λ2\frac{\partial \mathcal{L}}{\partial x} = 2x + \lambda = 0 \implies x = -\tfrac{\lambda}{2} ∂L∂y=2y+λ=0  ⟹  y=−λ2\frac{\partial \mathcal{L}}{\partial y} = 2y + \lambda = 0 \implies y = -\tfrac{\lambda}{2} ∂L∂λ=x+y−1=0\frac{\partial \mathcal{L}}{\partial \lambda} = x + y - 1 = 0

From the first two: x=yx = y. Substituting into the constraint: 2x=1  ⟹  x=y=0.52x = 1 \implies x = y = 0.5.

Solution: x∗=y∗=0.5x^* = y^* = 0.5, λ∗=−1\lambda^* = -1, with f(x∗)=0.5f(x^*) = 0.5.

Geometric check: the level curves of f(x,y)=cf(x,y) = c are circles centered at the origin. The constraint is the line x+y=1x+y=1. The smallest circle that touches the line is tangent to it — tangency means ∇f∥∇h\nabla f \parallel \nabla h, exactly the stationarity condition.

Python
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 f(x)f(x) subject to gi(x)≤0g_i(x) \leq 0 for i=1,…,mi = 1, \ldots, m.

Generalize the Lagrangian with dual variables μi≥0\mu_i \geq 0:

L(x,μ)=f(x)+∑i=1mμigi(x)\mathcal{L}(x, \mu) = f(x) + \sum_{i=1}^m \mu_i g_i(x)

The sign of μi\mu_i must be non-negative because we want the Lagrangian penalty to push xx toward the feasible region (where gi≤0g_i \leq 0), not away from it.

Active vs inactive constraints

At the optimum:

  • Active constraint: gi(x∗)=0g_i(x^*) = 0 — the boundary is reached; μi\mu_i can be positive.
  • Inactive constraint: gi(x∗)<0g_i(x^*) < 0 — the constraint is slack; μi=0\mu_i = 0 (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 min⁡xf(x)\min_x f(x) s.t. gi(x)≤0g_i(x) \leq 0, hj(x)=0h_j(x) = 0:

#ConditionMeaning
1∇xf(x∗)+∑iμi∗∇gi(x∗)+∑jλj∗∇hj(x∗)=0\nabla_x f(x^*) + \sum_i \mu_i^* \nabla g_i(x^*) + \sum_j \lambda_j^* \nabla h_j(x^*) = 0Stationarity: gradient of Lagrangian is zero
2gi(x∗)≤0g_i(x^*) \leq 0 for all iiPrimal feasibility: constraints are satisfied
3μi∗≥0\mu_i^* \geq 0 for all iiDual feasibility: dual variables non-negative
4μi∗gi(x∗)=0\mu_i^* g_i(x^*) = 0 for all iiComplementary slackness: inactive constraints have zero multiplier

What the multiplier is worth

unconstrained (3, 2)xconstraint activex + y = 4.000budget b = 4.00optimum(2.500, 1.500)complementary slacknessλ·g(x*) = 0.000000
optimal value0.50000
multiplier1.00000
measured shadow price1.00000
agreementexact

λ 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 (x−3)2+(y−2)2(x-3)^2 + (y-2)^2 inside x+y≤bx + y \le b and watch λ\lambda against a numerical derivative of the optimal value:

bbf∗f^*λ\lambdameasured −df∗/db-\mathrm{d}f^*/\mathrm{d}b
2.04.500003.000003.00000
3.02.000002.000002.00000
4.00.500001.000001.00000
4.50.125000.500000.50000
5.00.000000.000000.00000

Exact at every budget. That is what makes λ\lambda a shadow price rather than an algebraic device: relax the constraint by one unit and the objective improves by λ\lambda. It is the number to quote when someone asks what another unit of budget is worth before you go and negotiate for it.

Push bb past 55 and the unconstrained optimum becomes feasible: λ\lambda drops to exactly 00 and stays there. A constraint that is not binding has no price — complementary slackness happening rather than being stated, and the reason μi∗gi(x∗)=0\mu_i^* g_i(x^*) = 0 is a condition rather than a coincidence. The dashed line from the constrained optimum back to (3,2)(3,2) is ∇f\nabla f, and it stays perpendicular to the active constraint the whole time, which is condition 1 doing its work.

KKT sufficient conditions

For convex ff and convex inequality constraints (convex gig_i, affine hjh_j), 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 −2x−y-2x - y subject to x+y≤4x + y \leq 4, x≤3x \leq 3, y≤3y \leq 3, x,y≥0x, y \geq 0.

Rewrite constraints as gi≤0g_i \leq 0: g1=x+y−4g_1 = x+y-4, g2=x−3g_2 = x-3, g3=y−3g_3 = y-3, g4=−xg_4 = -x, g5=−yg_5 = -y.

The feasible region is a polygon, and a linear objective always attains its optimum at a vertex, so evaluate them all:

VertexObjective −2x−y-2x - yActive constraints
(0,0)(0, 0)00g4,g5g_4, g_5
(3,0)(3, 0)−6-6g2,g5g_2, g_5
(0,3)(0, 3)−3-3g3,g4g_3, g_4
(1,3)(1, 3)−5-5g1,g3g_1, g_3
(3,1)(3, 1)−7\mathbf{-7} ← bestg1,g2g_1, g_2

Optimal point: (3,1)(3, 1), where g1g_1 and g2g_2 are active and the rest are slack. Now verify the KKT conditions there. Stationarity: ∇(−2x−y)=(−2,−1)\nabla(-2x-y) = (-2,-1), so we need μ1⋅(1,1)+μ2⋅(1,0)=(2,1)\mu_1 \cdot (1,1) + \mu_2 \cdot (1,0) = (2,1), giving μ1=1≥0\mu_1 = 1 \geq 0, μ2=1≥0\mu_2 = 1 \geq 0 ✅ (dual feasibility included). Complementary slackness: the slack constraints get zero multipliers, e.g. g3=1−3=−2<0g_3 = 1-3 = -2 < 0 forces μ3=0\mu_3 = 0 ✅. All four conditions hold — (3,1)(3,1) is confirmed optimal.

The SVM dual as KKT

The hard-margin SVM primal:

min⁡w,b12∥w∥2s.t.yi(w⋅xi+b)≥1∀i\min_{w, b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w \cdot x_i + b) \geq 1 \quad \forall i

Write constraints as gi=1−yi(w⋅xi+b)≤0g_i = 1 - y_i(w \cdot x_i + b) \leq 0 and form the Lagrangian:

L(w,b,α)=12∥w∥2−∑i=1nαi[yi(w⋅xi+b)−1]\mathcal{L}(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^n \alpha_i \bigl[y_i(w \cdot x_i + b) - 1\bigr]

with αi≥0\alpha_i \geq 0. Stationarity:

∂L∂w=w−∑iαiyixi=0  ⟹  w=∑iαiyixi\frac{\partial \mathcal{L}}{\partial w} = w - \sum_i \alpha_i y_i x_i = 0 \implies w = \sum_i \alpha_i y_i x_i ∂L∂b=−∑iαiyi=0  ⟹  ∑iαiyi=0\frac{\partial \mathcal{L}}{\partial b} = -\sum_i \alpha_i y_i = 0 \implies \sum_i \alpha_i y_i = 0

Substituting back into L\mathcal{L} eliminates ww and bb, yielding the dual problem:

max⁡α∑i=1nαi−12∑i=1n∑j=1nαiαjyiyj xi⋅xj\max_\alpha \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j\, x_i \cdot x_j s.t.∑iαiyi=0,αi≥0\text{s.t.} \quad \sum_i \alpha_i y_i = 0, \quad \alpha_i \geq 0

KKT complementary slackness:

αi[yi(w⋅xi+b)−1]=0\alpha_i \bigl[y_i(w \cdot x_i + b) - 1\bigr] = 0

This means either αi=0\alpha_i = 0 (the point is not a support vector) or yi(w⋅xi+b)=1y_i(w \cdot x_i + b) = 1 (the point lies exactly on the margin — it is a support vector). The weight vector is determined entirely by the support vectors:

w=∑i: αi>0αiyixiw = \sum_{i:\, \alpha_i > 0} \alpha_i y_i x_i

Why the dual matters

The dual objective depends on data only through inner products xi⋅xjx_i \cdot x_j. Replacing these with a kernel k(xi,xj)k(x_i, x_j) 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:

d∗≤p∗d^* \leq p^*

Strong duality (d∗=p∗d^* = p^*) holds when Slater's condition is satisfied: there exists a strictly feasible point (gi(x)<0g_i(x) < 0 for all inequality constraints).

The hard-margin SVM has nn constraints gi(x)=1−yi(w⋅xi+b)≤0g_i(x) = 1 - y_i(w \cdot x_i + b) \leq 0. Slater's condition holds whenever the data is linearly separable, which is the problem's premise. Therefore:

dSVM∗=pSVM∗d^*_\text{SVM} = p^*_\text{SVM}

Solving the dual is exactly equivalent to solving the primal. The dual is often easier because it has nn variables (αi\alpha_i) with simple box constraints, regardless of the input dimension.

Applications beyond SVM

Elastic net as dual of group lasso. The elastic net penalty λ1∥w∥1+λ22∥w∥2\lambda_1 \|w\|_1 + \frac{\lambda_2}{2}\|w\|^2 can be derived as the dual of a group-sparse regularizer — the Lagrange multiplier connects the two perspectives.

Maximum entropy. Finding the distribution pp that maximizes H(p)=−∑ipilog⁡piH(p) = -\sum_i p_i \log p_i subject to moment constraints ∑ipifk(xi)=μk\sum_i p_i f_k(x_i) = \mu_k is a constrained convex problem. Its KKT conditions give the Gibbs/Boltzmann distribution pi∝exp⁡(−∑kλkfk(xi))p_i \propto \exp(-\sum_k \lambda_k f_k(x_i)).

Portfolio optimization. Markowitz mean-variance: maximize expected return subject to variance ≤σ2\leq \sigma^2 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

  1. Forgetting the sign of μ\mu. For gi≤0g_i \leq 0 constraints, the multiplier must satisfy μi≥0\mu_i \geq 0. Flipping the constraint direction flips the sign requirement.
  2. 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.
  3. Ignoring complementary slackness. This condition is the one that tells you which constraints are active — skipping it leaves the system underdetermined.
  4. 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 L=f+λh\mathcal{L} = f + \lambda h converts equality-constrained problems into unconstrained ones; stationarity means ∇f∥∇h\nabla f \parallel \nabla h at the optimum.
  • Inequality constraints introduce dual variables μi≥0\mu_i \geq 0 with complementary slackness: inactive constraints have μi=0\mu_i = 0.
  • KKT conditions (stationarity, primal feasibility, dual feasibility, slackness) are necessary + sufficient for convex problems.
  • The SVM dual follows directly from KKT: w=∑αiyixiw = \sum \alpha_i y_i x_i; only support vectors (αi>0\alpha_i > 0) matter.
  • Strong duality (Slater's condition) guarantees solving the dual is equivalent to solving the primal.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelated
Constrained Optimization & KKTCalculus for MLNeural NetworksMaximum Margin Classifica…The Kernel TrickConvex Optimization