Karush–Kuhn–Tucker conditions

From Wikipedia, the free encyclopedia

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.

Let us consider the following nonlinear optimization problem:

\min\limits_{x}\;\; f(x)
\mbox{subject to: }\
g_i(x) \le 0 , h_j(x) = 0

where f(x) is the function to be minimized, g_i (x)\ (i = 1, \ldots,m) are the inequality constraints and h_j (x)\ (j = 1,\ldots,l) are the equality constraints, and m and l 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[1], although they only became renowned after a seminal conference paper by Harold W. Kuhn and Albert W. Tucker.[2]

Contents

[edit] Necessary conditions

Suppose that the objective function, i.e., the function to be minimized, is f : \mathbb{R}^n \rightarrow \mathbb{R} and the constraint functions are g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R} and h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R}. Further, suppose they are continuously differentiable at a point x * . If x * is a local minimum that satisfies some regularity conditions, then there exist constants \mu_i\ (i = 1,\ldots,m) and \nu_j\ (j = 1,...,l) such that [3]

Stationarity
\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0,
Primal feasibility
g_i(x^*) \le 0, \mbox{ for all } i = 1, \ldots, m
h_j(x^*) = 0, \mbox{ for all } j = 1, \ldots, l \,\!
Dual feasibility
\mu_i \ge 0\ (i = 1,\ldots,m)
Complementary slackness
\mu_i g_i (x^*) = 0\; \mbox{for all}\; i = 1,\ldots,m.

[edit] Regularity conditions (or constraint qualifications)

In order to a minimum point x * 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 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 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 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 x * then it is positive-linear dependent at a vicinity of x * . (v_1,\ldots,v_n is positive-linear dependent if there exists a_1\geq 0,\ldots,a_n\geq 0 not all zero such that a_1v_1+\ldots+a_nv_n=0)
  • Slater condition: for a problem with inequality constraints, g_i(x) \leq 0 only, there exists a point x such that gi(x) < 0 for all i. That is, there exists at least one strictly feasible point.

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.

[edit] Sufficient conditions

The most common sufficient conditions are stated as follows. Let the objective function f: \mathbb{R}^n \rightarrow \mathbb{R} be convex, the constraint functions g_i : \mathbb{R}^n \rightarrow \mathbb{R} be convex functions and h_j : \mathbb{R}^n \rightarrow \mathbb{R} be affine functions, and let x * be a point in \mathbb{R}^n. If there exist constants \mu_i\ (i = 1,\ldots,m) and \nu_j\ (j = 1,\ldots,l) such that

Stationarity
\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0
Primal feasibility
g_i(x^*) \le 0 \mbox{ for all } i = 1,\ldots, m
h_j(x^*) = 0 \mbox{ for all } j = 1,\ldots, l \,\!
Dual feasibility
\mu_i \ge 0\ (i = 1,\ldots,m)
Complementary slackness
\mu_i g_i (x^*) = 0\; \mbox{for all}\; i = 1,\ldots,m,

then the point x * is a global minimum.

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 invex functions then KKT conditions are necessary and sufficient for global optimality.

[edit] Value function

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

\max\limits_{x}\;\; f(x)
\mbox{subject to: }\
g_i(x) \le a_i , h_j(x) = 0

The value function is defined as:

V(a_1, \ldots a_n) = \sup\limits_{x}\;\; f(x)
\mbox{subject to: }\
g_i(x) \le a_i , h_j(x) = 0
j\in\{1,\ldots l\}, i\in{1,\ldots,m}

(So the domain of V is \{a \in \mathbb{R}^m | \mbox{for some }x\in X g_i(x) \leq a_i, i \in \{1,\ldots,m\})

Given this definition, each coefficient, λi, is the rate at which the value function increases as ai increases. Thus if each ai 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.

[edit] 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. Available from http://wwwlib.umi.com/dxweb/details?doc_no=7371591 (for a fee)
  2. ^ Kuhn, H. W.; Tucker, A. W. (1951). "Nonlinear programming". Proceedings of 2nd Berkeley Symposium: 481-492, Berkeley: University of California Press. 
  3. ^ The Karush-Kuhn-Tucker Theorem. Retrieved on 2008-03-11.

[edit] Further reading

  • J. Nocedal, S. J. Wright, Numerical Optimization. Springer Publishing. ISBN 978-0-387-30303-1.
  • 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. [1].
  • Martin, D.H, The essence of invexity, J. Optim. Theory Appl. 47, (1985) 65-76.