In mathematics, the Karush–Kuhn–Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal, provided some regularity conditions are satisfied. It is a generalization of the method of Lagrange multipliers to inequality constraints. The conditions are named for William Karush, Harold W. Kuhn, and Albert W. Tucker.
Let us consider the following nonlinear optimization problem:
where is the function to be minimized, () are the inequality constraints and () are the equality constraints, and and are the number of inequality and equality constraints, respectively.
The necessary conditions for this general equality-inequality constrained problem were first published in the Masters thesis of William Karush, although they only became renowned after a seminal conference paper by Harold W. Kuhn and Albert W. Tucker.
Suppose that the objective function, i.e., the function to be minimized, is and the constraint functions are and . Further, suppose they are continuously differentiable at a point . If is a local minimum that satisfies some regularity conditions, then there exist constants and such that
Regularity conditions (or constraint qualifications)
In order for a minimum point be KKT, it should satisfy some regularity condition, the most used ones are listed below
- Linear independence constraint qualification (LICQ): the gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at .
- Mangasarian-Fromowitz constraint qualification (MFCQ): the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at .
- Constant rank constraint qualification (CRCQ): for each subset of the gradients of the active inequality constraints and the gradients of the equality constraints the rank at a vicinity of is constant.
- Constant positive linear dependence constraint qualification (CPLD): for each subset of the gradients of the active inequality constraints and the gradients of the equality constraints, if it is positive-linear dependent at then it is positive-linear dependent at a vicinity of () is positive-linear dependent if there exists ,…, not all zero such that ).
- Quasi-normality constraint qualification (QNCQ): if the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at with associated multipliers for equalities and for inequalities than it doesn’t exist a sequence such that therefore and thus .
- Slater condition: for a convex problem, there exists a point such that and for all active in .
- Linearity constraints: If and are affine functions, then no other condition is needed to assure that the minimum point is KKT.
It can be shown that
(and the converses are not true), although MFCQ is not equivalent to CRCQ. In practice weaker constraint qualifications are preferred since they provide stronger optimality conditions.
In some cases, the necessary conditions are also sufficient for optimality. This is the case when the objective function and the inequality constraints are continuously differentiable convex functions and the equality constraints hi are affine functions. It was shown by Martin in 1985 that the broader class of functions in which KKT conditions guarantees global optimality are the so called invex functions. So if equality constraints are affine functions, inequality constraints and the objective function are continuously differentiable invex functions then KKT conditions are sufficient for global optimality.
If we reconsider the optimization problem as a maximization problem with constant inequality constraints
The value function is defined as
(So the domain of is
Given this definition, each coefficient, , is the rate at which the value function increases as increases. Thus if each is interpreted as a resource constraint, the coefficients tell you how much increasing a resource will increase the optimum value of our function . This interpretation is especially important in economics and is used, for instance, in utility maximization problems.