1.11 Constrained optimization

What this is and why it exists

Real optimization rarely runs free: probabilities must sum to one, budgets cap spending, margins must exceed thresholds. Constrained optimization is the machinery for "minimise this, SUBJECT TO that", and its vocabulary — Lagrangians, KKT, duality — is the standing prerequisite for reading half the ML literature, SVMs first among them. The goal here is reading fluency, not proof mastery.

The vocabulary

• Lagrange multiplier — a new variable per constraint that prices it into the objective.
• Lagrangian — objective plus multiplier-times-constraint: one unconstrained-looking function carrying the whole problem.
• KKT conditions — the first-order requirements at a constrained optimum, inequality constraints included.
• Complementary slackness — per constraint: either it is tight (active) or its multiplier is zero — never both slack and priced.
• Duality — every minimisation has a shadow maximisation over the multipliers; solving one illuminates the other.
• Projected gradient — step downhill, then snap back to the feasible set; the constrained loop.
• Penalty method — replace the wall with a spring: add a term punishing violation, and tighten it.

The mental model

At a constrained optimum on a boundary, two forces balance. You want to walk downhill, the constraint surface fences you in — and the stopping condition is that steepest descent points STRAIGHT INTO the fence: the objective's gradient is parallel to the constraint's gradient. The multiplier is the ratio between them, and its VALUE is a price — how much the optimum would improve per unit of constraint relaxation. Economists call multipliers shadow prices for exactly this reason. The Lagrangian is the bookkeeping that turns "gradients parallel" into "set derivatives of one function to zero".

Inequalities add one honest wrinkle. A constraint you never touch (spending under an ample budget) might as well not exist — multiplier zero. A constraint you press against is active — positive multiplier, a real price. Complementary slackness is that either/or, and KKT is the full checklist: stationarity of the Lagrangian, feasibility, non-negative multipliers, slackness. Read a paper's "by KKT…" as: at the optimum, only the active constraints matter, and they carry prices.

Duality is the move that explains SVM notation forever: instead of minimising over weights subject to margin constraints, maximise over the constraints' multipliers. In the dual, the data appears ONLY through pairwise dot products — which is what lets kernels replace those dot products and buy nonlinearity (the classical-ML module's kernel trick) — and the points with nonzero multipliers are exactly the ones pressing on the margin: the support vectors, named at last. That is why SVMs are STATED in dual form: the dual is where both the kernels and the sparsity live.

When analysis gives way to iteration, two workhorses: projected gradient — ordinary descent, then project back into the feasible set each step (feasible sets with cheap projections, like boxes and balls, make this trivially practical); and penalty methods — add a violation-punishing term with a growing weight, turning the hard wall into a stiffening spring. Weight-decay regularization is a soft constraint in exactly this sense — la6's constrained-projection picture, met from the other side.

What you should now be able to explain or do

Solve a small equality-constrained problem with a Lagrangian. Interpret a multiplier as a price. Walk the KKT checklist and use slackness to spot active constraints. Say why SVMs go dual, and choose projected-gradient or penalty for a given feasible set.

Check yourself