= Convex KKT optimality certificate
{title2=$f(x_*)\leq f(z)\quad(z\text{ feasible})$}
For <differentiable functions> $f,g_i$ that are <convex functions> on an open <convex set> and <affine functions> $h_j$, the <KKT conditions> certify a <global minimum>. Once <Lagrange multipliers> satisfy them, no extra <Slater condition> is needed.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§5.5.3, printed p. 244: sufficiency under convexity and affine equalities]{ref}
The certificate is a short chain of <inequalities>. Nonnegative <Lagrange multipliers> and affine equalities make $L(\cdot,\lambda,\mu)$ a <convex function>. Its zero <gradient> gives a <global minimum> at $x_*$ by the <first-order optimality condition>. For every <feasible point> $z$,
$$
f(x_*)=L(x_*,\lambda,\mu)\leq L(z,\lambda,\mu)\leq f(z).
$$
The first equality uses feasibility and <complementary slackness>; the last inequality uses $g_i(z)\leq0$ and $\lambda_i\geq0$. Equivalently, the <Lagrange dual function> attains the same value as the primal <objective function>, proving <strong duality>. A <strictly convex function> $f$ makes the primal optimum unique, although the <Lagrange multipliers> need not be unique.
Affine equality <optimization constraints> matter: an arbitrary signed multiple of a nonlinear equality can destroy <convexity> of the <optimization Lagrangian>. For example, minimizing $(x-2)^2$ subject to the affine equality $x=b$ gives $x_*=b$ and $\mu=2(2-b)$ for $L=(x-2)^2+\mu(x-b)$. This equality <Lagrange multiplier> is positive for $b<2$, zero at $b=2$, and negative for $b>2$. <Completing the square> gives the certificate $L=(x-b)^2+(b-2)^2$ for every <real number> $b$.
Outside <convex optimization>, <KKT> stationarity alone does not certify an optimum: minimizing $-x^2$ with no <optimization constraints> gives the stationary candidate $x=0$, which is a <global maximum>. The <Lagrangian sufficiency theorem> remains applicable whenever a global minimum of the <optimization Lagrangian> can be proved directly.
Back to article page
