Condițiile Karush-Kuhn-Tucker

Condițiile Karush–Kuhn–Tucker (KKT) sunt condiții necesare și suficiente de găsire a soluțiilor pentru probleme neliniare. Condițiile KKT pot fi folosite pentru rezolvarea unor probleme care conțin constrângeri de tip egalitate și inegalitate, fiind o generalizare a multiplicatorilor Lagrange, care pot fi folosiți doar pentru constrângeri de tip egalitate. Sistemul de ecuații care corespunde soluțiilor KKT nu poate fi mereu rezolvat analitic, în acest caz fiind nevoie de metode numerice de optimizare. Multi algoritmi de optimizare pot fi interpretați ca fiind metode numerice care rezolva sistemul de ecuații KKT. 

Condițiile KKT sunt numite după matematicienii Harold W. Kuhn si Albert W. Tucker care le-au publicat în 1951. Mai târziu s-a descoperit faptul ca William Karush a dedus condițiile necesare în teza sa de masterat din 1939.

Definiție

Se considera următoarea problema de optimizare non-liniară:

maximizează $f(x)$

astfel încât

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

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

unde x este variabila ce trebuie optimizată, $f$ este funcția obiectiv ce trebuie maximizată (denumită și funcție de cost), $g_{i}\ (i=1,\ldots ,m)$ sunt funcțiile de constrângere de tip inegalitate, iar $h_{j}\ (j=1,\ldots ,l)$ sunt funcțiile de constrângere de tip egalitate. Parametrii m și l reprezinta numărul de constrângeri de tip inegalitate, respectiv egalitate.

Condițiile necesare KKT

Se presupune că atât funcția obiectiv $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ cât și funcțiile de constrângere $g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R}$ și $h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R}$ sunt continue și derivabile într-un punct $x^{*}$. Dacă $x^{*}$ este un punct de minim local care satisface anumite condiții de regularitate, atunci există $\mu _{i}\ (i=1,\ldots ,m)$ și $\lambda _{j}\ (j=1,\ldots ,l)$, denumiți multiplicatori KKT, astfel încât următoarele 4 condiții KKT sunt satisfăcute:

Diagrama de optimizare cu constrângeri.

Condiția Lagrange de staționaritate

pentru maximizarea lui f(x): $\nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*}),$

pentru minimizarea lui f(x): $-\nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*}),$

Condiția de fezabilitate primară

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

$h_{j}(x^{*})=0,{\mbox{ for all }}j=1,\ldots ,l\,\!$

Condiția de fezabilitate duală

$\mu _{i}\geq 0,{\mbox{ for all }}i=1,\ldots ,m$

Condiția de staționaritate complementară – lipsă de energie

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

In cazul în care $m=0$, (i.e. atunci când nu exista constrângeri de tip inegalitate), conditiile KKT corespund metodei multiplicatorilor Lagrange, iar multiplicatorii KKT sunt numiți multiplicatori Lagrange.

Dacă funcțiile din cerinta problemei nu sunt derivabile în punctul $x^{*}$, se pot aplica asa-numitele versiuni subdiferentiale ale teoremei Karush–Kuhn–Tucker (KKT).