From a free landscape to a fenced one
Everything in this rung so far solved unconstrained optimization: roll downhill until the gradient vanishes, because the first-order condition for a free minimum is simply grad f = 0. But almost every real problem is fenced. You minimize cost subject to a fixed budget; you fit a model subject to weights that must sum to one; you design a beam subject to a stress that must not exceed a limit. The minimum you want may sit nowhere near the bottom of the free landscape — it sits at the lowest point you can reach WITHOUT crossing the fence.
Two kinds of fence matter. An equality constraint g(x) = 0 pins you onto a curve or surface — think of a marble forced to stay exactly on a wire bent into a hoop. An inequality constraint h(x) <= 0 lets you roam inside a region but never past its boundary — a marble free to move on a tabletop but walled in by a fence. The whole art of constrained optimization is characterizing the lowest point under these restrictions, and then computing it. The genius of Lagrange is that it converts 'minimize on a surface' back into the familiar 'set a gradient to zero', which is exactly the kind of problem the earlier guides taught you to solve.
Lagrange multipliers: gradients must line up
Picture minimizing f(x) while constrained to the curve g(x) = 0. Walk along the curve. As long as you can still descend — as long as the curve points even slightly downhill on f — you keep going. You can only be stuck at a minimum when moving in either direction along the curve no longer decreases f. Geometrically that happens exactly when the gradient of f is perpendicular to the curve, i.e. it points straight along the constraint's own gradient. So at a constrained minimum the two gradients must be PARALLEL: grad f = lambda times grad g, for some single number lambda. That number is the Lagrange multiplier.
The bookkeeping trick that makes this practical is the Lagrangian, L(x, lambda) = f(x) - lambda g(x). Setting its gradient with respect to x to zero reproduces grad f = lambda grad g, and setting its derivative with respect to lambda to zero just gives back g(x) = 0, the constraint itself. So an n-variable problem with one constraint becomes a single unconstrained stationary-point problem in n + 1 unknowns (the original x plus lambda). You have traded a fenced search for a plain 'set the gradient to zero' — solvable by Newton's method or any tool from the earlier guides.
minimize f(x) = x^2 + y^2 subject to g(x) = x + y - 1 = 0 Lagrangian: L = (x^2 + y^2) - lambda (x + y - 1) grad_x L = 0 : 2x - lambda = 0 grad_y L = 0 : 2y - lambda = 0 grad_lambda L = 0 : x + y - 1 = 0 => x = y = lambda/2, and x + y = 1 => x = y = 1/2, lambda = 1 (closest point of the line x+y=1 to the origin: (1/2, 1/2), as geometry predicts)
Inequalities and the KKT conditions
Equalities are the easy half. Most real fences are inequalities: h(x) <= 0. Now a subtlety appears. At the optimum each inequality is in one of two states. Either it is inactive — the minimum sits comfortably inside the region, the fence is slack, and the constraint is irrelevant, exactly as if it were not there. Or it is active — the minimum is pressed right up against the boundary h(x) = 0, where the fence is doing real work and behaves like an equality. The hard part is that you do not know in advance WHICH constraints will be active; that is what the solver must discover.
The KKT conditions (Karush-Kuhn-Tucker) package this 'active or not' logic into clean algebra and generalize Lagrange to inequalities. They are the cornerstone optimality conditions for constrained problems, and every constrained solver is, at heart, a machine for satisfying them. There are four parts, and the third is the clever one.
- Stationarity: the gradient of the Lagrangian vanishes — grad f = sum of mu_i times grad h_i — so f's gradient is balanced by the active constraints' gradients, just like the equality case.
- Primal feasibility: the point actually obeys every constraint, h_i(x) <= 0. An answer that violates the fence is no answer at all.
- Complementary slackness: for each inequality, mu_i times h_i(x) = 0 — so either the multiplier mu_i is zero (constraint inactive, ignore it) or h_i(x) is zero (constraint active, on the boundary). They cannot both be nonzero. This single equation encodes the whole 'which fences matter' question.
- Dual feasibility: each inequality multiplier is non-negative, mu_i >= 0. The sign matters — it says an active fence can only PUSH the solution inward, never pull it outward, which is what distinguishes a constrained minimum from a maximum.
A crucial honesty: the KKT conditions are NECESSARY for an optimum (under a mild regularity assumption on the constraints), but in general they are not SUFFICIENT — a point satisfying them could be a minimum, a maximum, or a saddle point, exactly as grad f = 0 alone never settled things in the unconstrained case. There is one beautiful exception, and it is the subject of the next section.
Convexity: when KKT is the whole answer
Recall from the gradient-descent and Newton guides why convexity was such a gift: a convex function has a bowl shape with no false bottoms, so any point where the gradient vanishes is the GLOBAL minimum, not merely a local one. The same magic carries over to constraints. When the objective is convex and the feasible region is convex (every constraint convex, equalities linear), the KKT conditions flip from merely necessary to fully SUFFICIENT: any point satisfying them is a guaranteed global optimum. You can stop the instant KKT holds and know you have truly won.
This is why practitioners work so hard to cast a problem as convex. Two convex families dominate. Linear programming (LP) minimizes a linear objective over linear constraints — the feasible region is a polyhedron, a many-faced crystal, and the optimum always sits at one of its corners (vertices). Quadratic programming (QP) allows a convex quadratic objective with linear constraints — the workhorse behind support vector machines, portfolio optimization, and the trust-region subproblems you met earlier. For both, KKT plus convexity means a solution found is a solution proved.
Solving them on a computer: barriers, interior points, and simplex
How do you actually MAKE a computer find the KKT point? The most intuitive idea is the penalty method: add a big penalty to the objective whenever a constraint is violated, so the unconstrained minimum of the penalized function drifts toward the feasible region. It is simple and it works, but it has a flaw — to push the answer tightly onto the constraint you must crank the penalty weight up, and a huge weight makes the problem savagely ill-conditioned, so the condition number blows up and (as the conditioning rung warned) you bleed accuracy, losing roughly a digit for every factor of ten you add.
The modern fix is the interior-point method, which approaches the boundary from the inside using a barrier instead of a penalty. Add a logarithmic barrier term that grows to plus infinity as you near any fence, so the iterate is repelled and stays strictly interior. Then gradually shrink the barrier's strength toward zero; the sequence of interior minima traces a smooth 'central path' that glides toward the true KKT point right on the boundary. Each step is essentially a Newton step on the KKT equations, and the whole method converges in a remarkably small, nearly problem-independent number of iterations — the breakthrough that made huge LPs and QPs routine.
For linear programming there is also the classic simplex method, with an utterly different geometry. Since the LP optimum lives at a vertex of the feasible polyhedron, the simplex method simply walks from corner to corner along the edges, each step moving to an adjacent vertex that improves the objective, until no neighbour is better. It is elegant and superbly fast in practice — yet here is a famous honesty: in the worst case it can be forced to visit an exponential number of vertices, so it is NOT polynomial-time, even though such worst cases essentially never arise in real life. Interior-point methods, by contrast, carry a polynomial-time guarantee. Both are battle-tested; which wins depends on the problem.
Closing the rung
Step back and see the whole rung. You learned to read a landscape through its gradient and Hessian, to roll downhill with gradient descent and feel its zig-zag on ill-conditioned bowls, to leap with Newton and approximate the Hessian cheaply via quasi-Newton, to train on noisy mini-batches with stochastic gradient descent — and now, to optimize inside a fence. The bridge that ties it all together is one idea: constrained optimality is just unconstrained optimality of an augmented function. Lagrange builds that function for equalities; KKT extends it to inequalities; barriers and simplex are the engines that hunt the point down.
And keep the field's permanent caveats close. Every number a solver returns is an APPROXIMATION found in finite floating-point arithmetic, never exact real arithmetic; a stable interior-point step still cannot rescue a wildly ill-conditioned constraint geometry. Newton-flavoured steps converge fast only near a good iterate. KKT only certifies a global optimum when the problem is convex; outside that world, 'a solution' means a local one. Honesty about these limits is not a weakness of numerical optimization — it is what lets you trust the answers it does give.