= Solution
For a minimization problem on a domain $D$, write the equality constraints as $h(x)=0$ and the inequality constraints as $g(x)\leq0$. Define the <optimization Lagrangian>
$$
L(x,\lambda,\mu)=f(x)+\lambda^T h(x)+\mu^Tg(x),\qquad \mu\geq0.
$$
The <Lagrangian sufficiency theorem> states that a feasible $x^*$ is globally optimal if it globally minimizes $L(\cdot,\lambda^*,\mu^*)$ on $D$ for some multipliers with $\mu^*\geq0$ and satisfies <complementary slackness>, $\mu_j^*g_j(x^*)=0$ for every $j$. Equality multipliers have unrestricted signs.
For any feasible $x$, the multiplier sign gives $L(x,\lambda^*,\mu^*)\leq f(x)$. Feasibility and <complementary slackness> at $x^*$ give $L(x^*,\lambda^*,\mu^*)=f(x^*)$. Hence
$$
\boxed{f(x)\geq L(x,\lambda^*,\mu^*)\geq L(x^*,\lambda^*,\mu^*)=f(x^*).}
$$
This proves sufficiency. \b[Global Lagrangian minimization, rather than stationarity alone, is the certificate.] No <convexity> or constraint qualification is needed for this implication; <convexity> is one way to verify the required global minimum.
Back to article page
