# What are the KKT conditions?

Consider an optimization problem in standard form:

\begin{aligned} \text{minimize} \quad& f_0(x) \\ \text{subject to} \quad& f_i(x) \leq 0, \quad i = 1, \dots, m, \\ & h_i(x) = 0, \quad i = 1, \dots, p, \end{aligned}

with the variable $x \in \mathbb{R}^n$. Assume that the $f_i$‘s and $h_i$‘s are differentiable. (At this point, we are not assuming anything about their convexity.)

As before, define the Lagrangian as the function

\begin{aligned} L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x). \end{aligned}

Let $x^\star$ and $(\lambda^\star, \nu^\star)$ be the primal and dual optimal points respectively (i.e. points where the primal and dual problems are optimized). The Karush-Kuhn-Tucker (KKT) conditions refer to the following set of 4 assumptions:

1. Primal feasibility: $f_i(x^\star) \leq 0$ for $i = 1, \dots, m$, and $h_i(x^\star) = 0$ for $i = 1, \dots, p$.
2. Dual feasibility: $\lambda_i^\star \geq 0$ for $i = 1, \dots, m$.
3. Stationarity: $\partial_x L(x^\star, \lambda^\star, \nu^\star) = 0$, i.e. $\nabla f_0(x^\star) + \displaystyle\sum_{i=1}^m \lambda_i^\star \nabla f_i(x^\star) + \displaystyle\sum_{i=1}^p \nu_i^\star \nabla h_i(x^\star) = 0$.
4. Complementary slackness: $\lambda_i^\star f_i(x^\star) = 0$ for $i = 1, \dots, m$.

Here are 3 statements (theorems, if you will) involving the KKT conditions which highlight their importance:

1. (Necessity) For any optimization problem for which strong duality holds, any pair of primal and dual optimal points must satisfy the KKT conditions.
2. (Sufficiency) For a convex optimization problem (i.e. $f_i$‘s convex and $h_i$‘s affine), if the KKT conditions hold for some $(\tilde{x}, \tilde{\lambda}, \tilde{\nu})$, then $\tilde{x}$ and $(\tilde{\lambda}, \tilde{\nu})$ are primal and dual optimal, and there is zero duality gap.
3. (Necessity & sufficiency) For a convex optimization problem that satisfies Slater’s condition, then $\tilde{x}$ is primal optimal if and only if there exists $(\tilde{\lambda}, \tilde{\nu})$ such that the KKT conditions are satisfied.

Note: There are more general versions of the KKT conditions; see Reference 2 for details.

References:

1. Boyd, S., and Vandenberghe, L. (2004). Convex Optimization. Chapter 5.
2. Wikipedia. Karush-Kuhn-Tucker conditions.