Optimization - Lagrangian, KKT, duality

We will assume throughout this page that all functions are differentiable (smooth) unless stated otherwise. We start with a simple unconstrained problem: find $x \in \mathbb{R}^n$ that minimizes a cost function $f : \mathbb{R}^n \to \mathbb{R}$. You might remember from calculus that the minimum can be found by setting the gradient to zero,

This is known as the stationarity condition, and it has a very simple proof for our unconstrained system.

Now force $x$ to satisfy an equality constraint $h(x) = 0$. The feasible set is the surface where $h$ vanishes. We want

The condition $\nabla f = 0$ is too strong now: we do not need $f$ flat in every direction, only flat along the directions we are actually allowed to move, which are the directions that stay on the surface. Those are the directions $v$ tangent to the surface: move along the surface in such a direction and $h$ stays at zero, so they satisfy $\nabla h(x)^\top v = 0$.

For $x^\star$ to be a minimum, $f$ must not decrease along any such $v$, which means $\nabla f$ has no component in the tangent directions:

A vector that is orthogonal to everything orthogonal to $\nabla h$ has to be a multiple of $\nabla h$ itself. So at the optimum the two gradients line up,

for some scalar $\lambda$, the Lagrange multiplier. The sign and size of $\lambda$ are free here, an equality constraint can push either way, so the minus is only a convention. We write it this way to stay with the Lagrangian introduced later. Geometrically this says the level set of $f$ and the constraint surface are tangent at $x^\star$. Two surfaces are tangent exactly when their normals line up, and the normals here are the gradients $\nabla f$ and $\nabla h$, so tangency is the same statement as the equation above. If they crossed instead of touching, you could slide along the constraint to a lower level set.

We can actually "package" the whole optimization problem into one single function called the Lagrangian. Note that it takes both the state $x$ and the Lagrange multipliers $\lambda$ as input,

If we apply the stationarity condition to it, i.e. set its gradient to zero (w.r.t. both $x$ and $\lambda$), we can recover the two conditions that we want. The $x$-gradient gives the tangency, and the $\lambda$-gradient gives the equality constraint:

With several equality constraints $h_j(x) = 0$ for $j = 1, \dots, m$, each gets its own multiplier and they add up,

So at stationarity $\nabla_x \mathcal{L} = 0$ says $\nabla f$ is a linear combination of the constraint gradients.

Play with the tool below to see how the multipliers change as you move the constraints. The constraints are linear, so each is a line $a_j^\top x = b_j$ where $b_j$ is the "offset" below. The relaxation $c$ is just a change in $b_j$, which makes $\lambda_j$ literally $\partial f^\star / \partial b_j$.

With one constraint, $x^\star$ is where the line touches a contour, and sliding the line glides that tangent point along. With two, $x^\star$ is pinned at the intersection, so sliding line $j$ while the other is held drags $x^\star$ along the held line. Either way $\lambda_j$ is how fast $f$ changes as the solution is forced that way. The sign is free for an equality: a negative $\lambda_j$ just means relaxing that way lowers $f^\star$.

Inequalities are a bit more involved. Let's now look at the general optimization problem,

An inequality $g_i(x) \le 0$ behaves in one of two ways at the solution. Either it is inactive, $g_i(x^\star) < 0$, and the optimum sits strictly inside that constraint, in the interior of the feasible region, in which case the constraint is doing nothing and we can ignore it locally. Or it is active, $g_i(x^\star) = 0$, and the optimum is pinned against the boundary, in which case it behaves like an equality constraint that happens to be pushing from one side only.

That one-sidedness is important. For an active inequality, the constraint can only resist motion that would take us into the forbidden region $g_i > 0$. So at the optimum $\nabla f$ points back into the feasible side, and that fixes the sign of the multiplier.

The Lagrangian can be written as before, but this time with the addition of the inequality constraints,

Note that the multipliers are now $\lambda_i$ for the inequalities and $\nu_j$ for the equalities.

With no constraints, a minimum just needs $\nabla f = 0$. As we have seen earlier, constraints change that: the solution can sit on a boundary where $\nabla f \ne 0$, held there by the constraints pushing back. The Karush-Kuhn-Tucker (KKT) conditions are the general way to write that "$\nabla f = 0$" condition, but with constraints this time. There are four of them:

