In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first-order necessary conditions for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. The system of equations and inequalities corresponding to the KKT conditions is usually not solved directly, except in the few special cases where a closed-form solution can be derived analytically. In general, many optimization algorithms can be interpreted as methods for numerically solving the KKT system of equations and inequalities.
The KKT conditions were originally named after Harold W. Kuhn, and Albert W. Tucker, who first published the conditions in 1951. Later scholars discovered that the necessary conditions for this problem had been stated by William Karush in his master's thesis in 1939.
Nonlinear optimization problemEdit
Consider the following nonlinear minimization or maximization problem:
- subject to
where is the optimization variable, is the objective or utility function, are the inequality constraint functions, and are the equality constraint functions. The numbers of inequality and equality constraints are denoted m and ℓ, respectively.
Suppose that the objective function and the constraint functions and are continuously differentiable at a point . If is a local optimum and the optimization problem satisfies some regularity conditions (see below), then there exist constants and , called KKT multipliers, such that
- For maximizing f(x):
- For minimizing f(x):
- Primal feasibility
- Dual feasibility
- Complementary slackness
In the particular case , i.e., when there are no inequality constraints, the KKT conditions turn into the Lagrange conditions, and the KKT multipliers are called Lagrange multipliers.
Regularity conditions (or constraint qualifications)Edit
In order for a minimum point to satisfy the above KKT conditions, the problem should satisfy some regularity conditions; some common examples are tabulated here:
|Linearity constraint qualification||LCQ||If and are affine functions, then no other condition is needed.|
|Linear independence constraint qualification||LICQ||The gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at .|
|Mangasarian-Fromovitz constraint qualification||MFCQ||The gradients of the equality constraints are linearly independent at and there exists a vector such that for all active inequality constraints and for all equality constraints.|
|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 in the vicinity of .|
|Quasi-normality constraint qualification||QNCQ||If the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly dependent at with associated multipliers for equalities and for inequalities, then there is no sequence such that and .|
|Slater condition||SC||For a convex problem (i.e., assuming minimization, are convex and is affine), there exists a point such that and . x should be from relative interior of domain of optimization problem (intersection of function domains). Slater's condition implies that the duality gap is zero.|
( ) is positive-linear dependent if there exists and an element such that .
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. In general, the necessary conditions are not sufficient for optimality and additional information is necessary, such as the Second Order Sufficient Conditions (SOSC). For smooth functions, SOSC involve the second derivatives, which explains its name.
The necessary conditions are sufficient for optimality if the objective function of a maximization problem is a concave function, the inequality constraints are continuously differentiable convex functions and the equality constraints are affine functions.
Second-order sufficient conditionsEdit
For smooth, non-linear optimization problems, a second order sufficient condition is given as follows. Consider that find a local minimum using the Karush–Kuhn–Tucker conditions above. With such that strict complementarity is held at (i.e. all ), then for all such that
(where the bracketed expression is a row vector), the following equation must hold;
If the above condition is strictly met, the function is a strict constrained local minimum.[clarification needed]
Often in mathematical economics the KKT approach is used in theoretical models in order to obtain qualitative results. For example, consider a firm that maximizes its sales revenue subject to a minimum profit constraint. Letting Q be the quantity of output produced (to be chosen), R(Q) be sales revenue with a positive first derivative and with a zero value at zero output, C(Q) be production costs with a positive first derivative and with a non-negative value at zero output, and be the positive minimal acceptable level of profit, then the problem is a meaningful one if the revenue function levels off so it eventually is less steep than the cost function. The problem expressed in the previously given minimization form is
- subject to
and the KKT conditions are
Since Q = 0 would violate the minimum profit constraint, we have Q > 0 and hence the third condition implies that the first condition holds with equality. Solving that equality gives
Because it was given that and are strictly positive, this inequality along with the non-negativity condition on guarantees that is positive and so the revenue-maximizing firm operates at a level of output at which marginal revenue is less than marginal cost — a result that is of interest because it contrasts with the behavior of a profit maximizing firm, which operates at a level at which they are equal.
If we reconsider the optimization problem as a maximization problem with constant inequality constraints,v.
The value function is defined as
(So the domain of V 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 f. This interpretation is especially important in economics and is used, for instance, in utility maximization problems.
With an extra constant multiplier , which may be zero, in front of the KKT stationarity conditions turn into
which are called the Fritz John conditions.
The KKT conditions belong to a wider class of the first-order necessary conditions (FONC), which allow for non-smooth functions using subderivatives.
- Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge: Cambridge University Press. p. 244. ISBN 0-521-83378-7. MR 2061575.
- Kuhn, H. W.; Tucker, A. W. (1951). "Nonlinear programming". Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press. pp. 481–492. MR 0047303.
- W. Karush (1939). "Minima of Functions of Several Variables with Inequalities as Side Constraints". M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois.
- Kjeldsen, Tinne Hoff (2000). "A contextualized historical analysis of the Kuhn-Tucker theorem in nonlinear programming: the impact of World War II". Historia Math. 27 (4): 331–361. doi:10.1006/hmat.2000.2289. MR 1800317.
- Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. ISBN 978-0691119151. MR 2199043.
- Dimitri Bertsekas (1999). Nonlinear Programming (2 ed.). Athena Scientific. pp. 329–330. ISBN 9781886529007.
- Chandler Davis (1954). "Theory of Positive Linear Dependence". American Journal of Mathematics. 76 (4): 733–746. doi:10.2307/2372648.
- Rodrigo Eustaquio; Elizabeth Karas; Ademir Ribeiro. Constraint Qualification for Nonlinear Programming (PDF) (Technical report). Federal University of Parana.
- Martin, D. H. (1985). "The Essence of Invexity". J. Optim. Theory Appl. 47 (1): 65–76. doi:10.1007/BF00941316.
- Hanson, M. A. (1999). "Invexity and the Kuhn-Tucker Theorem". J. Math. Anal. Appl. 236 (2): 594–604. doi:10.1006/jmaa.1999.6484.
- Chiang, Alpha C. Fundamental Methods of Mathematical Economics, 3rd edition, 1984, pp. 750–752.
- Andreani, R.; Martínez, J. M.; Schuverdt, M. L. (2005). "On the relation between constant positive linear dependence condition and quasinormality constraint qualification". Journal of Optimization Theory and Applications. 125 (2): 473–485. doi:10.1007/s10957-004-1861-9.
- Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover. ISBN 0-486-43227-0.
- Boyd, S.; Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. ISBN 0-521-83378-7.
- Nocedal, J.; Wright, S. J. (2006). Numerical Optimization. New York: Springer. ISBN 978-0-387-30303-1.
- Sundaram, Rangarajan K. (1996). "Inequality Constraints and the Theorem of Kuhn and Tucker". A First Course in Optimization Theory. New York: Cambridge University Press. pp. 145–171. ISBN 0-521-49770-1.