Duality and the KKT Conditions

Every inequality constraint carries a shadow price. It stays zero while the constraint is slack and turns on the instant the constraint binds. Those prices are the dual variables, and at an optimum they and the primal solution satisfy the KKT conditions. In physics the same prices come back with a physical name: they are the constraint forces that hold contacts and joints together.

The Lagrangian and the dual

Take the problem $\min_x f(x)$ subject to $g_i(x) \le 0$ for $i = 1,\dots,m$. Fold the constraints into the objective with one multiplier each:

$$\mathcal{L}(x,\mu) = f(x) + \sum_{i=1}^m \mu_i\, g_i(x), \qquad \mu_i \ge 0 .$$

Each $\mu_i$ charges a penalty proportional to the violation $g_i(x)$. Minimizing $\mathcal{L}$ over $x$ for a fixed price vector gives the dual function

$$q(\mu) = \inf_x\, \mathcal{L}(x,\mu) .$$

For any feasible $x$ (so $g_i(x) \le 0$) and any $\mu \ge 0$, the penalty sum is nonpositive, hence $\mathcal{L}(x,\mu) \le f(x)$ and

$$q(\mu) \;\le\; \mathcal{L}(x,\mu) \;\le\; f(x) .$$

Taking the infimum over feasible $x$ gives weak duality, $q(\mu) \le p^\star$, where $p^\star$ is the primal optimum. The dual problem sharpens this lower bound, $d^\star = \max_{\mu \ge 0} q(\mu) \le p^\star$. The difference $p^\star - d^\star \ge 0$ is the duality gap. When $f$ and the $g_i$ are convex and a strictly feasible point exists (Slater's condition), the gap closes: $d^\star = p^\star$, which is strong duality.¹

The KKT conditions

At a primal-dual optimum $(x^\star,\mu^\star)$ under strong duality, four conditions hold together:

$$\begin{aligned} &\text{stationarity:} && \nabla f(x^\star) + \sum_i \mu_i^\star\, \nabla g_i(x^\star) = 0, \\ &\text{primal feasibility:} && g_i(x^\star) \le 0, \\ &\text{dual feasibility:} && \mu_i^\star \ge 0, \\ &\text{complementary slackness:} && \mu_i^\star\, g_i(x^\star) = 0 . \end{aligned}$$

Complementary slackness is the hinge. For each constraint either $g_i = 0$ (tight, and it may carry a positive price) or $\mu_i = 0$ (slack, and its price vanishes), never both. Stationarity reads geometrically: $-\nabla f$ is a nonnegative combination of the active constraint gradients, so the steepest-descent direction is exactly cancelled by the constraints that push back. For convex programs these four conditions are not only necessary but sufficient for optimality.

A worked example

Minimize $\tfrac12(x_1^2 + x_2^2)$ subject to $x_1 + x_2 \ge 1$, written as $g(x) = 1 - x_1 - x_2 \le 0$. The gradients are

$$\nabla f = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}, \qquad \nabla g = \begin{bmatrix} -1 \\ -1 \end{bmatrix}.$$

Stationarity $\nabla f + \mu \nabla g = 0$ gives $x_1 = \mu$ and $x_2 = \mu$. Complementary slackness $\mu\,(1 - x_1 - x_2) = 0$ leaves two branches. If $\mu = 0$ then $x = 0$, but $g(0) = 1 > 0$ is infeasible, so that branch is rejected. The other branch takes the constraint active, $x_1 + x_2 = 1$:

$$2\mu = 1 \;\implies\; \mu = \tfrac12, \qquad x^\star = \begin{bmatrix} \tfrac12 \\ \tfrac12 \end{bmatrix}, \qquad f^\star = \tfrac14 .$$

Dual feasibility $\mu = \tfrac12 \ge 0$ and primal feasibility $g(x^\star) = 0$ both check, so this is the optimum. The dual confirms it. Minimizing $\mathcal{L} = \tfrac12(x_1^2 + x_2^2) + \mu(1 - x_1 - x_2)$ over $x$ at $x_1 = x_2 = \mu$ gives

$$q(\mu) = \mu - \mu^2, \qquad \mu \ge 0,$$

which is maximized at $\mu = \tfrac12$ with $q(\tfrac12) = \tfrac14 = p^\star$. The gap is zero: strong duality holds.

KKT geometryinteractive

objective bowl + feasible halfspace (drag to move c)

c (uncon. min)

(0.00, 0.00)

x* (optimum)

(0.50, 0.50)

g(x*) = 1−x1−x2

0.00

μ (multiplier)

0.50

μ · g(x*)

0.00 = 0

constraint active: g(x*) = 0, μ > 0. −∇f (dark) lies along ∇g (yellow), so −∇f = μ∇g.

Complementary slackness forces μ·g(x*) = 0: either the constraint is tight and priced (μ > 0), or slack and free (μ = 0). Never both.

Constraint forces are the multipliers

In rigid-body dynamics the nonpenetration constraint at contact $i$ is $g_i(x) = -\phi_i \le 0$, where $\phi_i \ge 0$ is the gap. Its multiplier $\mu_i$ is nothing other than the normal contact force (or impulse) $\lambda_i$, and the three complementarity pieces of KKT read as physical laws:

$$\lambda_i \ge 0, \qquad \phi_i \ge 0, \qquad \lambda_i\, \phi_i = 0 .$$

Dual feasibility $\lambda_i \ge 0$ is one-sidedness: a contact pushes and never pulls. Complementary slackness $\lambda_i \phi_i = 0$ is the Signorini condition: a force acts only when the gap is closed. Stationarity is the equation of motion, with each constraint force $\lambda_i \nabla g_i$ acting along the surface normal and scaled by its multiplier. So the geometric statement from the demo, that the multiplier scales the constraint normal, is literally the statement that a contact force points along the normal with magnitude set by how hard the constraint is pressed. KKT is the optimization face of the same complementarity that governs contact.

Footnotes

1. Boyd & Vandenberghe, Convex Optimization (2004). ↩