The Karush–Kuhn–Tucker (KKT) conditions are a set of necessary conditions for a solution to be optimal for a constrained optimization problem. They are widely used in mathematical optimization, particularly in nonlinear programming. The KKT conditions generalize the method of Lagrange multipliers to handle problems with inequality constraints.
Articles by others on the same topic
The Karush-Kuhn-Tucker conditions combine membership of the feasible set with a balance of gradients and complementary slackness. For a minimization problem with differentiable functions on an open subset of , writeand use the optimization LagrangianA candidate satisfies the KKT conditions exactly when all four requirements hold:
- Primal feasibility: and , so is a feasible point.
- Dual sign feasibility: . The equality Lagrange multipliers are unrestricted real numbers.
- Stationarity: the gradient of the optimization Lagrangian in the decision variables vanishes,
- Complementary slackness: for every inequality optimization constraint.[ref]Lecture 7: Lagrange Multipliers and KKT Conditions. Lecture 7, §L7.1.1, Definition L7.1, printed p. 3: the four KKT requirements
The sign of each inequality Lagrange multiplier follows the chosen convention : on the feasible set, makes the optimization Lagrangian a lower bound on the objective function. An equality contributes zero on the feasible set for either sign of its Lagrange multiplier. Complementary slackness says an inequality with must have , while implies an active constraint. An active constraint can still have zero Lagrange multiplier; the quadratic minimization with a moving upper bound below gives an explicit example.
The name records William Karush's 1939 master's thesis and the 1951 work of Harold W. Kuhn and Albert W. Tucker.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. Chapter 5 bibliography, printed p. 272, and bibliography entries KT51 and Kuh76