• Stationarity. $\nabla_x \mathcal{L} = \nabla f + \sum_i \lambda_i \nabla g_i + \sum_j \nu_j \nabla h_j = 0$. The objective gradient is balanced by the active constraints pushing back, so the solution sits at a stationary point of the Lagrangian.
• Primal feasibility. $g_i(x) \le 0$ and $h_j(x) = 0$. The solution obeys the constraints.
• Dual feasibility. $\lambda_i \ge 0$. Inequality multipliers cannot go negative, because the constraint only pushes one way.
• Complementary slackness. $\lambda_i\, g_i(x) = 0$ for every $i$. Either the constraint is active ($g_i(x) = 0$) and pushes with a potentially non-zero multiplier $\lambda_i$, or the constraint is inactive ($g_i(x) < 0$) and the multiplier is $0$.

A point that satisfies the KKT conditions is not automatically optimal. Under some extra assumptions, though, KKT is both necessary at a minimum and sufficient for one.

Necessary. At a local minimum, KKT holds as long as the constraints satisfy a mild regularity assumption, a constraint qualification. One common version is that the active constraint gradients are linearly independent. So every well-behaved minimum is a KKT point, and we can safely search among KKT points for it.

Sufficient. When the problem is convex, $f$ and the $g_i$ convex and the $h_j$ affine, the reverse also holds: any point meeting all four conditions is a global minimum. This means that under these conditions you can find the solution by solving the KKT. We talk about this in more detail below.

Even then, KKT describes the solution without telling you how to find it, and not knowing in advance which constraints end up active makes a direct approach hard. The dual is a way around that. Rather than treating the constraints as hard walls, we attach a price to each one and adjust the prices until they do the job the walls were doing.

Start from the Lagrangian and minimize it over $x$ with the multipliers held fixed. What comes out is a function of the multipliers alone, the dual function,

This inner minimization is unconstrained in $x$, which is the whole point: we have traded the constraints for the penalty terms, and can often solve the inside in closed form. What is left is to pick the prices $\lambda, \nu$, and two facts about the dual function make that manageable.

The first useful fact is that the dual function is a lower bound on the original optimal value $p^\star = \min f$, for any prices with $\lambda \ge 0$. That is called weak duality.

So every choice of prices gives a lower bound. The best one we can get is the dual problem,

The second useful fact is that this maximization is always well behaved, even when the original problem is not. For fixed $x$, $\mathcal{L}$ is linear in $(\lambda, \nu)$, and a minimum of linear functions is concave, so $d$ is concave. We are maximizing a concave function over the convex set $\lambda \ge 0$, whatever $f$, $g$, $h$ look like.

The gap $p^\star - d^\star \ge 0$ is the duality gap. When it is zero we have strong duality: the dual optimum is the primal optimum, so solving the concave dual solves the original problem. This is however not always guaranteed. For convex problems it needs to satisfy Slater's condition, which asks for one strictly feasible point with $g_i(x) < 0$. When it holds, the primal and dual solutions satisfy the KKT conditions together. Complementary slackness then says only the active constraints carry a positive price.

As a summary, let's walk through solving the dual for a general convex problem, with several inequalities and equalities,

We will assume the problem is convex with a strictly feasible point: the $g_i$ are convex, the $h_j$ affine, and Slater's condition met. This means the duality gap is zero and solving the dual recovers the optimal solution.

The dual turns this into two nested loops, an inner solve for $x$ and an outer update for the prices.

First, form the Lagrangian, with a price (Lagrange multiplier) on each constraint. $\lambda_i \ge 0$ to the inequalities and a free-sign $\nu_j$ to the equalities.

The inner solve fixes the prices and minimizes over $x$, which is just an unconstrained problem.

We want to maximize $d$ over $\lambda \ge 0$ and $\nu$, and by the envelope theorem (below) each partial derivative is just the matching constraint value evaluated at the unconstrained minimum $x^\star(\lambda, \nu)$,

With these derivatives we can perform gradient ascent on the prices,

An inequality price rises when its constraint is violated, $g_i(x^\star) > 0$, and the penalty pushes $x^\star$ back toward the feasible region. When the constraint is slack ($g_i(x^\star) < 0$) it falls toward $0$, and the clip $[\,\cdot\,]_+$ keeps it at $\lambda_i \ge 0$.

An equality has no good side, so its price $\nu_j$ is free in sign and moves either way to drive $h_j(x^\star)$ to zero.

At convergence the inequalities satisfy complementary slackness, $\lambda_i\, g_i(x^\star) = 0$: each is either inactive with zero price or tight ($g_i = 0$). Equalities are always active, so their $\nu_j$ are generally nonzero.

Overall the whole idea is to replace each constraint "wall" with a price and adjust it until the constraint holds. This transforms a constrained problem into a sequence of unconstrained ones.

Putting the two loops together, the whole procedure is: