Unconstrained optimisation asks "where is the lowest point?". Constrained optimisation asks "where is the lowest point within the allowed region?". Probabilities must sum to one; an SVM's points must lie outside the margin; a fair classifier must satisfy fairness constraints. Lagrange multipliers and the Karush–Kuhn–Tucker (KKT) conditions are the tools, and duality theory reveals hidden structure — such as the support vectors of an SVM.
Equality constraints#
Minimise $f(\mathbf{x})$ subject to $h(\mathbf{x}) = 0$. At the optimum, you cannot move along the constraint surface and decrease $f$. That means $\nabla f$ has no component along the surface — it must be parallel to the constraint normal $\nabla h$:
for some scalar $\lambda$, the Lagrange multiplier. We package this with the Lagrangian:
and find its stationary points: $\nabla_{\mathbf{x}}\mathcal{L} = \mathbf{0}$ and $\partial\mathcal{L}/\partial\lambda = h(\mathbf{x}) = 0$.
Interpretation of $\lambda$#
The multiplier measures the sensitivity of the optimal value to the constraint: if the constraint is relaxed to $h(\mathbf{x}) = \epsilon$, the optimal value changes by approximately $-\lambda\epsilon$. In economics it is a "shadow price".
Inequality constraints and KKT#
Now minimise $f(\mathbf{x})$ subject to $g_i(\mathbf{x}) \le 0$ for $i = 1, \dots, m$ and $h_j(\mathbf{x}) = 0$. The Lagrangian is
The KKT conditions at an optimum $\mathbf{x}^*$ (under mild regularity conditions) are:
- Stationarity: $\nabla f(\mathbf{x}^*) + \sum_i \alpha_i\nabla g_i(\mathbf{x}^*) + \sum_j \lambda_j\nabla h_j(\mathbf{x}^*) = \mathbf{0}$.
- Primal feasibility: $g_i(\mathbf{x}^*) \le 0$, $h_j(\mathbf{x}^*) = 0$.
- Dual feasibility: $\alpha_i \ge 0$.
- Complementary slackness: $\alpha_i\,g_i(\mathbf{x}^*) = 0$ for every $i$.
Complementary slackness is the elegant part: for each inequality, either the constraint is active ($g_i = 0$, the solution sits on the boundary) or its multiplier is zero (the constraint does not matter). For convex problems, the KKT conditions are both necessary and sufficient.
Duality#
Define the dual function by minimising the Lagrangian over $\mathbf{x}$:
For any $\boldsymbol{\alpha} \ge 0$, $d \le f^*$ — the dual gives a lower bound (weak duality). The dual problem maximises this bound. For convex problems satisfying Slater's condition (a strictly feasible point exists), strong duality holds: the dual optimum equals the primal optimum.
The dual can be easier to solve, and it often exposes structure.
The payoff: support vector machines#
The hard-margin SVM solves
Forming the Lagrangian with multipliers $\alpha_i \ge 0$ and applying stationarity gives
Substituting back yields the dual:
Two profound consequences:
- By complementary slackness, $\alpha_i > 0$ only for points on the margin — the support vectors. The solution depends only on them.
- The data appear only through dot products $\mathbf{x}_i^\top\mathbf{x}_j$. Replace them with a kernel $k(\mathbf{x}_i, \mathbf{x}_j)$ and you get non-linear SVMs for free — the kernel trick.
import numpy as np
from sklearn.svm import SVC
rng = np.random.default_rng(0)
X = np.vstack([rng.normal([-2, -2], 1, (50, 2)), rng.normal([2, 2], 1, (50, 2))])
y = np.array([-1] * 50 + [1] * 50)
clf = SVC(kernel="linear", C=1e3).fit(X, y)
print("number of support vectors:", clf.n_support_) # only a handful
w_from_dual = (clf.dual_coef_ @ clf.support_vectors_).ravel()
print(np.allclose(w_from_dual, clf.coef_.ravel())) # w = sum alpha_i y_i x_iConstraints in modern ML#
- Probability simplex constraints appear in attention, mixtures and optimal transport.
- Norm-ball constraints define adversarial perturbations ($\|\boldsymbol{\delta}\|_\infty \le \epsilon$); projected gradient descent handles them by projecting after each step.
- Trust regions in reinforcement learning (TRPO) constrain policy change with a KL-divergence constraint, solved via Lagrangian methods; PPO approximates this with clipping.
- Fairness constraints can be imposed with Lagrangian (min–max) training.