Week 12: Duality for Practitioners

Lagrangian#

Consider a convex optimisation problem with inequality constraints:

$\min_{x} \; f(x) \quad \text{subject to} \quad h_i(x) \leq 0, \; i = 1, \ldots, m$

The Lagrangian combines the objective and the constraints with Lagrange multipliers $\lambda_i \geq 0$:

$L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i h_i(x)$

where $\lambda \in \mathbb{R}^m$, $\lambda \geq 0$ (elementwise). The multipliers penalise constraint violations: if $h_i(x) > 0$, the term $\lambda_i h_i(x)$ adds a positive penalty.

The primal problem can be rewritten as:

$\min_{x} \max_{\lambda \geq 0} L(x, \lambda)$

If $x$ violates any constraint ($h_i(x) > 0$), the inner max drives $L \to \infty$ by letting $\lambda_i \to \infty$. If $x$ is feasible (all $h_i(x) \leq 0$), the max over $\lambda$ sets each $\lambda_i = 0$ or keeps it at the boundary, recovering $f(x)$. So $\max_{\lambda \geq 0} L(x, \lambda)$ equals $f(x)$ when $x$ is feasible and $+\infty$ otherwise.

Dual Function#

The Lagrange dual function is obtained by swapping min and max:

$g(\lambda) = \min_{x} L(x, \lambda) = \min_{x} \left[ f(x) + \sum_i \lambda_i h_i(x) \right]$

For each fixed $\lambda \geq 0$, $g(\lambda)$ is the minimum of an unconstrained (but $\lambda$-parametrised) problem. The domain of $g$ is $\{\lambda \geq 0 \mid g(\lambda) > -\infty\}$.

The dual problem is to maximise the dual function:

$\max_{\lambda \geq 0} \; g(\lambda)$

Worked example — 1D quadratic with constraint:

$\min_x \; \frac{1}{2}x^2$ subject to $x \geq 1$ (rewritten as $1 - x \leq 0$).

Lagrangian: $L(x, \lambda) = \frac{1}{2}x^2 + \lambda(1 - x)$, $\lambda \geq 0$.

Dual function: $\min_x L(x, \lambda)$. Set $\frac{\partial L}{\partial x} = x - \lambda = 0 \implies x = \lambda$. Substitute: $g(\lambda) = \frac{1}{2}\lambda^2 + \lambda(1 - \lambda) = \lambda - \frac{1}{2}\lambda^2$.

Dual problem: $\max_{\lambda \geq 0} (\lambda - \frac{1}{2}\lambda^2)$. Set derivative to zero: $1 - \lambda = 0 \implies \lambda^* = 1$. Dual value: $g(1) = 1 - 0.5 = 0.5$. Primal optimum: $x^* = 1$, $f(1) = 0.5$. Duality gap: $0$.

Weak and Strong Duality#

Weak duality: For any feasible $x$ and any $\lambda \geq 0$,

$g(\lambda) \leq f(x)$

The dual function always lower-bounds the primal objective. Maximising $g$ gives the best possible lower bound. The duality gap $f(x^*) - g(\lambda^*)$ is always nonnegative.

Strong duality: Under certain conditions, $f(x^*) = g(\lambda^*)$ — the duality gap is zero. For convex problems, Slater's condition is sufficient: if there exists a strictly feasible point (all $h_i(x) < 0$), then strong duality holds.

In practice, most convex ML problems satisfy Slater's condition trivially. Strong duality means we can solve either the primal or the dual and get the same answer — whichever is easier.

Complementary Slackness#

At the primal-dual optimum $(x^*, \lambda^*)$ with strong duality:

$\lambda_i^* \, h_i(x^*) = 0 \quad \text{for all } i$

This is complementary slackness. For each constraint:

• If $h_i(x^*) < 0$ (constraint is inactive/slack), then $\lambda_i^* = 0$ (the multiplier for that constraint is zero)
• If $\lambda_i^* > 0$ (the multiplier is active), then $h_i(x^*) = 0$ (the constraint is tight/binding)

