Namespaces
Variants
Actions

Difference between revisions of "Karush-Kuhn-Tucker conditions"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(MSC 49Kxx suits better)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{TEX|done}}{{MSC|49Kxx}}
 +
 
''KKT conditions, Karush–Kuhn–Tucker optimality conditions, KKT optimality conditions, Kuhn–Tucker conditions''
 
''KKT conditions, Karush–Kuhn–Tucker optimality conditions, KKT optimality conditions, Kuhn–Tucker conditions''
  
Consider the general mathematical programming problem (see also [[Mathematical programming|Mathematical programming]]):
+
Consider the general [[mathematical programming]] problem:
 
+
\begin{equation}
minimize <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100501.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100502.png" />,
+
\begin{array}{lll}
 
+
\mbox{minimize}  & f(x), & x\in\mathbb{R}^n \\
subject to
+
\mbox{subject to} & g_i(x)\leq 0, & i=1,\ldots,p,\\
 
+
& h_j(x)=0, & j=1,\ldots,q,
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100503.png" /></td> </tr></table>
+
\end{array}
 
+
\end{equation}
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100504.png" /></td> </tr></table>
+
with $f$, $g_i$, $h_j$ all [[Continuous function|continuously]] [[Differentiable function|differentiable]] ($C^1$-functions), and form the [[Lagrangian]] function
 
+
\begin{equation}
with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100505.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100506.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100507.png" /> all continuously differentiable, and form the Lagrangian function
+
L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{p}\lambda_i g_i(x) + \sum_{j=1}^{q}\mu_j h_j(x).
 
+
\end{equation}
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100508.png" /></td> </tr></table>
 
 
 
 
The Karush–Kuhn–Tucker optimality conditions now are:
 
The Karush–Kuhn–Tucker optimality conditions now are:
 +
\begin{equation} \label{eq:1}
 +
\begin{array}{rl}
 +
\dfrac{\partial}{\partial x_k}L(x,\lambda,\mu)=0, & k=1,\ldots,n,\\
 +
\lambda_i\geq 0, & i=1,\ldots,p,\\
 +
\lambda_i g_i(x)=0, & i=1,\ldots,p,\\
 +
g_i(x)\leq 0, & i=1,\ldots,p,\\
 +
h_j(x)=0, & j=1,\ldots,q.
 +
\end{array}
 +
\end{equation}
 +
