KKT Conditions — Mathematics Knowledge System

Overview

The Karush–Kuhn–Tucker (KKT) conditions are first-order necessary conditions for a solution to a constrained optimisation problem to be locally optimal, generalising the Lagrange multiplier conditions to inequality constraints. For convex problems satisfying a constraint qualification, the KKT conditions are also sufficient for global optimality. They are the foundation of most numerical optimisation algorithms and theoretical analyses of constrained optimisation.

Intuition

At an optimal point, the gradient of the objective must be expressible as a non-negative linear combination of the active constraint gradients. Intuitively: you cannot move in a direction that improves the objective without violating some active constraint. The KKT multipliers are the 'shadow prices' of those constraints.

Formal Definition

Definition

Consider the problem: min f₀(x) subject to fᵢ(x) ≤ 0 (i=1,…,m) and hⱼ(x) = 0 (j=1,…,p). If x* is a local minimiser and a constraint qualification holds, then there exist multipliers λᵢ* ≥ 0 and νⱼ* such that the following KKT conditions hold:

\nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(x^*) = 0

Stationarity

f_i(x^*) \le 0, \quad i = 1,\ldots,m

Primal feasibility

h_j(x^*) = 0, \quad j = 1,\ldots,p

Equality constraint feasibility

\lambda_i^* \ge 0, \quad i = 1,\ldots,m

Dual feasibility

\lambda_i^* f_i(x^*) = 0, \quad i = 1,\ldots,m

Complementary slackness

Notation

Notation	Meaning
$\lambda_i^*$	KKT multiplier for inequality constraint fᵢ ≤ 0
$\nu_j^*$	KKT multiplier for equality constraint hⱼ = 0
$\text{LICQ}$	Linear Independence Constraint Qualification — gradients of active constraints are linearly independent

Properties

Necessity (LICQ case)

\text{If } x^* \text{ is a local minimiser and LICQ holds at } x^*, \text{ then the KKT conditions hold}

Sufficiency for convex problems

\text{If } f_0, f_1,\ldots,f_m \text{ are convex and } h_j \text{ affine, then KKT conditions are sufficient for global optimality}

Shadow price interpretation

\frac{\partial p^*}{\partial b_i} = -\lambda_i^* \quad \text{(sensitivity of optimal value to constraint perturbation)}

Worked Examples

1
Rewrite constraints as f₁ = -(x+y-1) ≤ 0, f₂ = -x ≤ 0, f₃ = -y ≤ 0.
$\text{Constraints: } -(x+y-1) \le 0,\; -x \le 0,\; -y \le 0$
2
Lagrangian: L = x²+y² - λ₁(x+y-1) - λ₂x - λ₃y.
$L = x^2+y^2 - \lambda_1(x+y-1) - \lambda_2 x - \lambda_3 y$
3
Stationarity: ∂L/∂x = 2x - λ₁ - λ₂ = 0, ∂L/∂y = 2y - λ₁ - λ₃ = 0.
$2x = \lambda_1 + \lambda_2,\quad 2y = \lambda_1 + \lambda_3$
4
By symmetry try x=y=1/2: constraint x+y≥1 is active, x,y>0 so λ₂=λ₃=0.
$x^* = y^* = 1/2,\quad \lambda_1^* = 1,\quad \lambda_2^* = \lambda_3^* = 0$
5
Check CS: λ₁(x+y-1) = 1·0 = 0 ✓. All KKT conditions verified.
$p^* = (1/2)^2 + (1/2)^2 = 1/2$

✓ Answer

KKT gives x* = y* = 1/2, λ₁* = 1, optimal value 1/2.

Practice Problems

Hardproof writing

Show that for a convex program satisfying Slater's condition, the KKT conditions are necessary and sufficient for global optimality.

Common Mistakes

Common Mistake

Thinking KKT conditions are always sufficient for optimality

KKT conditions are generally only necessary. They are sufficient when the problem is convex (and the objective/constraints satisfy appropriate conditions).

Common Mistake

Forgetting the constraint qualification

KKT conditions are only guaranteed to hold at a local minimiser when a constraint qualification (e.g., LICQ, MFCQ, or Slater's) is satisfied.

Quiz

Complementary slackness λᵢ*fᵢ(x*) = 0 means:

All constraints are active at x*All multipliers are zeroEach active constraint has a positive multiplier, inactive constraints have zero multiplierThe duality gap is zero

Historical Background

William Karush derived the conditions in his 1939 master's thesis at the University of Chicago, but the work went unnoticed. Harold Kuhn and Albert Tucker independently rediscovered and published them in 1951, which is why they are often called 'KKT conditions'. The full historical record was recovered only in the 1970s.

1939
Karush derives the conditions in his MSc thesis (unpublished)
William Karush
1951
Kuhn and Tucker publish the conditions at the Second Berkeley Symposium
Harold Kuhn, Albert Tucker
1970s
Historical record corrected; Karush credited alongside Kuhn-Tucker

Summary

KKT conditions are five first-order necessary conditions for constrained optimisation: stationarity, primal feasibility, dual feasibility, complementary slackness, and a constraint qualification.
They are necessary for local optimality under a constraint qualification (e.g., LICQ or Slater).
For convex programs, KKT conditions are also sufficient for global optimality.
Multipliers λᵢ* are shadow prices: rate of change of optimal value per unit relaxation of constraint i.

References

BookBoyd, S. and Vandenberghe, L. — Convex Optimization (2004), Chapter 5. Free at https://web.stanford.edu/~boyd/cvxbook/
WebsiteWikipedia — Karush-Kuhn-Tucker conditions
WebsiteMathWorld — Kuhn-Tucker Theorem