Misplaced Pages

Revision as of 03:10, 27 August 2007

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. It is a generalization of the method of Lagrange multipliers.

Let us consider the following nonlinear optimization problem:

${\displaystyle \min \limits _{x}\;\;f(x)}$

${\displaystyle {\mbox{subject to: }}\ }$

${\displaystyle g_{i}(x)\leq 0,h_{j}(x)=0}$

where ${\displaystyle f(x)}$ is the function to be minimized, ${\displaystyle g_{i}(x)\ (i=1,\ldots ,m)}$ are the nonequality constraints and ${\displaystyle h_{j}(x)\ (j=1,\ldots ,l)}$ are the equality constraints, and ${\displaystyle m}$ and ${\displaystyle l}$ are the number of nonequality and equality constraints, respectively.

The necessary conditions for inequality constrained problem were first published in the Masters thesis of William Karush, although they became renowned after a seminal conference paper by Harold W. Kuhn and Albert W. Tucker.

Necessary conditions

Suppose that the objective function, i.e., the function to be minimized, is ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ and the constraint functions are ${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ and ${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$. Further, suppose they are continuously differentiable at a point ${\displaystyle x^{*}}$. If ${\displaystyle x^{*}}$ is a local minimum, then there exist constants ${\displaystyle \lambda \geq 0}$, ${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$ and ${\displaystyle \nu _{j}\ (j=1,...,l)}$ such that

${\displaystyle \lambda +\sum _{i=1}^{m}\mu _{i}+\sum _{j=1}^{l}|\nu _{j}|>0,}$

${\displaystyle \lambda \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}(x^{*})=0,}$

${\displaystyle \mu _{i}g_{i}(x^{*})=0\;{\mbox{for all}}\;i=1,\ldots ,m.}$

Regularity conditions (or constraint qualifications)

In the necessary condition above, the dual multiplier ${\displaystyle \lambda }$ may be zero. Such cases are referred to as degenerate or abnormal. The necessary condition then does not take into account the properties of the function, but only the geometry of constraints.

A number of regularity conditions exist which ensure that the solution is non-degenerate (i.e. ${\displaystyle \lambda \neq 0}$). These include:

• Linear independence constraint qualification (LICQ): the gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at ${\displaystyle x^{*}}$.
• Mangasarian-Fromowitz constraint qualification (MFCQ): the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at ${\displaystyle x^{*}}$.
• 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 ${\displaystyle x^{*}}$ 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 ${\displaystyle x^{*}}$ then it is positive-linear dependent at a vicinity of ${\displaystyle x^{*}}$. (${\displaystyle \{v_{1},\ldots ,v_{n}\}}$ is positive-linear dependent if there exists ${\displaystyle a_{1}\geq 0,\ldots ,a_{n}\geq 0}$ not all zero such that ${\displaystyle a_{1}v_{1}+\ldots +a_{n}v_{n}=0}$)
• Slater condition: for a problem with inequality constraints only, there exists a point ${\displaystyle x}$ such that ${\displaystyle g_{i}(x)<0}$ for all ${\displaystyle i=1,\ldots ,m}$

It can be shown that LICQ=>MFCQ=>CPLD, LICQ=>CRCQ=>CPLD, although MFCQ is not equivalent to CRCQ. In practice weaker constraint qualifications are preferred since they provide stronger optimality conditions.

Sufficient conditions

Let the objective function ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ and the constraint functions ${\displaystyle g_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ be convex functions and ${\displaystyle h_{j}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ be affine functions, and let there be a feasible point ${\displaystyle x^{*}}$. If there exist constants ${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$ and ${\displaystyle \nu _{j}\ (j=1,\ldots ,l)}$ such that

${\displaystyle \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}(x^{*})=0}$

${\displaystyle \mu _{i}g_{i}(x^{*})=0\;{\mbox{for all}}\;i=1,\ldots ,m,}$

then the point ${\displaystyle x^{*}}$ is a global minimum.

Value function

If we reconsider the optimization problem as a maximization problem with constant inequality constraints,

${\displaystyle \max \limits _{x}\;\;f(x)}$

${\displaystyle {\mbox{subject to: }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0}$

The value function is defined as:

${\displaystyle V(a_{1},\ldots a_{n})=\sup \limits _{x}\;\;f(x)}$

${\displaystyle {\mbox{subject to: }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0}$

${\displaystyle j\in \{1,\ldots l\},i\in {1,\ldots ,m}}$

(So the domain of V is ${\displaystyle \{a\in \mathbb {R} ^{m}|{\mbox{for some }}x\in Xg_{i}(x)\leq a_{i},i\in \{1,\ldots ,m\}}$)

Given this definition, each coefficient, ${\displaystyle \lambda _{i}}$, is the rate at which the value function increases as ${\displaystyle a_{i}}$ increases. Thus if each ${\displaystyle a_{i}}$ 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.

References

1. 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. {{cite journal}}: Cite journal requires |journal= (help). Available from http://wwwlib.umi.com/dxweb/details?doc_no=7371591 (for a fee)
2. Kuhn, H. W. (1951). "Nonlinear programming". Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press. pp. 481–492. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

Further reading

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, pp. 473-485 (2005).
• Jalaluddin Abdullah, Optimization by the Fixed-Point Method, Version 1.97, Vuze/Azureus (under Science and Technology), 2007. (note 1. you need a bittorrent client, preferably Azureus, to download the book 2. the book is free)

• Optimization