§4.4–4.5Constrained Optimization · Example: Linear Least Squares

§4.4 Constrained optimization

Sometimes we don’t want the best $\boldsymbol{x}$ anywhere — we want the best $\boldsymbol{x}$ within a set $\mathbb{S}$ of feasible points: constrained optimization constrained optimization Optimizing f over x within a feasible set S rather than all x — by projection, re-parametrization, or the KKT machinery. defined in ch. 4 — open in glossary . A typical wish is smallness, imposed as a norm constraint like $\|\boldsymbol{x}\| \le 1$:

Three simple approaches before the general machinery: project each gradient-descent result back into $\mathbb{S}$ (or run the line search line search Evaluate f(x − ε∇f) for several ε and keep the best — step-size selection by trial. defined in ch. 4 — open in glossary only over feasible step sizes, ideally after projecting the gradient into the feasible region’s tangent space); or re-parametrize the problem so the constraint is automatic — e.g. minimize $g(\theta) = f([\cos\theta, \sin\theta]^\top)$ to enforce exactly unit norm, at the price of case-by-case creativity.

The KKT machinery

The general solution: describe $\mathbb{S} = \{\boldsymbol{x} \mid \forall i,\, g^{(i)}(\boldsymbol{x}) = 0 \text{ and } \forall j,\, h^{(j)}(\boldsymbol{x}) \le 0\}$ via equality constraints $g^{(i)}$ and inequality constraints $h^{(j)}$, then build the generalized Lagrangian generalized lagrangian L(x, λ, α) = f(x) + Σλᵢg⁽ⁱ⁾(x) + Σαⱼh⁽ʲ⁾(x): converts constrained problems into unconstrained min-max over KKT multipliers. defined in ch. 4 — open in glossary :

Then, as long as at least one feasible point exists and $f$ cannot reach $\infty$,

$\min_{\boldsymbol{x}} \max_{\boldsymbol{\lambda}} \max_{\boldsymbol{\alpha}, \boldsymbol{\alpha} \ge 0} L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\alpha}) \quad\text{has the same optimum as}\quad \min_{\boldsymbol{x} \in \mathbb{S}} f(\boldsymbol{x}).$

Active vs inactive. A constraint is active if $h^{(i)}(\boldsymbol{x}^*) = 0$ — the solution sits ON its boundary. Inactive constraints ($h < 0$) get $\alpha_i = 0$: removing them would leave a local solution in place (though they may have excluded other solutions elsewhere). Either the boundary shapes the solution and its multiplier pushes, or it doesn’t and its multiplier is zeroed: complementary slackness, $\boldsymbol{\alpha} \odot \boldsymbol{h}(\boldsymbol{x}) = \boldsymbol{0}$. Together, the KKT conditions kkt conditions Necessary optimality conditions: ∇L = 0, all constraints satisfied, complementary slackness α⊙h(x) = 0 (each inequality active or its multiplier zero). defined in ch. 4 — open in glossary — necessary (not always sufficient) for optimality:

1. $\nabla L = 0$ (gradient of the generalized Lagrangian vanishes);
2. all constraints on $\boldsymbol{x}$ and the multipliers hold;
3. complementary slackness.

§4.5 Example: linear least squares

Everything in this chapter, exercised on one function — linear least squares linear least squares Minimize ½‖Ax − b‖₂²: gradient AᵀAx − Aᵀb; solvable by GD (alg 4.1), one Newton step, or the pseudoinverse. defined in ch. 4 — open in glossary . Minimize $f(\boldsymbol{x}) = \frac{1}{2}\|\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b}\|_2^2$:

The bowl being descended is exactly the lab from §4.3.1 with $\boldsymbol{H} = \boldsymbol{A}^\top\boldsymbol{A}$ — revisit it and imagine $\kappa$ as the (squared) conditioning of $\boldsymbol{A}$.

The constrained version

Now minimize the same $f$ subject to $\boldsymbol{x}^\top\boldsymbol{x} \le 1$ — the unit-disk picture at the top of this page, solved with the KKT recipe:

That concludes the mathematical preliminaries. Next: full-fledged learning systems — chapter 5, Machine Learning Basics.