Lagrange Multipliers and the KKT Conditions
Constraints change the game. At a constrained optimum the gradient is almost never zero — the boundary is holding you back from an even lower valley. The genius of Lagrange was to turn that resistance into an equation: at the optimum the objective's gradient must line up with the constraint's. This chapter builds that idea for equalities, reads the multiplier as a price, and then generalizes to inequalities through the celebrated Karush–Kuhn–Tucker conditions — the master optimality test for the whole of nonlinear programming.
- Why \(\nabla f = 0\) fails once constraints appear, and the tangency condition that replaces it.
- The Lagrangian and the method of Lagrange multipliers for equality constraints.
- How to read a multiplier as a shadow price — the sensitivity of the optimum to the constraint.
- The four KKT conditions: stationarity, primal feasibility, dual feasibility, and complementary slackness.
- What complementary slackness says about active versus inactive inequality constraints.
- When the KKT conditions are merely necessary, and when — for convex problems — they are sufficient for a global optimum.
Why Constraints Change Everything
Chapter 4 found optima by demanding a flat slope, \(\nabla f = 0\). That test collapses the moment a constraint appears. Consider minimizing \(x^2 + y^2\): the unconstrained answer is the origin, where the gradient vanishes. Now insist that \(x + y = 1\). The origin is no longer allowed, and at the true constrained optimum the gradient is not zero — the function is still trying to pull us toward the origin, but the constraint line blocks the way.
The right question is not "where is the slope zero?" but "where can we no longer improve without leaving the constraint?" That happens where the objective's contour just grazes the constraint — a point of tangency. And at a tangency, the gradient of the objective and the gradient of the constraint point along the same line. Turning that geometric fact into algebra is exactly what Lagrange multipliers do.
Equality Constraints: The Lagrangian
For the problem \(\min f(x)\) subject to \(h(x) = 0\), the tangency insight says \(\nabla f\) must be parallel to \(\nabla h\) at the optimum: \(\nabla f = \lambda\, \nabla h\) for some scalar \(\lambda\), the Lagrange multiplier. We package this into a single function, the Lagrangian, whose stationary points reproduce both the tangency and the constraint:
Setting the gradient of \(\mathcal{L}\) with respect to both \(x\) and \(\lambda\) to zero yields \(n + m\) equations: the tangency conditions and the original constraints. Solving them together gives the candidate optimum \(x^\star\) and the multipliers \(\lambda\).
The Lagrange Multiplier Method
The recipe is mechanical. (1) Form the Lagrangian \(\mathcal{L}(x,\lambda) = f(x) - \sum_j \lambda_j h_j(x)\). (2) Take partial derivatives with respect to every \(x_i\) and every \(\lambda_j\) and set them to zero. (3) Solve the resulting system for \(x^\star\) and \(\lambda^\star\). (4) If needed, confirm the point is a minimum (not a maximum or saddle) using the bordered-Hessian test or, far more simply, by checking convexity.
The Multiplier as a Shadow Price
Suppose the constraint is \(h(x) = b\) and let \(f^\star(b)\) be the optimal value as the right-hand side \(b\) varies. A central result is that the multiplier measures exactly how sensitive the optimum is to that level:
This is why economists call \(\lambda\) a shadow price: it is the most you should be willing to pay for one more unit of the constrained resource. A large multiplier flags a tight, valuable constraint worth relaxing; a multiplier of zero means the constraint is not really costing you anything at the optimum. (Sign conventions differ between textbooks; the magnitude is the marginal value, and the sign records the direction of the effect.)
Inequality Constraints: The KKT Conditions
Real problems have inequalities too. The general nonlinear program is \(\min f(x)\) subject to \(g_i(x) \le 0\) and \(h_j(x) = 0\). Its optimality test is the Karush–Kuhn–Tucker (KKT) conditions — the crowning result of classical optimization, generalizing Lagrange to inequalities. Build the Lagrangian with a multiplier for every constraint, using \(\mu_i \ge 0\) for the inequalities:
| KKT condition | Statement | Meaning |
|---|---|---|
| Stationarity | \(\nabla f + \sum_i \mu_i \nabla g_i + \sum_j \lambda_j \nabla h_j = 0\) | No improving direction remains |
| Primal feasibility | \(g_i(x) \le 0,\ \ h_j(x) = 0\) | The point obeys the constraints |
| Dual feasibility | \(\mu_i \ge 0\) | Inequality multipliers are non-negative |
| Complementary slackness | \(\mu_i\, g_i(x) = 0\) | Either the constraint is active or its multiplier is zero |
At any (regular) local optimum, all four hold. Note the dual-feasibility sign \(\mu_i \ge 0\): a binding inequality can only push the optimum one way, so its multiplier cannot go negative — unlike an equality multiplier \(\lambda_j\), which is free in sign.
Complementary Slackness
The most revealing KKT condition is complementary slackness, \(\mu_i g_i(x) = 0\). It forces a clean either/or at every inequality: either the constraint is active (\(g_i = 0\), the boundary is touched) and its multiplier may be positive, or it is inactive (\(g_i < 0\), slack to spare) and its multiplier must be zero. A constraint that is not binding exerts no price on the optimum.
This is what makes KKT solvable by hand. Complementary slackness lets you split the problem into cases: guess which constraints are active, set those \(g_i = 0\) and the rest of the \(\mu_i = 0\), solve the resulting equality system, then check that the leftover conditions (\(\mu_i \ge 0\) for active ones, \(g_i \le 0\) for inactive ones) actually hold. If they do, you have found a KKT point.
KKT, Sufficiency, and Convexity
By default the KKT conditions are only necessary: a genuine optimum satisfies them, but so might a saddle or a maximum, and they assume a mild regularity ("constraint qualification," e.g. Slater's condition that a strictly feasible point exists). The great payoff comes with convexity. If \(f\) and the \(g_i\) are convex and the \(h_j\) affine, then KKT becomes both necessary and sufficient — any point satisfying all four conditions is a global optimum.
This is the theoretical foundation for almost every reliable nonlinear solver. Verify convexity, write the KKT system, solve it, and the solution is guaranteed globally optimal — the same clean guarantee that made classical unconstrained optimization complete for convex functions in Chapter 4.
Worked Examples
Problem. Minimize \(f = x^2 + y^2\) subject to \(x + y = 1\). Find \(x^\star\) and interpret \(\lambda\).
Solution. \(\mathcal{L} = x^2 + y^2 - \lambda(x + y - 1)\). Then \(\partial_x\mathcal{L} = 2x - \lambda = 0\) and \(\partial_y\mathcal{L} = 2y - \lambda = 0\), so \(x = y = \lambda/2\). The constraint gives \(x + y = 1 \Rightarrow \lambda = 1\), hence \(x^\star = y^\star = \tfrac12\), \(f^\star = \tfrac12\).
The multiplier \(\lambda = 1\) is exactly the marginal cost of tightening the budget \(b\).
Problem. Maximize \(A = xy\) subject to \(x + y = 10\).
Solution. \(\mathcal{L} = xy - \lambda(x + y - 10)\). Then \(\partial_x = y - \lambda = 0\) and \(\partial_y = x - \lambda = 0\), forcing \(x = y = \lambda\). The constraint gives \(2\lambda = 10 \Rightarrow \lambda = 5\), so \(x = y = 5\) and \(A = 25\). The tangency \(\nabla A = \lambda \nabla h\) recovers the familiar "square is best" result.
Problem. Minimize \(x^2 + y^2 + z^2\) subject to \(x + 2y + 3z = 14\).
Solution. \(\mathcal{L} = x^2+y^2+z^2 - \lambda(x+2y+3z-14)\). Stationarity gives \(2x = \lambda,\ 2y = 2\lambda,\ 2z = 3\lambda\), i.e. \(x = \tfrac{\lambda}{2},\ y = \lambda,\ z = \tfrac{3\lambda}{2}\). Substituting into the plane:
The nearest point on the plane is \((1,2,3)\), the squared distance is \(14\), and the objective is convex, so this is the global minimum.
Problem. Minimize \((x - 3)^2 + (y - 2)^2\) subject to \(x + y \le 1\).
Solution. The unconstrained minimum \((3,2)\) has \(x + y = 5 > 1\) — infeasible, so the constraint is active (\(g = x + y - 1 = 0\)). KKT stationarity \(\nabla f + \mu\nabla g = 0\) gives \(2(x-3) + \mu = 0\) and \(2(y-2) + \mu = 0\), so \(x = 3 - \tfrac{\mu}{2},\ y = 2 - \tfrac{\mu}{2}\). Imposing \(x + y = 1\):
Dual feasibility (\(\mu = 4 \ge 0\)) and complementary slackness (\(g = 0\)) both hold, so \((1,0)\) is the KKT point — and, the problem being convex, the global optimum.
Problem. Minimize \((x - 0.2)^2 + (y - 0.3)^2\) subject to \(x + y \le 1\).
Solution. The unconstrained minimum is \((0.2, 0.3)\), where \(g = 0.5 - 1 = -0.5 < 0\): the constraint has slack. Complementary slackness \(\mu g = 0\) with \(g < 0\) forces \(\mu = 0\), and stationarity reduces to \(\nabla f = 0\), confirming \(x^\star = (0.2, 0.3)\), \(f^\star = 0\). The constraint is present but priceless — its multiplier is zero.
Problem. Minimize \(x^2 + y^2\) subject to \(x + y \ge 4,\ x \ge 0,\ y \ge 0\).
Solution. Write \(g_1 = 4 - x - y \le 0,\ g_2 = -x \le 0,\ g_3 = -y \le 0\). Guess \(g_1\) active, \(x, y > 0\) so \(\mu_2 = \mu_3 = 0\). Stationarity: \(2x - \mu_1 = 0,\ 2y - \mu_1 = 0 \Rightarrow x = y\). Active \(g_1\): \(x + y = 4 \Rightarrow x = y = 2\), and \(\mu_1 = 2x = 4 \ge 0\).
Every condition checks out and the problem is convex, so \((2,2)\) is the global minimum. Note how complementary slackness let us guess-and-verify the active set rather than solve a messy simultaneous system.
Chapter Summary
At an equality-constrained optimum, \(\nabla f = \lambda\nabla h\) — the contour is tangent to the constraint.
Form \(\mathcal{L} = f - \sum\lambda_j h_j\); set \(\nabla_x\mathcal{L}=0\) and \(\nabla_\lambda\mathcal{L}=0\) and solve.
\(\lambda^\star = \partial f^\star / \partial b\): the marginal value of relaxing the constraint.
Stationarity, primal feasibility, dual feasibility (\(\mu_i \ge 0\)), and complementary slackness (\(\mu_i g_i = 0\)).
Complementary slackness splits constraints into active (\(g_i=0\)) and inactive (\(\mu_i=0\)) — solve by cases.
For a convex program with constraint qualification, a KKT point is the global optimum.
Problems
For each item, form the Lagrangian or KKT system, solve, and check the multiplier signs and slackness. Difficulty rises down the list.
- Minimize \(x^2 + y^2\) subject to \(2x + y = 5\); find \(x^\star\), \(\lambda^\star\), and the shadow price.
- Maximize \(f = xy\) subject to \(x + 4y = 16\).
- Minimize \(x^2 + 2y^2\) subject to \(x + y = 6\); confirm the answer is a minimum.
- Find the point on the plane \(2x - y + 2z = 9\) closest to the origin using a multiplier.
- Maximize \(f = x + 2y\) subject to \(x^2 + y^2 = 5\) (a nonlinear equality).
- Minimize \((x-4)^2 + (y-4)^2\) subject to \(x + y \le 4\); identify whether the constraint is active and find \(\mu\).
- Minimize \((x-1)^2 + (y-1)^2\) subject to \(x + y \le 5\); show the constraint is inactive and state \(\mu\).
- Write the full KKT system for \(\min\ x^2 + y^2\) s.t. \(x \ge 1,\ y \ge 2\), and solve it.
- Explain, in one or two sentences each, why (a) equality multipliers are unrestricted in sign but (b) inequality multipliers must be \(\ge 0\).
- State complementary slackness in words and give a physical example (e.g. a resource that is not fully used has zero shadow price).
- For \(\min\ f = x_1 + x_2\) s.t. \(x_1^2 + x_2^2 \le 2,\ x_1, x_2 \ge 0\), find the KKT point and argue it is global.
- A firm minimizes cost \(C = x^2 + xy + y^2\) subject to an output requirement \(x + y \ge 6\) and \(x, y \ge 0\). Solve the KKT system, determine the active set, report the shadow price of the output requirement, and state how much cost would fall if the requirement were eased to \(x + y \ge 5\).