Condicions de Karush-Kuhn-Tucker

Les condicions de Karush-Kuhn-Tucker (també conegudes com les condicions KKT o Kuhn-Tucker) són requeriments necessaris i suficients per a que la solució d'un problema de programació matemàtica siga òptima. És una generalisació del método dels multiplicadors de Lagrange.

Problema general d'optimisació

Considerem el següent problema general:

$\text{min }f(x)$

$\text{sujeto a }$

$g_i(x)\le 0$, $i=1,\dots ,m$

$h_j(x)=0$, $j=1,\dots ,l$

a on $f(x)$ és la funció objectiu a minimisar, $g_i(x)$ són les restriccions de desigualtat i $h_j(x)$ són les restriccions d'igualtat, en $m$ i $l$ el número de restriccions de desigualtat i igualtat, respectivament.

Les condicions necessàries per a problemes en restriccions de desigualtat varen ser publicades per primera volta en la tesis de màster de W. Karush, encara que varen ser renombradas despuix d'un artícul en una conferència d'Harold W. Kuhn i Albert W. Tucker.

Condicions necessàries de primer orde

Supongam que la funció objectiu, per eixemple, a minimisar, és $f:{ℝ}^n\to ℝ$ i les funcions de restricció són $g_i:{ℝ}^n\to ℝ$ i $h_j:{ℝ}^n\to ℝ$. Llavors, supongam que són contínuament diferenciables en el punt $x^{*}$. Si $x^{*}$ és un mínim local, llavors existixen constants $\lambda \ge 0$, ${\mu }_i\ge 0(i=1,\dots ,m)$ i ${\nu }_j(j=1,\mathrm{...},l)$ no totes nules tals que:

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

$\lambda \mathrm{\nabla }f(x^{*})+\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{g}_i(x^{*})+\sum _{j=1}^l{\nu }_j\mathrm{\nabla }{h}_j(x^{*})=0,$

${\mu }_i{g}_i(x^{*})=0\text{para todo}i=1,\dots ,m.$

Referències

Bibliografia

• 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).

Vore també

• Teorema de Karush Kuhn Tucker aplicat a un Problema de Programació No Llineal
• L'artícul de A. Kuhn i W. Tucker (anglés)