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.  ^[1]

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

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

maximizează ${\displaystyle f(x)}$

astfel încât

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

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

unde x este variabila ce trebuie optimizată, ${\displaystyle f}$ este funcția obiectiv ce trebuie maximizată (denumită și funcție de cost), ${\displaystyle g_{i}\ (i=1,\ldots ,m)}$ sunt funcțiile de constrângere de tip inegalitate, iar ${\displaystyle 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.

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

Condiția Lagrange de staționaritate

pentru maximizarea lui f(x): ${\displaystyle \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): ${\displaystyle -\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ă

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

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

Condiția de fezabilitate duală

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

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

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

In cazul în care ${\displaystyle 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 ${\displaystyle x^{*}}$, se pot aplica asa-numitele versiuni subdiferentiale ale teoremei Karush–Kuhn–Tucker (KKT).^[5]

Portal matematică