Past exam of the mathematics course of the University of Cambridge / 2003 / ib / Paper 4 / 5H / Solution

For constrained optimization in minimization form, let $x\in X$, $g_i(x)\le 0$ and $h_j(x)=0$, and define the LagrangianThe Lagrangian sufficiency theorem says: if $x_{\ast }$ is feasible, ${\lambda }_i\ge 0$, ${\lambda }_i{g}_i(x_{\ast })=0$ for every $i$, and $x_{\ast }$ minimizes $L(\cdot ,\lambda ,\nu )$ globally over $X$, then $x_{\ast }$ minimizes $f$ over the feasible set. Equality multipliers ${\nu }_j$ may have either sign.

Indeed, for every feasible $x$,The first inequality uses the inequality-multiplier signs and the equality constraints; the last equality uses complementary slackness. This proves global optimality without assuming convexity or differentiability. The maximization version reverses the relevant signs, or follows by replacing $f$ with $-f$.

When $X$ is convex and the Lagrangian is differentiable and convex, the first-order condition ${\nabla }_{x}L(x_{\ast })=0$ implies its global minimum, because $L(x)\ge L(x_{\ast })+\nabla L(x_{\ast })\cdot (x-x_{\ast })$. Thus feasible stationarity plus complementary slackness is sufficient in that convex setting. Mere stationarity in a general nonconvex problem is not the theorem's global-minimum hypothesis.