KarushKuhnTacker

Karush–Kuhn–Tucker conditions, commonly abbreviated as the KKT conditions, are a set of mathematical criteria used to identify optimal solutions to constrained optimization problems. They are named after William Karush, Harold W. Kuhn, and Albert W. Tucker. The spelling “KarushKuhnTacker” reflects a common variation found in texts, with “Tacker” being a frequent misspelling of “Tucker.” The conditions are central in nonlinear programming and have broad applications in economics, engineering, and machine learning.

A typical problem form is to minimize a differentiable objective function f(x) subject to inequality constraints g_i(x) ≤ 0 for i = 1,...,m and equality constraints h_j(x) = 0 for j = 1,...,p, where x ∈ R^n. The Lagrangian is L(x, λ, μ) = f(x) + sum_i λ_i g_i(x) + sum_j μ_j h_j(x), where λ_i ≥ 0 are multipliers for the inequality constraints and μ_j are multipliers for the equality constraints.

At a local optimum x*, there exist multipliers λ ≥ 0 and μ such that:

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

- Primal feasibility: g_i(x*) ≤ 0 for all i, h_j(x*) = 0 for all j

- Dual feasibility: λ_i ≥ 0 for all i

- Complementary slackness: λ_i g_i(x*) = 0 for all i

Constraint qualifications, such as Slater’s condition, ensure the existence of these multipliers in many practical problems. When the problem is convex and qualifications hold, the KKT conditions are not only necessary but also sufficient for optimality. Extensions handle non-differentiable cases and various generalizations used in numerical optimization.