Kuhn-Tuckerove podmienky

V tejto časti sa budeme zaoberať stanovením podmienok optimálnosti pre sústavu ohraničení v tvare \(D_1\):  \[ f(\mathbf{x})=\mathbf{x}^TC\mathbf{x}+\mathbf{p}^T\mathbf{x} \to \min\]\[Ax\leq b\]\[x\geq 0.\]Inak povedané, podmienky optimálnosti Kuhn-Tuckera  nám pomôžu pri hľadaní riešenia úlohy \(\hbox{KP}\). Keďže účelová funkcia \(f\) je konvexná a diferencovateľná na celom \(\mathbb{R}^n\) a navyše množina prípustných riešení je určená lineárnymi podmienkami, tak je vhodné použiť Langrangeovu funkciu s multiplikátormi  \(u_1\in \mathbb{R}^m\) a \(u_2\in \mathbb{R}^n\) pri hľadaní viazaného extrému:  \[L(x,u)=x^TCx+p^Tx+u_1^T(Ax-b)+u_2^T(-x) .\]Rozhodovacie premenné sú nezáporné, a tak môžeme použiť zovšobecnenú Langrangeovu funkciu v tvare:  \[L(x,u)=x^TCx+p^Tx+u^T(Ax-b). \]

Postup na získanie Kuhn-Tuckerových podmienok:

K stanoveniu Kuhn-Tuckerových podmienok sú potrebné parciálne derivácie Langrageovej funkcie \(L(x,u)\) nakoľlko jej lokálne extrémy sú aj viazanými extrémami danej funkcie \(f\) na príslušnej väzbe:  \[\frac{\partial  L}{\partial u}=Ax-b,\quad \frac{\partial  L}{\partial x}=2Cx+p+A^Tu.\]Pre vypočítané derivácie majú platiť podmienky komplementárnej rovnováhy v tvare: \[\frac{\partial  L}{\partial x}\geq 0,\quad x\frac{\partial  L}{\partial x}=0,\quad x\geq 0,\]\[\frac{\partial  L}{\partial u}\leq 0,\quad u\frac{\partial  L}{\partial u}=0,\quad u\geq 0.\] Z vypočítaných parciálnych derivácií  dostávame  \[ 2Cx+p+A^Tu\geq 0,\quad Ax+b\leq 0,\]\[ x^T(2Cx+p+A^Tu)= 0,\quad u^T(Ax-b)=0,\]\[ x\geq 0\quad u\geq 0.\]Zavedením vhodných substitúcií, t.j. nových premenných \(v\in \mathbb{R}^n\), \(y\in \mathbb{R}^m\) \[\frac{\partial  L}{\partial x}=2Cx+p+A^Tu=v,\quad \frac{\partial  L}{\partial u}=Ax-b=-y\] a následnom dosadení dostávame hľadanú sústavu:\[ 2Cx+p+A^Tu=v \geq 0\]\[x_j.v_j=0 \hbox{ pre } j=1,\dots,n\]\[ x\geq 0\]\[ Ax-b=-y\leq 0\]\[u_i.y_i=0 \hbox{ pre } i=1,\dots,m\]\[ u\geq 0,\] resp. po malých úpravách sústavu v tvare: \[ -2Cx-A^Tu+v=p\]\[Ax+y=b\]\[x\geq 0,u\geq 0,v\geq 0,y\geq 0\]\[x_j.v_j=0 \hbox{ pre } j=1,\dots,n\]\[u_i.y_i=0 \hbox{ pre } i=1,\dots,m. \]