Optimization under constraints.

The simplest solver follows the slope downhill:

Everything rides on the step $\tau$. Too small and convergence crawls; too large and it overshoots, oscillates, and on the quadratic below it diverges once $\tau >2/{\lambda }_{\max }$ (the largest curvature eigenvalue). The elongated, tilted contours are an ill-conditioned problem - the gradient points across the valley rather than down it, so descent zig-zags. Push $\tau$ up in the figure and watch it break.

Now require $g^{\top }x\le h$ (the clay region is forbidden), with the unconstrained minimum sitting inside it. Plain gradient descent does not care - it walks straight to the infeasible minimum. The three standard fixes are all switchable live in the figure, and each one fails or converges in its own characteristic way.

Projected gradient. Take the gradient step, then snap back onto the feasible set:

For a half-space the projection is one line of algebra; the iterates hit the boundary and slide along it to $x^{\ast }$. Exact feasibility at every step, but it only works when $P_K$ is cheap to compute.

Penalisation. Replace the hard constraint by a soft wall in the objective and run plain gradient descent on

Watch the readout: the iterate converges slightly outside the feasible set, with a violation of order $\epsilon {\lambda }^{\ast }$ - tighten ε and the bias shrinks, but the wall gets stiff: the curvature along $g$ grows like $\Vert g{\Vert }^2/\epsilon$, forcing a smaller and smaller stable step (the demo caps τ automatically and tells you when). Cheap and general, but approximate and ill-conditioned as $\epsilon \to 0$.

Uzawa. Dualise instead: introduce a multiplier $\lambda \ge 0$ on the constraint and alternate an exact primal minimisation of the Lagrangian with a projected gradient ascent on the dual:

For our quadratic the primal step is closed-form, $x_n=c-{\lambda }_n{Q}^{-1}g$, so every iterate is an exact minimiser of a relaxed problem: the trajectory walks along the curve of relaxed optima while λ climbs the gauge to the KKT price ${\lambda }^{\ast }$. If the iterate is infeasible, λ rises (the constraint gets more expensive); if it is strictly feasible, λ falls back toward zero. The dual has its own stability limit $\rho <2/(g^{\top }{Q}^{-1}g)$ - push ρ past it and the multiplier oscillates and explodes, the dual mirror of the primal step-size rule from section 01.

All three methods agree on where to stop: the point where the gradient is normal to the active constraint, the KKT condition $\nabla J(x^{\ast })=-{\lambda }^{\ast }g,{\lambda }^{\ast }\ge 0$. The multiplier they implicitly (projection, penalisation) or explicitly (Uzawa) compute is the shadow price of the constraint: how much objective you would gain per unit of constraint relaxation. That is exactly the structure behind the portfolios on the Markowitz page: minimum-variance is a quadratic objective $w^{\top }\Sigma w$ under the budget $1^{\top }w=1$, and the budget's multiplier is the price of capital. Support vector machines are the same shape - a quadratic margin objective under linear inequality constraints - and Uzawa-style dual ascent is how you solve them at scale.