Note that the two last conditions just say that $x$ is feasible and that the third conditions could be replaced by $\sum\lambda_i g_i(x)=0$ (given the second and fourth). Under suitable constraint qualifications, the KKT optimality conditions are necessary conditions for a local solution $x^*$ of the general mathematical programming problem, in the following sense.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k1100509.png" /></td> </tr></table>
+
If $x^*$ is a local minimum, then there are corresponding $\lambda^*$, $\mu^*$ such that the triple $(x^*,\lambda^*,\mu^*)$ satisfies the KKT optimality conditions. A triple satisfying the KKT optimality conditions is sometimes called a KKT-triple.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005010.png" /></td> </tr></table>
+
This generalizes the familiar [[Lagrange multipliers]] rule to the case where there are also inequality constraints.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005011.png" /></td> </tr></table>
+
The result was obtained independently by Karush in 1939, by F. John in 1948, and by H.W. Kuhn and J.W. Tucker in 1951, see [[#References|[1]]], [[#References|[7]]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005012.png" /></td> </tr></table>
+
One suitable constraint qualification (for the case where there are no equality constraints) is $\overline{D}(x^*)=D(x^*)$, where $\overline{D}(x^*)$ is the closure of \begin{equation} D(x^*)=\left\{d\colon\exists\sigma > 0\colon\sigma\geq\tau\geq 0 \Rightarrow x^*+\tau d \quad\text{feasible}\right\} \end{equation} and \begin{equation} D(x^*)=\left\{d\colon\nabla g_i(x^*)^T d\geq 0,\quad i=1,\ldots,p\right\}, \end{equation} where $\nabla g_i(x^*)$ is the [[gradient]] vector of $g_i$ at $x^*$, \begin{equation} \nabla g_i(x^*)^T=\left(\dfrac{\partial g_i}{\partial x_1}(x^*),\ldots,\dfrac{\partial g_i}{\partial x_n}(x^*)\right), \end{equation} see [[#References|[2]]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005013.png" /></td> </tr></table>
+
Given a KKT-triple $(x^*,\lambda^*,\mu^*)$, there are also (as in the case of Lagrange multipliers) second-order sufficient conditions that ensure local optimality of $x^*$.
  
Note that the two last conditions just say that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005014.png" /> is feasible and that the third conditions could be replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005015.png" /> (given the second and fourth). Under suitable constraint qualifications, the KKT optimality conditions are necessary conditions for a local solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005016.png" /> of the general mathematical programming problem, in the following sense.
 
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005017.png" /> is a local minimum, then there are corresponding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005019.png" /> such that the triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005020.png" /> satisfies the KKT optimality conditions. A triple satisfying the KKT optimality conditions is sometimes called a KKT-triple.
 
  
This generalizes the familiar Lagrange multipliers rule (see [[Lagrange multipliers|Lagrange multipliers]]) to the case where there are also inequality constraints.
+
====Comment====
  
The result was obtained independently by Karush in 1939, by F. John in 1948, and by H.W. Kuhn and J.W. Tucker in 1951, see [[#References|[a1]]].
+
The KKT conditions \eqref{eq:1} provide a criterion for testing whether a solution which has been found by other methods is in fact an optimal solution.
  
One suitable constraint qualification (for the case where there are no equality constraints) is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005022.png" /> is the closure of
+
The KKT conditions have been generalized in various directions:
 +
* to necessary or sufficient conditions, or both types, for an extremum of a function subject to equality or inequality constraints [[#References|[6]]]; especially in case of [[Convex function (of a real variable)|convex functions]] $f$ and $g_i$ and affine $h_j$, the KKT conditions \eqref{eq:1} are sufficient, see [[#References|[9]]], pp. 243–246.
 +
* to changing the geometrical structure of the underlying manifold [[#References|[6]]], [[#References|[8]]].
 +
* [[Fritz John condition]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005023.png" /></td> </tr></table>
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005024.png" /></td> </tr></table>
 
  
and
+
====References====
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005025.png" /></td> </tr></table>
 
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005026.png" /> is the gradient vector of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005027.png" /> at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005028.png" />,
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005029.png" /></td> </tr></table>
+
<table>
 
+
<TR><TD valign="top">[1]</TD> <TD valign="top">  A.V. Fiacco,  G.P. McCormick,  "Nonlinear programming, sequential unconstrained minimization techniques" , SIAM  (1968)  (Edition: Reprinted)</TD></TR>
[[#References|[a2]]].
+
<TR><TD valign="top">[2]</TD> <TD valign="top">  W.I. Zangwill,  "Nonlinear programming" , Prentice-Hall  (1969)</TD></TR>
 
+
<TR><TD valign="top">[3]</TD> <TD valign="top">  O.L. Mangasarian,  "Nonlinear programming" , McGraw-Hill  (1969)</TD></TR>
Given a KKT-triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005030.png" />, there are also (as in the case of Lagrange multipliers) second-order sufficient conditions that ensure local optimality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110050/k11005031.png" />.
+
<TR><TD valign="top">[4]</TD> <TD valign="top">  G.P. McCormick,  "Nonlinear programming: theory, algorithms, and applications" , Wiley  (1983)</TD></TR>
 
+
<TR><TD valign="top">[5]</TD> <TD valign="top">  Jong-Shi Pang,  "Complementarity problems"  R. Horst (ed.)  P.M. Pardalos (ed.) , ''Handbook of Global Optimization'' , Kluwer Acad. Publ.  (1995)  pp. 271–338</TD></TR>
====References====
+
<TR><TD valign="top">[6]</TD> <TD valign="top">  K.J. Arrow,  L. Hurwicz,  H. Uzawa,  "Studies in linear and nonlinear programming" , Stanford Univ. Press  (1958)</TD></TR>
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.V. Fiacco,  G.P. McCormick,  "Nonlinear programming, sequential unconstrained minimization techniques" , SIAM  (1968)  (Edition: Reprinted)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.I. Zangwill,  "Nonlinear programming" , Prentice-Hall  (1969)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  O.L. Mangasarian,  "Nonlinear programming" , McGraw-Hill  (1969)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  G.P. McCormick,  "Nonlinear programming: theory, algorithms, and applications" , Wiley  (1983)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  Jong-Shi Pang,  "Complementarity problems"  R. Horst (ed.)  P.M. Pardalos (ed.) , ''Handbook of Global Optimization'' , Kluwer Acad. Publ.  (1995)  pp. 271–338</TD></TR></table>
+
<TR><TD valign="top">[7]</TD> <TD valign="top">  H.W. Kuhn,  A.W. Tucker,  "Nonlinear programming" , ''Proc. Second Berkeley Symp. Math. Stat. Probab.'' , California Univ. Press  (1951)  pp. 481–492</TD></TR>
 +
<TR><TD valign="top">[8]</TD> <TD valign="top">  C. Udrişte,  "Convex functions and optimization methods on Riemannian manifolds" , Kluwer Acad. Publ.  (1994)</TD></TR>
 +
<TR><TD valign="top">[9]</TD> <TD valign="top">  S.P. Boyd,  L. Vandenberghe,  "Convex Optimization" , Cambridge University Press  (2004). {{DOI|10.1017/CBO9780511804441}}</TD></TR>
 +
</table>

Latest revision as of 13:25, 3 May 2016

2020 Mathematics Subject Classification: Primary: 49Kxx [MSN][ZBL]

KKT conditions, Karush–Kuhn–Tucker optimality conditions, KKT optimality conditions, Kuhn–Tucker conditions

Consider the general mathematical programming problem: \begin{equation} \begin{array}{lll} \mbox{minimize} & f(x), & x\in\mathbb{R}^n \\ \mbox{subject to} & g_i(x)\leq 0, & i=1,\ldots,p,\\ & h_j(x)=0, & j=1,\ldots,q, \end{array} \end{equation} with $f$, $g_i$, $h_j$ all continuously differentiable ($C^1$-functions), and form the Lagrangian function \begin{equation} L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{p}\lambda_i g_i(x) + \sum_{j=1}^{q}\mu_j h_j(x). \end{equation} The Karush–Kuhn–Tucker optimality conditions now are: \begin{equation} \label{eq:1} \begin{array}{rl} \dfrac{\partial}{\partial x_k}L(x,\lambda,\mu)=0, & k=1,\ldots,n,\\ \lambda_i\geq 0, & i=1,\ldots,p,\\ \lambda_i g_i(x)=0, & i=1,\ldots,p,\\ g_i(x)\leq 0, & i=1,\ldots,p,\\ h_j(x)=0, & j=1,\ldots,q. \end{array} \end{equation} Note that the two last conditions just say that $x$ is feasible and that the third conditions could be replaced by $\sum\lambda_i g_i(x)=0$ (given the second and fourth). Under suitable constraint qualifications, the KKT optimality conditions are necessary conditions for a local solution $x^*$ of the general mathematical programming problem, in the following sense.

If $x^*$ is a local minimum, then there are corresponding $\lambda^*$, $\mu^*$ such that the triple $(x^*,\lambda^*,\mu^*)$ satisfies the KKT optimality conditions. A triple satisfying the KKT optimality conditions is sometimes called a KKT-triple.

This generalizes the familiar Lagrange multipliers rule to the case where there are also inequality constraints.

The result was obtained independently by Karush in 1939, by F. John in 1948, and by H.W. Kuhn and J.W. Tucker in 1951, see [1], [7].

One suitable constraint qualification (for the case where there are no equality constraints) is $\overline{D}(x^*)=D(x^*)$, where $\overline{D}(x^*)$ is the closure of \begin{equation} D(x^*)=\left\{d\colon\exists\sigma > 0\colon\sigma\geq\tau\geq 0 \Rightarrow x^*+\tau d \quad\text{feasible}\right\} \end{equation} and \begin{equation} D(x^*)=\left\{d\colon\nabla g_i(x^*)^T d\geq 0,\quad i=1,\ldots,p\right\}, \end{equation} where $\nabla g_i(x^*)$ is the gradient vector of $g_i$ at $x^*$, \begin{equation} \nabla g_i(x^*)^T=\left(\dfrac{\partial g_i}{\partial x_1}(x^*),\ldots,\dfrac{\partial g_i}{\partial x_n}(x^*)\right), \end{equation} see [2].

Given a KKT-triple $(x^*,\lambda^*,\mu^*)$, there are also (as in the case of Lagrange multipliers) second-order sufficient conditions that ensure local optimality of $x^*$.


Comment

The KKT conditions \eqref{eq:1} provide a criterion for testing whether a solution which has been found by other methods is in fact an optimal solution.

The KKT conditions have been generalized in various directions:

  • to necessary or sufficient conditions, or both types, for an extremum of a function subject to equality or inequality constraints [6]; especially in case of convex functions $f$ and $g_i$ and affine $h_j$, the KKT conditions \eqref{eq:1} are sufficient, see [9], pp. 243–246.
  • to changing the geometrical structure of the underlying manifold [6], [8].
  • Fritz John condition.


References

[1] A.V. Fiacco, G.P. McCormick, "Nonlinear programming, sequential unconstrained minimization techniques" , SIAM (1968) (Edition: Reprinted)
[2] W.I. Zangwill, "Nonlinear programming" , Prentice-Hall (1969)
[3] O.L. Mangasarian, "Nonlinear programming" , McGraw-Hill (1969)
[4] G.P. McCormick, "Nonlinear programming: theory, algorithms, and applications" , Wiley (1983)
[5] Jong-Shi Pang, "Complementarity problems" R. Horst (ed.) P.M. Pardalos (ed.) , Handbook of Global Optimization , Kluwer Acad. Publ. (1995) pp. 271–338
[6] K.J. Arrow, L. Hurwicz, H. Uzawa, "Studies in linear and nonlinear programming" , Stanford Univ. Press (1958)
[7] H.W. Kuhn, A.W. Tucker, "Nonlinear programming" , Proc. Second Berkeley Symp. Math. Stat. Probab. , California Univ. Press (1951) pp. 481–492
[8] C. Udrişte, "Convex functions and optimization methods on Riemannian manifolds" , Kluwer Acad. Publ. (1994)
[9] S.P. Boyd, L. Vandenberghe, "Convex Optimization" , Cambridge University Press (2004). DOI 10.1017/CBO9780511804441
How to Cite This Entry:
Karush-Kuhn-Tucker conditions. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Karush-Kuhn-Tucker_conditions&oldid=13879
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article