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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s