Constrained Optimization

Constrained optimization minimizes an optimization objective only over allowed solutions. The constraint may encode physics, budgets, fairness rules, simplex probabilities, or margins as in support vector machines.

Defining math

A constrained problem has the form

$$\underset{x}{\min }f(x)\text{subject to}{h}_i(x)=0,g_j(x)\le 0.$$

For equality constraints, the Lagrangian is

$$\mathcal{L}(x,\lambda )=f(x)+\sum _i{\lambda }_i{h}_i(x).$$

At a regular equality-constrained optimum, stationarity requires

$${\nabla }_x\mathcal{L}(x^{\star },{\lambda }^{\star })=0,h_i(x^{\star })=0.$$

The multiplier says how much the optimum would change if the constraint moved. In convex optimization, additional KKT conditions can certify global optimality, while the stationarity equation is still written in terms of gradients.

Worked example

Minimize $f(x,y)=x^2+y^2$ subject to $x+y=1$. The Lagrangian is $\mathcal{L}=x^2+y^2+\lambda (x+y-1)$, and stationarity in $x$ and $y$ gives

$$\frac{\partial \mathcal{L}}{\partial x}=2x+\lambda =0,\frac{\partial \mathcal{L}}{\partial y}=2y+\lambda =0,$$

so $x=y=-\lambda /2$. The constraint $x+y=1$ then forces $x=y=\frac{1}{2}$ (with $\lambda =-1$). The unconstrained minimum of $x^2+y^2$ is $(0,0)$, but the line $x+y=1$ pushes the closest feasible point to $(0.5,0.5)$, where the objective is $0.5^2+0.5^2=0.5$.

Caveats

Constraints can make easy-looking objectives hard. Infeasible constraints, badly scaled constraints, and active-set changes often create more numerical stability trouble than the objective itself, so monitor feasibility alongside objective value.

References

• Boyd and Vandenberghe, Convex Optimization

Nav

Section — Mathematical Foundations

← Convex Optimization Gradient Descent →