Lagrange multipliers, KKT conditions and duality

Before this lesson: lesson 02 (convex functions, the first-order condition); gradients and level sets (lesson 01, calculus 02); projections (linear algebra 03); the $\ell_1$ and $\ell_\infty$ norms (linear algebra 11) for the lasso dual. Time: about 95 minutes, plus the notebook.

---

Why this matters #

Constraints are everywhere in ML. A probability vector must lie on the simplex. A physical parameter has bounds. A fairness or safety requirement limits a model. A simulation must satisfy its equations. The KKT conditions tell you what a constrained solution looks like, so you can often write it in closed form: projections, sparsemax, the support vector machine (SVM). Each multiplier is the price of its constraint, which tells you which constraints matter. Duality turns every price into a lower bound on the optimal value. This gives stopping rules with a guarantee (scikit-learn's Lasso stops on a duality gap), and the SVM dual, where kernels and support vectors appear. In science, the multipliers of a PDE constraint are the adjoint variables used to compute gradients of simulations.

1. Predict first #

2. The picture #

2.1 One equality constraint: walk along the curve #

Take a function $f(x)$ of $x = (x_1, x_2)$ and a constraint $h(x) = 0$. The constraint is a curve in the plane. We want the point of the curve where $f$ is smallest.

Walk along the curve and watch the contour lines (level sets) of $f$. Recall two facts from lesson 01: $\nabla f$ is perpendicular to the level set of $f$ through the point, and $\nabla h$ is perpendicular to the curve $h = 0$.

• Where the curve crosses a level set, one direction along the curve goes downhill. So this point is not the minimum: you can still lower $f$.
• At the minimum, no direction along the curve goes downhill. The curve touches the level set there: they are tangent. Two curves that are tangent have the same normal direction.

So at a constrained minimum $x^\star$, the gradients are parallel:

The number $\nu$ is the Lagrange multiplier. It can be positive or negative. We assume $\nabla h(x^\star) \ne 0$, so that the curve has a normal direction at $x^\star$.

The same argument with a formula. Let $\tau$ be a unit tangent vector of the curve at $x$. The rate of change of $f$ along the curve is the directional derivative $\nabla f(x)^\top \tau$. At a minimum along the curve this rate must be 0; otherwise a small step along $-\tau$ or $+\tau$ lowers $f$. So $\nabla f(x^\star) \perp \tau$. In the plane, the only directions perpendicular to $\tau$ are the multiples of $\nabla h(x^\star)$. Hence $\nabla f(x^\star)$ is a multiple of $\nabla h(x^\star)$.

Interactive figure: loading…

Example. Minimize $f(x) = x_1^2 + x_2^2$ subject to $x_1 + x_2 = 1$. Here $h(x) = x_1 + x_2 - 1$, $\nabla f = (2x_1, 2x_2)$ and $\nabla h = (1, 1)$.

1. Parallel gradients: $2x_1 + \nu = 0$ and $2x_2 + \nu = 0$. So $x_1 = x_2 = -\nu/2$.
2. The constraint: $-\nu/2 - \nu/2 = 1$, so $\nu = -1$.
3. Hence $x^\star = (0.5, 0.5)$ and $f(x^\star) = 0.5$.

In the figure, the level set $x_1^2 + x_2^2 = 0.5$ is the circle of radius $1/\sqrt2 \approx 0.707$, and it touches the line at $(0.5, 0.5)$. This answers question 1 of section 1: at the lowest point, the road touches the contour line.

Seen in 3D. The constrained minimum is not the bottom of the bowl. Lift the constraint curve onto the surface $z = f(x)$. The constrained minimum is the lowest point of this lifted curve.

Interactive figure: loading…

2.2 The Lagrangian #

Put the objective and the constraint into one function, the Lagrangian:

Its stationary points are exactly the candidates of section 2.1:

• $\nabla_x \mathcal L = \nabla f(x) + \nu \nabla h(x) = 0$ is the tangency condition;
• $\partial \mathcal L / \partial \nu = h(x) = 0$ is the constraint.

With $x \in \R^d$ this is $d + 1$ equations for $d + 1$ unknowns. Two warnings:

• A stationary point of $\mathcal L$ is a saddle point of $\mathcal L$, not a minimum. In the example, $\mathcal L$ is linear in $\nu$, so it has no minimum in $\nu$.
• The condition finds candidates: constrained minima, maxima and other critical points. You must compare them (or use convexity, section 3).

2.3 The multiplier as a price #

Move the constraint: require $x_1 + x_2 = c$ instead of $= 1$. Repeat the example: $x^\star = (c/2, c/2)$ and the optimal value is

With $h(x) = x_1 + x_2 - c$, the same steps give $\nu = -c$. So $\frac{dp^\star}{dc} = -\nu$. At $c = 1$ the slope is 1 and $\nu = -1$.

Why this holds in general (intuition). Write the constraint as $a(x) = c$, so $h(x) = a(x) - c$ and $\nabla h = \nabla a$. Change $c$ by a small $dc$. The optimal point moves by some $dx$ that keeps the constraint, so $\nabla a(x^\star)^\top dx = dc$. Then

So $-\nu$ is the price of the constraint: one more unit of $c$ changes the best value by about $-\nu$. Section 3 states this precisely.

Interactive figure: loading…

2.4 Inequality constraints: the wall #

Now take a constraint $x \le 1$ in one variable, and minimize a smooth convex $f_0(x)$. There are two cases.

• Inactive. The unconstrained minimizer satisfies $x \le 1$. The constraint does nothing: $f_0'(x^\star) = 0$.
• Active. The unconstrained minimizer is to the right of 1. The solution sits on the wall, $x^\star = 1$. There $f_0'(x^\star) < 0$: $f_0$ wants to move right, but the wall stops it. Write this balance of forces as $f_0'(x^\star) + \lambda = 0$, with a wall force $\lambda > 0$.

Both cases are one statement. Write the constraint as $f_1(x) = x - 1 \le 0$. Then

The last condition says: the wall pushes only if you touch it. If $f_1(x^\star) < 0$ (not touching), then $\lambda = 0$. This is complementary slackness. The sign $\lambda \ge 0$ says that a wall can only push you back into the feasible set, never pull you out.

Example (question 2 of section 1). Minimize $(x - 3)^2$ subject to $x \le 1$. The constraint is active: $x^\star = 1$, and $2(1 - 3) + \lambda = 0$ gives $\lambda = 4$. Relaxing to $x \le 1 + \delta$ gives $p^\star(\delta) = (1 + \delta - 3)^2 = (2 - \delta)^2 = 4 - 4\delta + \delta^2$. So $p^\star$ goes down by about $4\delta = \lambda\delta$: the multiplier is again the price.

In two dimensions the picture is the same. The feasible set is a region; the wall is its boundary. If the unconstrained minimizer is inside, $\lambda = 0$. If it is outside, the solution is on the boundary, where the level set of $f$ touches the boundary, and $\lambda > 0$.

Interactive figure: loading…

For $a = (2, 1)$ and the half-plane $x_1 + x_2 \le 1$: stationarity gives $x = (2 - \lambda/2,\ 1 - \lambda/2)$, the active constraint gives $3 - \lambda = 1$, so $\lambda = 2$, $x^\star = (1, 0)$ and $p^\star = 2$. Section 4 checks every condition.

3. Definitions and main results #

Standard form and the Lagrangian #

The variable is $x \in \R^d$. The problem in standard form is

with optimal value $p^\star$. A point that satisfies all constraints is feasible. The problem is convex when $f_0, f_1, \dots, f_m$ are convex and every $h_j$ is affine (so the equalities read $Ax = b$). Write every constraint in this form first: $x_1 + x_2 \ge 2$ becomes $2 - x_1 - x_2 \le 0$.

The Lagrangian adds each constraint with its own multiplier:

with $\lambda_i \ge 0$ for an inequality and $\nu_j \in \R$ (any sign) for an equality. In this lesson, $\lambda$ is a Lagrange multiplier, not an eigenvalue. We follow the notation of Boyd and Vandenberghe.

The KKT conditions #

A point $(x, \lambda, \nu)$ satisfies the Karush–Kuhn–Tucker (KKT) conditions if (for differentiable $f_i$, $h_j$):

1. primal feasibility: $f_i(x) \le 0$ for all $i$ and $h_j(x) = 0$ for all $j$;
2. dual feasibility: $\lambda_i \ge 0$ for all $i$;
3. complementary slackness: $\lambda_i f_i(x) = 0$ for all $i$;
4. stationarity: $\nabla f_0(x) + \sum_i \lambda_i \nabla f_i(x) + \sum_j \nu_j \nabla h_j(x) = 0$.

A constraint with $f_i(x) = 0$ is active; one with $f_i(x) < 0$ is inactive. Complementary slackness says that an inactive constraint has $\lambda_i = 0$. In practice it is a case split: for each inequality, guess "active" ($f_i = 0$) or "inactive" ($\lambda_i = 0$), solve, and check the signs. If the guess "active" gives $\lambda_i < 0$, the guess was wrong.

Theorem (KKT points of convex problems are optimal) #

Let the problem be convex, with differentiable $f_0, \dots, f_m$. If $(\tilde x, \tilde\lambda, \tilde\nu)$ satisfies the four KKT conditions, then $\tilde x$ is a global minimizer.

Why it is true (intuition). With the prices $\tilde\lambda, \tilde\nu$ fixed, the Lagrangian is a convex function of $x$ whose gradient is zero at $\tilde x$, so $\tilde x$ minimizes it. On the feasible set, the Lagrangian is never above $f_0$, and at $\tilde x$ it equals $f_0$.

Proof.

1. $\tilde\lambda_i \ge 0$, each $f_i$ is convex and each $h_j$ is affine. So $x \mapsto \mathcal L(x, \tilde\lambda, \tilde\nu)$ is a sum of convex functions: it is convex.
2. Stationarity says that its gradient is zero at $\tilde x$. For a differentiable convex function, a zero gradient means a global minimum (lesson 02, first-order condition). So $\mathcal L(x, \tilde\lambda, \tilde\nu) \ge \mathcal L(\tilde x, \tilde\lambda, \tilde\nu)$ for every $x$.
3. Complementary slackness and $h_j(\tilde x) = 0$ remove the added terms at $\tilde x$: $\mathcal L(\tilde x, \tilde\lambda, \tilde\nu) = f_0(\tilde x)$.
4. Let $x$ be any feasible point. Then $\tilde\lambda_i f_i(x) \le 0$ and $h_j(x) = 0$, so $f_0(x) \ge \mathcal L(x, \tilde\lambda, \tilde\nu)$.
5. Steps 4, 2 and 3 give $f_0(x) \ge \mathcal L(x, \tilde\lambda, \tilde\nu) \ge \mathcal L(\tilde x, \tilde\lambda, \tilde\nu) = f_0(\tilde x)$. $\blacksquare$

For a nonconvex problem this fails: a KKT point can be a maximum or a saddle (the circle quiz above).

When are the KKT conditions necessary? #

The theorem says KKT ⇒ optimal (for convex problems). The converse needs an extra assumption, a constraint qualification. The standard one for convex problems is Slater's condition: there is a strictly feasible point, that is, some $x$ with $f_i(x) < 0$ for every non-affine $f_i$ (affine inequalities only need $f_i(x) \le 0$) and $Ax = b$. Under Slater's condition, $x^\star$ is optimal if and only if there are multipliers with which the KKT conditions hold (the proof follows from strong duality, below).

For nonconvex problems, KKT is necessary at a local minimum under a constraint qualification such as LICQ (the gradients of the active constraints are linearly independent), and it is not sufficient.

An example where KKT fails at the optimum

Minimize $x$ subject to $x^2 \le 0$. Only $x = 0$ is feasible, so $x^\star = 0$ and $p^\star = 0$. Stationarity asks for $1 + 2\lambda x^\star = 1 + 0 = 0$, which no $\lambda$ satisfies. So no KKT multiplier exists at the optimum. The problem is convex, but Slater's condition fails: $x^2 < 0$ is impossible. Geometrically, $\nabla f_1(x^\star) = 2x^\star = 0$: the "wall" has no normal direction to push with.

Projection onto the probability simplex #

Problem. Given $y \in \R^n$, find the closest point of the probability simplex $\Delta = \{x : x \ge 0,\ \mathbf 1^\top x = 1\}$:

The Lagrangian is $\tfrac12\|x - y\|^2 + \nu(\mathbf 1^\top x - 1) - \lambda^\top x$.

1. Stationarity: $x_i - y_i + \nu - \lambda_i = 0$ for each $i$.
2. If $x_i > 0$, complementary slackness gives $\lambda_i = 0$, so $x_i = y_i - \nu$ (and $y_i > \nu$).
3. If $x_i = 0$, then $\lambda_i = \nu - y_i$, and dual feasibility $\lambda_i \ge 0$ gives $y_i \le \nu$.
4. Together: $x_i = \max(y_i - \nu, 0)$. Shift every entry down by one constant $\nu$, then clip at 0.
5. $\nu$ solves $\sum_i \max(y_i - \nu, 0) = 1$. The left side is continuous and strictly decreasing where it is positive, so $\nu$ is unique. To find it, sort $y$ in decreasing order, $u_1 \ge \dots \ge u_n$. Let $\rho$ be the largest $j$ with $u_j - \frac{1}{j}\big(\sum_{i \le j} u_i - 1\big) > 0$. Then $\nu = \frac{1}{\rho}\big(\sum_{i \le \rho} u_i - 1\big)$. The cost is $O(n \log n)$.

The problem is convex with affine constraints, so the KKT conditions are sufficient: this $x$ is the projection. The constant $\nu$ is a threshold (some papers call it $\tau$). Entries below it become exactly 0.

Duality: every price gives a lower bound #

Fix the prices $\lambda \ge 0$ and $\nu$, and minimize the Lagrangian over all $x$, with no constraints. The result is the dual function:

It can be $-\infty$. It is always concave, even when the original problem is not convex: for each fixed $x$, $\mathcal L(x, \lambda, \nu)$ is an affine function of $(\lambda, \nu)$ (a line, in one dimension), and $g$ is the lower envelope of these affine functions. A pointwise infimum of affine functions is concave.

Theorem (weak duality) #

For every $\lambda \ge 0$ and every $\nu$: $g(\lambda, \nu) \le p^\star$.

Proof.

1. Take any feasible $\tilde x$. Then $\lambda_i f_i(\tilde x) \le 0$ (because $\lambda_i \ge 0$ and $f_i(\tilde x) \le 0$), and $h_j(\tilde x) = 0$.
2. So $\mathcal L(\tilde x, \lambda, \nu) \le f_0(\tilde x)$.
3. The infimum is at most the value at one point: $g(\lambda, \nu) \le \mathcal L(\tilde x, \lambda, \nu) \le f_0(\tilde x)$.
4. This holds for every feasible $\tilde x$, so $g(\lambda, \nu) \le p^\star$. $\blacksquare$

The dual problem looks for the best lower bound: maximize $g(\lambda, \nu)$ subject to $\lambda \ge 0$. Its value is $d^\star$, and weak duality gives $d^\star \le p^\star$. The difference $p^\star - d^\star \ge 0$ is the optimal duality gap.

Interactive figure: loading…

Strong duality means $d^\star = p^\star$. It does not always hold, not even for every convex problem. Theorem (Boyd and Vandenberghe §5.2.3): if the problem is convex and Slater's condition holds, then $d^\star = p^\star$, and the dual optimum is attained when $d^\star > -\infty$.

The duality gap as a certificate. Let $x$ be feasible and $(\lambda, \nu)$ dual feasible ($\lambda \ge 0$, $g > -\infty$). Then $f_0(x) - p^\star \le f_0(x) - g(\lambda, \nu)$. The right side can be computed without knowing $p^\star$. When it is below a tolerance, you can stop: $x$ is that close to optimal. This is how scikit-learn's Lasso decides to stop.

Why KKT is necessary under strong duality

Suppose strong duality holds, $x^\star$ is primal optimal and $(\lambda^\star, \nu^\star)$ is dual optimal. Then

$$\begin{aligned} f_0(x^\star) = g(\lambda^\star, \nu^\star) &\le \mathcal L(x^\star, \lambda^\star, \nu^\star) \\ &= f_0(x^\star) + \textstyle\sum_i \lambda_i^\star f_i(x^\star) \le f_0(x^\star). \end{aligned}$$

So both inequalities are equalities. The second one gives $\sum_i \lambda_i^\star f_i(x^\star) = 0$. Every term is $\le 0$, so every term is 0: complementary slackness. The first one says that $x^\star$ minimizes $\mathcal L(\cdot, \lambda^\star, \nu^\star)$, so its gradient is zero there: stationarity. Feasibility of $x^\star$ and $\lambda^\star \ge 0$ are given. So all four KKT conditions hold. With Slater's condition (which gives strong duality and an attained dual optimum), optimal $\iff$ KKT.

A convex problem with a positive duality gap

Boyd and Vandenberghe, exercise 5.21: minimize $e^{-x}$ subject to $x^2/y \le 0$, on the domain $y > 0$. Only $x = 0$ is feasible, so $p^\star = 1$. But for every $\lambda \ge 0$, $g(\lambda) = \inf_{x,\ y > 0} \big(e^{-x} + \lambda x^2/y\big) = 0$: take $y = x^3$ and let $x \to \infty$, so that both terms go to 0. So $d^\star = 0$ and the gap is 1. The problem is convex, but Slater's condition fails, because $x^2/y < 0$ is impossible.

Multipliers as sensitivities (precise form) #

Perturb the constraints to $f_i(x) \le u_i$ and $h_j(x) = v_j$, with optimal value $p^\star(u, v)$. If strong duality holds and $(\lambda^\star, \nu^\star)$ is dual optimal for $u = 0$, $v = 0$, then for every $(u, v)$ (Boyd and Vandenberghe §5.6):

Proof. For any $x$ feasible for the perturbed problem, $p^\star(0, 0) = g(\lambda^\star, \nu^\star) \le \mathcal L(x, \lambda^\star, \nu^\star) \le f_0(x) + \lambda^{\star\top} u + \nu^{\star\top} v$, because $\lambda_i^\star f_i(x) \le \lambda_i^\star u_i$ and $\nu_j^\star h_j(x) = \nu_j^\star v_j$. Take the infimum over such $x$. $\blacksquare$

If $p^\star$ is differentiable at 0, then $\partial p^\star / \partial u_i = -\lambda_i^\star$ and $\partial p^\star / \partial v_j = -\nu_j^\star$. A large $\lambda_i^\star$ means that tightening constraint $i$ is expensive; $\lambda_i^\star = 0$ means a small change costs nothing.

Two duals you should know #

Least norm. Minimize $x^\top x$ subject to $Ax = b$, with $A$ of full row rank. Here $\mathcal L = x^\top x + \nu^\top(Ax - b)$, and $\nabla_x \mathcal L = 2x + A^\top \nu = 0$ gives $x = -A^\top \nu / 2$. Substitute:

a concave quadratic. Setting its gradient $-\tfrac12 AA^\top\nu - b$ to zero gives $\nu^\star = -2(AA^\top)^{-1} b$ and $d^\star = b^\top (AA^\top)^{-1} b$. Then $x^\star = -A^\top\nu^\star/2 = A^\top(AA^\top)^{-1} b = A^+ b$, the pseudoinverse solution, and $p^\star = \|x^\star\|^2 = d^\star$.

Lasso. Minimize $P(x) = \tfrac12\|Ax - b\|^2 + \lambda\|x\|_1$, with optimal value $P^\star$. Here $\lambda > 0$ is the penalty weight, not a multiplier. There are no constraints, so first introduce a copy $z = Ax - b$, with a multiplier $\theta$ for the constraint $z - Ax + b = 0$: $\mathcal L = \tfrac12\|z\|^2 + \lambda\|x\|_1 + \theta^\top(z - Ax + b)$.

1. Over $z$: $\tfrac12\|z\|^2 + \theta^\top z$ is smallest at $z = -\theta$, with value $-\tfrac12\|\theta\|^2$.
2. Over $x$: $\lambda\|x\|_1 - (A^\top\theta)^\top x$ is 0 if $\|A^\top\theta\|_\infty \le \lambda$, and $-\infty$ otherwise (grow $x$ along a coordinate where $|(A^\top\theta)_i| > \lambda$).
3. The dual: maximize $D(\theta) = b^\top\theta - \tfrac12\|\theta\|^2 = \tfrac12\|b\|^2 - \tfrac12\|b - \theta\|^2$ subject to $\|A^\top\theta\|_\infty \le \lambda$.
4. All constraints are affine, so strong duality holds. From step 1, $\theta^\star = -z^\star = b - Ax^\star$: the optimal dual point is the residual.
5. A certificate from any $x$: let $r = b - Ax$ and $\theta = s\,r$ with $s = \min\big(1, \lambda / \|A^\top r\|_\infty\big)$. This $\theta$ is dual feasible, so $P(x) - D(\theta) \ge P(x) - P^\star \ge 0$.

The SVM dual (statement; the ML fundamentals track covers SVMs in detail). The dual of the support vector machine uses the data only through inner products $x_i^\top x_j$, so a kernel $k(x_i, x_j)$ can replace them. Stationarity gives $w = \sum_i \alpha_i y_i x_i$, and complementary slackness gives $\alpha_i > 0$ only for points on the margin: the support vectors.

Answers to section 1. (1) The road touches the contour line (section 2.1). (2) By about $4\delta$, because $\lambda = 4$ (section 2.4). (3) No. The projection shifts all entries by the same $\nu$ and then clips; it does not rescale. The answer is $(0.7, 0.3, 0)$ (section 4). The rescaled point is feasible but farther from $y$.

4. Worked example #

(a) KKT, multiplier, dual and certificate. Minimize $f_0(x) = (x_1 - 2)^2 + (x_2 - 1)^2$ subject to $f_1(x) = x_1 + x_2 - 1 \le 0$. This is the projection of $(2, 1)$ onto a half-plane.

• Which case? The unconstrained minimizer $(2, 1)$ has $x_1 + x_2 = 3 > 1$. It is infeasible, so the constraint must be active ($\lambda > 0$).
• Stationarity: $\nabla f_0 + \lambda \nabla f_1 = 0$ reads $2(x_1 - 2) + \lambda = 0$ and $2(x_2 - 1) + \lambda = 0$. So $x = (2 - \lambda/2,\ 1 - \lambda/2)$.
• Active constraint: $(2 - \lambda/2) + (1 - \lambda/2) = 1$ gives $3 - \lambda = 1$, so $\lambda^\star = 2$. Then $x^\star = (1, 0)$ and $p^\star = 1 + 1 = 2$.
• Check all four conditions: $f_1(x^\star) = 0 \le 0$ ✓; $\lambda^\star = 2 \ge 0$ ✓; $\lambda^\star f_1(x^\star) = 0$ ✓; $\nabla f_0(x^\star) + \lambda^\star \nabla f_1 = (-2, -2) + 2(1, 1) = 0$ ✓. The problem is convex, so $x^\star$ is optimal (theorem above).
• Sensitivity: with $x_1 + x_2 \le 1 + u$, the same steps give $\lambda = 2 - u$ and $p^\star(u) = 2(\lambda/2)^2 = (2 - u)^2/2$. So $dp^\star/du = -(2 - u) = -2 = -\lambda^\star$ at $u = 0$. For $u = 0.1$: $p^\star = 1.9^2/2 = 1.805$, and the linear estimate gives $2 - 2(0.1) = 1.8$.
• Dual: for fixed $\lambda$, $\mathcal L$ is minimized at $x(\lambda) = (2 - \lambda/2,\ 1 - \lambda/2)$. Substitute: $g(\lambda) = 2(\lambda/2)^2 + \lambda(3 - \lambda - 1) = 2\lambda - \lambda^2/2$. Its maximum is at $\lambda = 2$ with $d^\star = 4 - 2 = 2 = p^\star$. (Slater holds: $x = (0, 0)$ is strictly feasible.)
• Certificate: the feasible guess $x = (0.5, 0.5)$ has $f_0 = 2.25 + 0.25 = 2.5$. The price $\lambda = 1$ gives $g(1) = 2 - 0.5 = 1.5$. The gap is $2.5 - 1.5 = 1$, so $f_0(x) - p^\star \le 1$ without solving anything. (The true value is $2.5 - 2 = 0.5$.)

(b) Simplex projection of $y = (1.0, 0.6, -0.4)$. Sorted: $u = (1.0, 0.6, -0.4)$, partial sums $1.0,\ 1.6,\ 1.2$.

• $j = 1$: $1.0 - (1.0 - 1)/1 = 1.0 > 0$.
• $j = 2$: $0.6 - (1.6 - 1)/2 = 0.3 > 0$.
• $j = 3$: $-0.4 - (1.2 - 1)/3 \approx -0.467 < 0$.

So $\rho = 2$ and $\nu = (1.6 - 1)/2 = 0.3$. Then $x = \max(y - 0.3, 0) = (0.7, 0.3, 0)$, which sums to 1 ✓. The multipliers are $\lambda = (0, 0, \nu - y_3) = (0, 0, 0.7)$, and stationarity $x - y + \nu\mathbf 1 - \lambda = (0.7 - 1 + 0.3,\ 0.3 - 0.6 + 0.3,\ 0 + 0.4 + 0.3 - 0.7) = 0$ ✓. The squared distance to $y$ is $0.09 + 0.09 + 0.16 = 0.34$, against $0.35125$ for the rescaled point $(0.625, 0.375, 0)$.

(c) A lasso certificate. $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$, $b = (1, 2, -0.5)$, $\lambda = 1$. (Lesson 09 solves it: $x^\star = (1, 0)$, $P^\star = 1.625$.) Take the guess $x = (0.5, 0)$.

• $r = b - Ax = (1, 2, -0.5) - (0.5, 0.5, 0) = (0.5, 1.5, -0.5)$ and $A^\top r = (0.5 + 1.5,\ 0.5 - 0.5) = (2, 0)$. So $s = \min(1, 1/2) = 0.5$ and $\theta = (0.25, 0.75, -0.25)$.
• $P(x) = \tfrac12(0.25 + 2.25 + 0.25) + 0.5 = 1.875$.
• $D(\theta) = \tfrac12\|b\|^2 - \tfrac12\|b - \theta\|^2 = \tfrac12(5.25) - \tfrac12(0.5625 + 1.5625 + 0.0625) = 1.53125$.
• The gap $1.875 - 1.53125 = 0.34375$ bounds the true suboptimality $P(x) - P^\star = 0.25$ ✓. At $x^\star = (1, 0)$: $r = (0, 1, -0.5)$ and $A^\top r = (1, -0.5)$, so $s = 1$, $\theta = r$, and the gap is 0.

5. In code #

SciPy's general constrained solver (SLSQP) checks the hand results. The notebook builds the simplex projection, the multipliers and the lasso gap yourself.

import numpy as np
from scipy.optimize import minimize

# (a) min (x1-2)^2 + (x2-1)^2  s.t.  x1 + x2 <= c, at c = 1
f = lambda x: (x[0] - 2) ** 2 + (x[1] - 1) ** 2

def solve(c):
    con = {"type": "ineq", "fun": lambda x: c - x[0] - x[1]}   # SciPy wants fun(x) >= 0
    return minimize(f, np.zeros(2), method="SLSQP", constraints=[con], tol=1e-12)

res = solve(1.0)
print(res.x.round(6) + 0.0, round(res.fun, 6))                  # [1. 0.] 2.0
print(res.multipliers.round(6))                                 # [2.]  (SciPy >= 1.16)
h = 1e-3                                                        # multiplier = sensitivity
print(round(-(solve(1 + h).fun - solve(1 - h).fun) / (2 * h), 6))   # 2.0

# (b) projection of y onto the probability simplex
y = np.array([1.0, 0.6, -0.4])
res = minimize(lambda x: 0.5 * np.sum((x - y) ** 2), np.ones(3) / 3, method="SLSQP",
               bounds=[(0, None)] * 3, tol=1e-12,
               constraints=[{"type": "eq", "fun": lambda x: x.sum() - 1}])
naive = np.maximum(y, 0) / np.maximum(y, 0).sum()               # clip and renormalize
print(res.x.round(6) + 0.0, naive)                              # [0.7 0.3 0. ] [0.625 0.375 0.   ]
print(np.sum((res.x - y) ** 2).round(5), np.sum((naive - y) ** 2).round(5))   # 0.34 0.35125

# (c) least norm: min ||x||^2 s.t. 3 x1 + 4 x2 = 10
A, b = np.array([[3.0, 4.0]]), np.array([10.0])
x_star = np.linalg.pinv(A) @ b
d_star = b @ np.linalg.solve(A @ A.T, b)
print(x_star, round(x_star @ x_star, 12), d_star)               # [1.2 1.6] 4.0 4.0

SLSQP does not use the structure of the problem and is slow for large $n$. The KKT derivation of the simplex projection is exact and costs $O(n \log n)$.

6. Where it shows up #

• Support vector machines. The SVM is usually solved in the dual: the data enter only through inner products, so kernels can replace them, and complementary slackness makes the solution depend only on the support vectors.
• Stopping rules with a guarantee. scikit-learn's Lasso and ElasticNet build the dual point of section 3 from the residual and stop when the duality gap is small. "Gap safe" screening rules use the same gap to remove features that must be zero.
• Simplex constraints. Sparsemax (Martins and Astudillo, 2016) is exactly the Euclidean projection onto the simplex. Unlike softmax, it gives exact zeros, which makes attention weights sparse. Mixture weights and portfolio weights use the same projection.
• Constrained training. Fairness constraints, safety constraints in reinforcement learning (constrained MDPs) and budget constraints are often handled with a Lagrangian: the multiplier is learned by gradient ascent while the model is trained by gradient descent.
• ML for science: PDE constraints and adjoints. To minimize a loss $J(u, \theta)$ subject to a discretized PDE $F(u, \theta) = 0$ (state $u$, parameters $\theta$), form $J + \mu^\top F$ with a multiplier vector $\mu$. Stationarity in $u$ is the adjoint equation $(\partial F/\partial u)^\top \mu = -(\partial J/\partial u)^\top$, and then $dJ/d\theta = \partial J/\partial\theta + \mu^\top \partial F/\partial\theta$. The adjoint vector is the multiplier of the state equation (Johnson's notes below). Strong-constraint 4D-Var in weather forecasting uses the forecast model as the constraint; its multipliers solve the adjoint model backward in time.

7. Common mistakes #

• Wrong sign of $\lambda$. The rule $\lambda \ge 0$ holds for constraints written as $f_i(x) \le 0$ and added as $+\lambda_i f_i$. For $x_1 + x_2 \ge 2$, write $2 - x_1 - x_2 \le 0$ first. Equality multipliers $\nu$ have no sign condition.
• Checking only one case. Complementary slackness is a case split: each constraint is either active or has a zero multiplier. If the guess "active" gives $\lambda < 0$, the constraint is inactive.
• Treating every Lagrange point as a minimum. $\nabla f + \nu\nabla h = 0$ also holds at constrained maxima. Without convexity, compare the candidates.
• "Strong duality, because it is convex." Convexity is not enough. You need a constraint qualification such as Slater's condition (exercise 5.21 above).
• Ignoring the implicit constraints of the dual. Where $g = -\infty$ the dual point gives no bound. For the lasso this is $\|A^\top\theta\|_\infty \le \lambda$; a "gap" computed from an infeasible $\theta$ certifies nothing.
• Clip-and-renormalize for the simplex. The result is feasible, but it is not the projection.

8. Check yourself #

1. Why is the dual function concave even when the primal problem is not convex?
   Answer

   For each fixed $x$, $\mathcal L(x, \lambda, \nu)$ is affine in $(\lambda, \nu)$. The dual function is the pointwise infimum of this family of affine functions (their lower envelope), and such an infimum is concave.
2. Minimize $x_1 + 2x_2$ on the ellipse $\tfrac14 x_1^2 + x_2^2 = 1$ with a Lagrange multiplier. Give the minimizer and $\nu$.
   Answer

   $\nabla f = (1, 2)$ and $\nabla h = (x_1/2, 2x_2)$. Stationarity: $1 + \nu x_1/2 = 0$ and $2 + 2\nu x_2 = 0$, so $x_1 = -2/\nu$ and $x_2 = -1/\nu$. The constraint gives $1/\nu^2 + 1/\nu^2 = 1$, so $\nu = \pm\sqrt2$. For $\nu = \sqrt2$: $x = (-\sqrt2, -1/\sqrt2)$ with $f = -2\sqrt2 \approx -2.83$, the minimum. For $\nu = -\sqrt2$: $x = (\sqrt2, 1/\sqrt2)$ with $f = 2\sqrt2$, the maximum.
3. Solve $\min \|x\|^2$ s.t. $3x_1 + 4x_2 = 10$ through the dual. What does the price $\nu = -1$ tell you?
   Answer

   $AA^\top = 25$, so $g(\nu) = -\tfrac{25}{4}\nu^2 - 10\nu$. Its maximum is at $\nu^\star = -0.8$ with $d^\star = -4 + 8 = 4$, and $x^\star = (3, 4) \cdot 10/25 = (1.2, 1.6)$ with $p^\star = 4$. Any $\nu$ gives a lower bound: $g(-1) = -6.25 + 10 = 3.75 \le 4$.
4. Take $\min x$ s.t. $x^2 \le 0$. Find $p^\star$ and $d^\star$. Is the dual optimum attained?
   Answer

   Only $x = 0$ is feasible, so $p^\star = 0$. For $\lambda > 0$, $g(\lambda) = \inf_x (x + \lambda x^2) = -1/(4\lambda)$ (at $x = -1/(2\lambda)$), and $g(0) = -\infty$. So $d^\star = \sup_\lambda g = 0 = p^\star$, but no $\lambda$ attains it. No KKT multiplier exists (stationarity $1 = 0$ fails), because Slater's condition fails.
5. In a hard-margin SVM, a training point has $y_i(w^\top x_i + b) > 1$. What is $\alpha_i$, and what happens if you delete the point?
   Answer

   $\alpha_i = 0$ by complementary slackness, because its constraint is not tight. It does not appear in $w = \sum_i \alpha_i y_i x_i$, so deleting it does not change the solution.
6. For the lasso, show that $x = 0$ is optimal exactly when $\lambda \ge \|A^\top b\|_\infty$.
   Answer

   If $\|A^\top b\|_\infty \le \lambda$, then $\theta = b$ is dual feasible, and the gap at $x = 0$ is $P(0) - D(b) = \tfrac12\|b\|^2 - \tfrac12\|b\|^2 = 0$, so $x = 0$ is optimal. Conversely, if $x^\star = 0$, then $\theta^\star = b - A \cdot 0 = b$ must be dual feasible. So $\lambda_{\max} = \|A^\top b\|_\infty$ is where the lasso path starts.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. At a constrained minimum of $f$ on the curve $h(x) = 0$, how are $\nabla f$ and $\nabla h$ related, and why?

   Show answer

2. Write the Lagrangian of $\min f_0(x)$ s.t. $f_i(x) \le 0$, $h_j(x) = 0$.

   Show answer

3. What does a Lagrange multiplier $\lambda_i^\star$ mean?

   Show answer

4. Name the four KKT conditions.

   Show answer

5. What does complementary slackness say in words?

   Show answer

6. What is Slater's condition, and what does it give?

   Show answer

7. State weak duality.

   Show answer

8. How does a duality gap act as a stopping certificate?

   Show answer

9. Give the Euclidean projection of $y$ onto the probability simplex.

   Show answer

10. Compute the multiplier of $\min (x - 3)^2$ s.t. $x \le 1$.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What does a Lagrange multiplier mean?" — A price: the rate at which the optimal value improves when the constraint is relaxed. Zero for an inactive constraint.
• "Explain Lagrange multipliers geometrically." — At the constrained optimum a level set of the objective is tangent to the constraint surface, so the two gradients are parallel.
• "Are the KKT conditions necessary? Sufficient?" — Sufficient for convex problems; necessary under Slater's condition (convex) or a constraint qualification such as LICQ (general).
• "Weak versus strong duality?" — $d^\star \le p^\star$ always; equality for convex problems under Slater.
• "Why solve the SVM in the dual?" — Kernels (the data enter only through inner products), simple box constraints, and a sparse solution (support vectors).
• "How do you know an iterative solver is done?" — A duality gap bounds the suboptimality without knowing $p^\star$.
• "Project a vector onto the simplex in $O(n \log n)$." — Sort, find $\rho$ and $\nu$, shift and clip.

10. Practice #

The notebook for this lesson runs in Colab. Each exercise has a check cell and a folded solution.

1. Solve the equality example as a linear KKT system, and check that the multiplier equals the numerical sensitivity $-dp^\star/dc$.
2. Project onto a box and onto the probability simplex, return the multipliers, and verify all four KKT conditions.
3. Solve the inequality example with scipy.optimize.minimize (SLSQP) for many values of $c$, and compare the slope of $p^\star(c)$ with your $\lambda$.
4. Least norm through the dual: build dual feasible points and compute the duality gap of a guess.
5. Lasso on the diabetes data: use the duality gap of the iterates of a simple solver as a stopping rule.

11. Watch and read #

Lagrange multipliers, using tangency to solve constrained optimizationKhan Academy (Grant Sanderson) · 9 min

The tangency picture of section 2.1, with contour lines and a constraint curve.

Meaning of Lagrange multiplierKhan Academy (Grant Sanderson) · 10 min

Why the multiplier is the rate of change of the optimal value (section 2.3).

The Karush–Kuhn–Tucker (KKT) Conditions and the Interior Point Method for Convex OptimizationVisually Explained · 22 min

Duality and the KKT conditions with clear animations; the last part shows how interior-point solvers use them.

Lecture 8 | Convex Optimization I (Stanford)Stephen Boyd · Stanford EE364A · 77 min

The Lagrange dual function, weak and strong duality, and Slater's condition (book chapter 5).

• Boyd and Vandenberghe, Convex Optimization, free PDF: §5.1 (dual function; §5.1.5 least norm), §5.2 (weak duality, Slater), §5.5 (certificates, complementary slackness, KKT), §5.6 (sensitivity), exercise 5.21 (a positive gap).
• Ryan Tibshirani, CMU 10-725 Convex Optimization, lecture notes on KKT conditions and duality.
• Wang and Carreira-Perpiñán, Projection onto the probability simplex (the sort-based algorithm and its KKT proof).
• Martins and Astudillo, From softmax to sparsemax (the simplex projection as an activation).
• scikit-learn user guide, Lasso (coordinate descent with the duality-gap stopping rule).
• S. G. Johnson, Notes on adjoint methods (the adjoint vector as a Lagrange multiplier).