Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 3 / 21H / a / Solution

For a minimization problem over a domain $D$ with inequality constraints $g_j(x)\le 0$ and equality constraints $h_{\ell }(x)=0$, letThe Lagrangian sufficiency theorem states: if $x_{\ast }$ is feasible, ${\lambda }_j\ge 0$, ${\lambda }_j{g}_j(x_{\ast })=0$, and $x_{\ast }$ globally minimizes $\mathcal{L}(\cdot ,\lambda ,\mu )$ on $D$, then $x_{\ast }$ globally minimizes the constrained objective. Equality multipliers have no sign restriction.

For any feasible $x$, the sign of the inequality multipliers gives $\mathcal{L}(x,\lambda ,\mu )\le f(x)$. Feasibility and complementary slackness give $\mathcal{L}(x_{\ast },\lambda ,\mu )=f(x_{\ast })$. ThereforeThis proves the theorem. No convexity is necessary if the global minimization of the Lagrangian is already known. In a differentiable convex optimization problem with convex inequalities and affine equalities, a stationary point of this convex Lagrangian is automatically a global minimizer, which gives the familiar sufficiency of the Karush-Kuhn-Tucker conditions.