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:

Primal feasibility: $f_i(x^\star) \leq 0$ for $i = 1, \dots, m$ , and $h_i(x^\star) = 0$ for $i = 1, \dots, p$ .
Dual feasibility: $\lambda_i^\star \geq 0$ for $i = 1, \dots, m$ .
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$ .
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:

(Necessity) For any optimization problem for which strong duality holds, any pair of primal and dual optimal points must satisfy the KKT conditions.
(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.
(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:

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

Statistical Odds & Ends

What are the KKT conditions?

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply