sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that:

"The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are continuously differentiable convex functions and the equality constraints h_i are affine functions." link

Could someone please show me how this result is derived? That is, given a convex objective function, convex inequality constraints and affine equality constraints, how can we show that any point in the feasible set that satisfies the KKT conditions must be a minimizer of the function over the feasible set?

Solution 1:

The primal problem is \begin{align} \operatorname{minimize}_x & \quad f_0(x) \\ \text{subject to} & \quad f_i(x) \leq 0 \quad \text{for } i = 1,\ldots, m\\ & \quad Ax = b. \end{align} The functions $f_i, i = 0,\ldots,m$ are differentiable and convex.

Assume $x^*$ is feasible for the primal problem (so $f_i(x^*) \leq 0$ for $i = 1,\ldots,m$ and $A x^* = b$) and that there exist vectors $\lambda \geq 0$ and $\eta$ such that $$ \tag{$\spadesuit$}\nabla f_0(x^*) + \sum_{i=1}^m \lambda_i \nabla f_i(x^*) + A^T \eta = 0 $$ and $$ \lambda_i f_i(x_i) = 0 \quad \text{for } i = 1,\ldots,m. $$ Because the functions $f_i$ are convex, equation ($\spadesuit$) implies that $x^*$ is a minimizer (with respect to $x$) of the Lagrangian $$ L(x,\lambda,\eta) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \eta^T(Ax - b). $$ Thus, if $x$ is feasible for the primal problem, then \begin{align*} f_0(x) & \geq f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \eta^T(Ax - b) \\ & \geq f_0(x^*) + \sum_{i=1}^m \lambda_i f_i(x^*) + \eta^T(Ax^* - b) \\ & = f_0(x^*). \end{align*} This shows that $x^*$ is a minimizer for the primal problem.

Solution 2:

I believe the result you're looking for is in Boyd and Vandenberghe's book "Convex Optimization", which can be downloaded for free on the linked website. Anyway, on page 244 they state when the KKT conditions are both necessary and sufficient for convex optimization problems and give a short proof.