Karush-Kuhn-Tucker (KKT) conditions

If strong duality (with zero duality gap) holds and $x,\lambda,\nu$ - possibly more than one pair - are optimal (see previous post), and the problem has differentiable $f_i, h_i$, it must satisfy the KKT conditions: [necessary condition]

1. primal constraints: $f_i(x)\leq 0, i=1,\cdots,m, \; h_i(x) = 0, i=1,\cdots,p$
2. dual constraints: $\lambda\succeq 0$
3. complementary slackness: $\lambda_i f_i(x) = 0, i=1,\cdots,m$
4. gradient of Lagrangian with respect to $x$ vanishes:
   $$\nabla f_0(x) + \sum_{i=1}^m \lambda_i \nabla f_i(x) + \sum_{i=1}^p \nu_i\nabla h_i(x) = 0$$

For convex problems

Key: When the primal problem is convex, the KKT conditions are also sufficient for points to be primal and dual optimal.

If $\tilde{x},\tilde{\lambda},\tilde{\nu}$ satisfy KKT for a convex problem (i.e. $f_i$ convex, $h_i$ affine).  Then they are optimal, with zero duality gap:

• from complementary slackness: $f_0(\tilde{x})=L(\tilde{x},\tilde{\lambda},\tilde{\nu})$
• from 4th condition (and convexity): $g(\tilde{x},\tilde{\lambda},\tilde{\nu}) =L(\tilde{x},\tilde{\lambda},\tilde{\nu})$

hence, $f_0(\tilde{x}) = g(\tilde{x},\tilde{\lambda},\tilde{\nu})$

If Slater's condition is satisfied:

$x$ is optimal iff there exist $\lambda,\nu$ that satisfy KKT conditions

• Slater implies strong duality, therefore dual optimum is attained
• generalizes optimality condition $\nabla f_0(x) = 0$ for unconstrained problem

Key: Many algorithms for convex optimization are conceived as methods for solving the KKT conditions.