KKT

KKT, short for Karush-Kuhn-Tucker conditions, are a set of mathematical criteria that characterize optimality in a broad class of constrained optimization problems. They apply to problems of the form: minimize f(x) subject to h_i(x) = 0 for i = 1,...,m and g_j(x) ≤ 0 for j = 1,...,p, where f, h_i, and g_j are differentiable functions.

The Lagrangian L is formed as L(x, λ, μ) = f(x) + ∑ λ_i h_i(x) + ∑ μ_j g_j(x), where λ ∈ R^m and μ ∈ R^p with μ ≥ 0 for the inequality constraints. The KKT conditions require the existence of multipliers λ and μ such that:

- Stationarity: ∇x L(x, λ, μ) = 0.

- Primal feasibility: h_i(x) = 0 for all i; g_j(x) ≤ 0 for all j.

- Dual feasibility: μ_j ≥ 0 for all j.

- Complementary slackness: μ_j g_j(x) = 0 for all j.

Under mild regularity conditions, such as differentiability and Slater’s condition (there exists a feasible point with g_j(x) < 0 for all j), a feasible point x is optimal if and only if there exist multipliers λ and μ satisfying the KKT conditions. In convex problems—where f is convex, each g_j is convex, and h_i is affine—the KKT conditions are both necessary and sufficient for optimality.

In non-smooth settings, subgradients replace gradients, leading to a subgradient form of the KKT conditions. The KKT framework is foundational in nonlinear programming, duality theory, and many algorithmic approaches, and it has wide applications in economics, engineering, and machine learning, including support vector machines and robust optimization.