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
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.