= Solution
For a <maximization problem> with $g_i(u)\leq0$ and $h_j(u)=0$, use the <optimization Lagrangian>
$$
L(u,\lambda,\mu)=f(u)-\sum_i\lambda_i g_i(u)-\sum_j\mu_jh_j(u),\qquad \lambda_i\geq0.
$$
The <Lagrangian sufficiency theorem> says: if $u^*$ is feasible, $u^*$ globally maximizes $L(\cdot,\lambda^*,\mu^*)$ over its original domain, and <complementary slackness> holds, $\lambda_i^*g_i(u^*)=0$, then $u^*$ globally maximizes $f$ over the feasible set. Equality <Lagrange multipliers> have no sign restriction. For every feasible $u$,
$$
f(u)\leq L(u,\lambda^*,\mu^*)\leq L(u^*,\lambda^*,\mu^*)=f(u^*),
$$
which proves the theorem.
For a <minimization problem>, reverse the signs in the <optimization Lagrangian>: take $L=f+\sum_i\lambda_i g_i+\sum_j\mu_jh_j$, with $\lambda_i\geq0$. If a feasible $u^*$ globally minimizes this <optimization Lagrangian> and satisfies <complementary slackness>, then
$$
f(u)\geq L(u,\lambda^*,\mu^*)\geq L(u^*,\lambda^*,\mu^*)=f(u^*).
$$
\b[The hypothesis is a global extremum of the Lagrangian.] Merely solving its stationarity equations is insufficient; no convexity assumption is needed when the global extremum itself has been proved.
Back to article page
