Condicions de Karush-Kuhn-Tucker

En programació no lineal les condicions de Karush-Kuhn-Tucker (també anomenades condicions de KKT, o condicions Kuhn-Tucker) són condicions que ha de complir un punt que sigui solució d'un problema de la forma:

Diagrama de limitació de desigualtat per problemes d'optimització

${\displaystyle \min \ f(x)}$

${\displaystyle g_{i}(x)\leq 0}$ on ${\displaystyle i\in \{1,...,m\}}$

${\displaystyle h_{j}(x)=0}$ on ${\displaystyle j\in \{1,...,l\}}$

On, si definim ${\displaystyle g(x)=(g_{1}(x),...,g_{m}(x))}$ i ${\displaystyle h(x)=(h_{1}(x),...,h_{l}(x))}$:

${\displaystyle f:\ \mathbb {R} ^{n}\rightarrow \mathbb {R} }$

${\displaystyle g:\ \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}}$

${\displaystyle h:\ \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{l}}$

Es tracta d'una generalització del Mètode dels multiplicadors de Lagrange.

Condicions necessàries de 1r ordre

Es tracta d'aplicar les condicions necessàries de 1r ordre per tal que un punt sigui mínim d'una funció de classe ${\displaystyle C^{1}}$ a la funció Lagrangiana:

${\displaystyle L:\ \mathbb {R} ^{n+m+l}\longrightarrow \mathbb {R} }$

${\displaystyle \ (x,\lambda ,\mu )\mapsto f(x)+\lambda ^{T}\cdot g(x)+\mu ^{T}\cdot h(x)}$

Però per tal que els mínims d'aquesta funció coincideixin amb els de ${\displaystyle f(x)}$ cal que imposem un parell de condicions més (que "penalitzen" els punts on no es compleixen les restriccions). Les condicions necessàries de KKT de primer ordre ens diuen que:

Si ${\displaystyle x^{*}}$ és mínim relatiu de ${\displaystyle f(x)}$ on ${\displaystyle f\in C^{1}}$, aleshores existeixen ${\displaystyle \lambda \in \mathbb {R} ^{m}}$ i ${\displaystyle \mu \in \mathbb {R} ^{l}}$ tals que:

1-

${\displaystyle \nabla f(x^{*})+\lambda ^{*^{T}}\cdot \nabla g(x^{*})+\mu ^{*^{T}}\cdot \nabla h(x^{*})=0}$

2-

${\displaystyle \lambda _{i}\cdot g_{i}(x^{*})=0}$

3-

${\displaystyle \lambda _{i}\geq 0}$

Problema general d'optimització

Considerem el següent problema general:

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

${\displaystyle {\text{subjecte a }}\ }$

${\displaystyle \ g_{i}(x)\leq 0\ }$, ${\displaystyle \ i=1,\ldots ,m}$

${\displaystyle \ h_{j}(x)=0\ }$, ${\displaystyle \ j=1,\ldots ,l}$

on ${\displaystyle f(x)}$ és la funció objectiu a minimitzar, ${\displaystyle g_{i}(x)}$ són les restriccions de desigualtat i ${\displaystyle h_{j}(x)}$ són les restriccions d'igualtat, amb ${\displaystyle m}$ i ${\displaystyle l}$ el nombre de restriccions de desigualtat i igualtat, respectivament.

Les condicions necessàries per a problemes amb restriccions de desigualtat van ser publicades per primera vegada en la tesi de màster de W. Karush,^[1] encara que van ser renombradas després d'un article en una conferència de Harold W. Kuhn i Albert W. Tucker.^[2]

Condicions suficients

Si ${\displaystyle f}$ és una funció convexa definida en un domini convex, aleshores les condicions de KKT són suficients. Sigui ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ la funció objectiu i les funcions de restricció ${\displaystyle g_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ siguin funcions convexes i ${\displaystyle h_{j}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ siguin les funcions d'afinitat, i sigui un punt ${\displaystyle x^{*}}$. Si existeixen constants ${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$ i ${\displaystyle \nu _{j}\ (j=1,\ldots ,l)}$ tals que

${\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{per tot}}\;i=1,\ldots ,m,}$

Aleshores el punt ${\displaystyle x^{*}}$ és un mínim global.

Referències

1. W. Karush «Minima of Functions of Several Variables with Inequalities as Side Constraints». Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois, 1939.. disponible en http://wwwlib.umi.com/dxweb/details?doc_no=7371591%5BEnllaç+no+actiu%5D (amb càrrec)
2. H. W. Kuhn,Tucker, A. W., Proceedings of 2nd Berkeley Symposium, Nonlinear programming, University of California Press, 1951, Berkeley

Bibliografia

• Andreani, R.; Martínez, J. M.; Schuverdt, M. L. «On the relation between constant positive linear dependence condition and quasinormality constraint qualification». Journal of Optimization Theory and Applications, 125, 2, 2005, pàg. 473–485. DOI: 10.1007/s10957-004-1861-9.
• Avriel, Mordecai. Nonlinear Programming: Analysis and Methods. Dover, 2003. ISBN 0-486-43227-0.
• Boyd, S.; Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004. ISBN 0-521-83378-7.
• Nocedal, J.; Wright, S. J.. Numerical Optimization. Nova York: Springer, 2006. ISBN 978-0-387-30303-1.
• Sundaram, Rangarajan K. «Inequality Constraints and the Theorem of Kuhn and Tucker». A: A First Course in Optimization Theory. Nova York: Cambridge University Press, 1996, p. 145–171. ISBN 0-521-49770-1.