The Lagrangian and KKT conditions

Gradients are normal to level sets

A level set of $f$ is $\{x : f(x)=c\}$, a contour. Walking along it in a tangent direction $v$ doesn't change $f$ at all, so the directional derivative must vanish:

$$ \nabla f(x)\cdot v = 0 \quad \text{for every tangent direction } v \text{ of the level set through } x. $$

Intuition: $\nabla f$ points where $f$ increases fastest; a level set is exactly the directions where $f$ doesn't change, so the two must be perpendicular.

Example

$f(x,y)=x^2+y^2$, level set $x^2+y^2=4$ (a circle). At $(2,0)$: $\nabla f=(4,0)$, and the circle's tangent there is $(0,1)$. $(4,0)\cdot(0,1)=0.$ ✓

Constrained optimization: a tangency condition

Minimize $f(x)$ subject to $g(x)=0$. At an optimum $x^*$ on the constraint surface, moving along any tangent direction $v$ of that surface (so $\nabla g(x^*)\cdot v=0$) can't improve $f$ to first order either, so $\nabla f(x^*)\cdot v=0$ for the same $v$'s. Both gradients are normal to the same tangent space, in $\mathbb{R}^2$ that forces them to be parallel:

$$ \nabla f(x^*) = \lambda\, \nabla g(x^*) \quad \text{for some scalar } \lambda. $$

Intuition: at the optimum, $f$'s contour must be tangent to the constraint surface; if they crossed instead, sliding along the constraint would still change $f$, so you couldn't be at an optimum yet.

Example

Minimize $f(x,y)=x^2+y^2$ subject to $g(x,y)=x+y-1=0$. $\nabla f=(2x,2y)$, $\nabla g=(1,1)$. Setting $\nabla f=\lambda\nabla g$ gives $x=y$, and $x+y=1$ then gives $x=y=\tfrac12$, $\lambda=1$.

The Lagrangian

$L(x,\lambda) := f(x) + \lambda g(x)$ packages the tangency condition as a single unconstrained stationarity condition:

$$ \nabla_x L = \nabla f(x) + \lambda\nabla g(x) = 0, \qquad \nabla_\lambda L = g(x) = 0. $$

With $m$ equality constraints $g_1,\dots,g_m$: $L(x,\lambda) = f(x) + \sum_i \lambda_ig_i(x)$, stationary in both $x$ and every $\lambda_i$.

Intuition: the Lagrangian turns a constrained problem into an unconstrained one, each multiplier $\lambda_i$ is just the bookkeeping that enforces $g_i(x)=0$.

Shapes

With $x\in\mathbb{R}^n$ and $m$ constraints $g:\mathbb{R}^n\to\mathbb{R}^m$ (Jacobian $J_g$ is $m\times n$), the $m$ multipliers form a vector $\lambda\in\mathbb{R}^m$, and stationarity is one vector equation in $\mathbb{R}^n$:

$$ \underbrace{\nabla f(x)}_{n\times1}+\underbrace{J_g(x)^T}_{n\times m}\underbrace{\lambda}_{m\times1}=0, \qquad J_g^T\lambda=\begin{pmatrix}\vert&&\vert\\\nabla g_1&\cdots&\nabla g_m\\\vert&&\vert\end{pmatrix}\begin{pmatrix}\lambda_1\\\vdots\\\lambda_m\end{pmatrix}=\sum_i\lambda_i\nabla g_i. $$

The columns of $J_g^T$ are the constraint gradients; $\lambda$ says how much of each to combine so that their sum cancels $\nabla f$. That is $\nabla f\in\operatorname{span}(\nabla g_1,\dots,\nabla g_m)$, the multi-constraint version of "parallel".

Example

Same problem: $L=x^2+y^2+\lambda(x+y-1)$. $\partial L/\partial x = 2x+\lambda=0$, $\partial L/\partial y=2y+\lambda=0$, $\partial L/\partial\lambda=x+y-1=0$. Solving: $x=y=\tfrac12$, $\lambda=-1$, the same point as above (the sign of $\lambda$ is just a convention).

Inequality constraints and KKT

Minimize $f(x)$ subject to $h(x)\leq0$. Two cases at the optimum $x^*$:

• Inactive ($h(x^*)<0$): the constraint doesn't touch the optimum, so plainly $\nabla f(x^*)=0$.
• Active ($h(x^*)=0$): same tangency argument as before, but now you can only move into the feasible side $h\leq0$, not any direction, so the multiplier's sign is pinned down: $\nabla f(x^*) = -\mu\,\nabla h(x^*)$ with $\mu\geq0$.

Intuition: an inequality constraint only pushes back once you're pressed against it; $\mu\geq0$ says that push can only block you from leaving the feasible region, never pull you into it.

Both cases are captured together by the KKT conditions, for $f$ minimized subject to $h_j(x)\leq0$ and $g_i(x)=0$:

$$ \nabla f(x^*) + \sum_j \mu_j\nabla h_j(x^*) + \sum_i \lambda_i\nabla g_i(x^*) = 0 \quad \text{(stationarity)} $$

Shapes

With $p$ inequality constraints $h:\mathbb{R}^n\to\mathbb{R}^p$ (Jacobian $J_h$, $p\times n$) and $m$ equality constraints $g$ (Jacobian $J_g$, $m\times n$) as before:

$$ \underbrace{\nabla f(x^*)}_{n\times1} + \underbrace{J_h(x^*)^T}_{n\times p}\underbrace{\mu}_{p\times1} + \underbrace{J_g(x^*)^T}_{n\times m}\underbrace{\lambda}_{m\times1} = 0. $$

Intuition: same cancellation as the equality-only case, now with two groups of constraint gradients feeding into the same $n$-dimensional sum; complementary slackness is what zeroes out the multiplier of every inequality constraint that isn't actually touching the optimum.

$$ h_j(x^*)\leq0,\ \ g_i(x^*)=0 \quad \text{(primal feasibility)}, \qquad \mu_j\geq0 \quad \text{(dual feasibility)} $$

$$ \mu_j\, h_j(x^*) = 0 \quad \text{(complementary slackness: inactive} \Rightarrow \mu_j=0\text{, active} \Rightarrow h_j=0\text{)}. $$

Example

Minimize $f(x,y)=x^2+y^2$ subject to $h(x,y)=1-x-y\leq0$ (i.e. $x+y\geq1$). The unconstrained minimum of $f$ is the origin, which has $h(0,0)=1>0$: infeasible, so the constraint is active at the optimum.

Same computation as the equality case gives $x^*=y^*=\tfrac12$. Checking the multiplier's sign: $\nabla f(x^*)=(1,1)$, $\nabla h(x^*)=(-1,-1)$, and $\nabla f=-\mu\nabla h$ gives $\mu=1\geq0$. ✓ Complementary slackness holds since $h(x^*)=0$ (active).