Complementary slackness tells us which constraints matter at the optimum. In the 1D example above: $h(x^*) = 1 - 1 = 0$ (active), so $\lambda^*$ can be nonzero; indeed $\lambda^* = 1$.

SVM Dual as Worked Example#

The soft-margin SVM is a canonical ML application of duality. The primal problem:

$\min_{w, b, \xi} \; \frac{1}{2}\|w\|_2^2 + C \sum_{i=1}^n \xi_i$ $\text{s.t.} \quad y_i (w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \; i = 1,\ldots,n$

The Lagrangian introduces multipliers $\alpha_i \geq 0$ (for the margin constraints) and $\mu_i \geq 0$ (for $\xi_i \geq 0$):

$L = \frac{1}{2}\|w\|_2^2 + C\sum_i \xi_i - \sum_i \alpha_i(y_i(w^T x_i + b) - 1 + \xi_i) - \sum_i \mu_i \xi_i$

Setting $\partial L/\partial w = 0$, $\partial L/\partial b = 0$, $\partial L/\partial \xi_i = 0$ gives:

• $w = \sum_i \alpha_i y_i x_i$
• $\sum_i \alpha_i y_i = 0$
• $\alpha_i + \mu_i = C \implies 0 \leq \alpha_i \leq C$

Substituting back, the SVM dual is:

$\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^T x_j)$ $\text{s.t.} \quad 0 \leq \alpha_i \leq C, \quad \sum_i \alpha_i y_i = 0$

This is a quadratic program in $n$ variables with box constraints. The number of variables is now $n$ (number of examples) instead of $d$ (feature dimension) — a win when $d \gg n$.

Kernel trick preview: The dual depends on the data only through inner products $x_i^T x_j$. Replacing $x_i^T x_j$ with a kernel $K(x_i, x_j)$ allows SVMs to learn nonlinear decision boundaries without ever computing features in the kernel space explicitly.

Browser lab#

Solve a tiny 2D linearly separable SVM via projected gradient on the dual variables $\alpha$. Plot the decision boundary and highlight support vectors.

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(42)
n = 30
X_pos = rng.normal(loc=[2, 2], scale=1.0, size=(n//2, 2))
X_neg = rng.normal(loc=[-2, -2], scale=1.0, size=(n//2, 2))
X = np.vstack([X_pos, X_neg])
y = np.hstack([np.ones(n//2), -np.ones(n//2)])
n = len(y)

C = 1.0
K = X @ X.T

def dual_obj(alpha):
    return np.sum(alpha) - 0.5 * np.sum(np.outer(alpha * y, alpha * y) * K)

def dual_grad(alpha):
    return 1.0 - (K @ (alpha * y)) * y

alpha = np.zeros(n)
eta = 0.01
for _ in range(2000):
    g = dual_grad(alpha)
    alpha = alpha + eta * g
    alpha = np.clip(alpha, 0, C) * (np.abs(alpha) > 1e-5)

sv_idx = alpha > 1e-3
w_dual = X.T @ (alpha * y)

print(f"Support vectors: {sv_idx.sum()} / {n}")
print(f"Dual objective: {dual_obj(alpha):.4f}")
print(f"w = {np.round(w_dual, 3)}")

plt.figure(figsize=(6, 5))
plt.scatter(X_pos[:, 0], X_pos[:, 1], c="tab:blue", alpha=0.6, label="y=+1")
plt.scatter(X_neg[:, 0], X_neg[:, 1], c="tab:red", alpha=0.6, label="y=−1")
plt.scatter(X[sv_idx, 0], X[sv_idx, 1], facecolors="none", edgecolors="black", s=80, linewidths=1.5, label="support vectors")
xx = np.linspace(-5, 5, 100)
yy = -w_dual[0] / w_dual[1] * xx
plt.plot(xx, yy, "k--", label="decision boundary")
plt.xlim(-5, 5); plt.ylim(-5, 5)
plt.xlabel("x1"); plt.ylabel("x2")
plt.title("SVM Dual: Decision Boundary and Support Vectors")
plt.legend(); plt.gca().set_aspect("equal"); plt.show()