Consider an optimization problem in standard form:

with the variable . Assume that the ‘s and ‘s are differentiable. (At this point, we are not assuming anything about their convexity.)

As before, define the Lagrangian as the function

Let and 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:* for , and for .
*Dual feasibility:* for .
*Stationarity:* , i.e. .
*Complementary slackness:* for .

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. ‘s convex and ‘s affine), if the KKT conditions hold for some , then and are primal and dual optimal, and there is zero duality gap.
*(Necessity & sufficiency)* For a convex optimization problem that satisfies Slater’s condition, then is primal optimal if and only if there exists 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.

### Like this:

Like Loading...

*Related*