Karuš-Kun-Takerovi uslovi

U matematičkoj optimizaciji, Karuš-Kun-Takerovi uslovi (KKT), poznati i kao Kun-Takerovi uslovi, su potrebni uslovi da bi rešenje u nelinearnom programiranju bilo optimalno, pod uslovom da su neki uslovi regularnosti ispunjeni.

Dopuštajući ograničenja nejednakosti, KKT pristup nelinearnom programiranju generalizuje metodu Lagranževih množitelja, koja omogućava samo ograničenja jednakosti. Slično Lagranžovom pristupu, problem ograničene optimizacije prepisuje se kao Lagranževa funkcija čija je optimalna tačka sedlasta, tj. globalni maksimum (minimum) nad domenom izabranih varijabli i globalni minimum (maksimum) nad množiteljima, zbog čega se teorema Karuš-Kun–Taker ponekad naziva i teoremom sedla.

KKT uslovi su prvobitno nazvani po Haroldu V. Kunu i Albertu V. Takeru, koji su prvi objavili uslove 1951. godine. Naučnici su kasnije otkrili da je neophodne uslove za ovaj problem naveo Vilijam Karuš u svom master radu 1939. godine.

Problem nelinearne optimizacije

Pretpostavimo da imamo sledeći problem minimizacije ili maksimizacije:

Optimizujte $f(\mathbf {x} )$

prema

$g_{i}(\mathbf {x} )\leq 0,$

$h_{i}(\mathbf {x} )=0.$

gde je $\mathbf {x} \in \mathbf {X}$ optimizaciona varijabla izabrana iz konveksnog podskupa $\mathbb {R} ^{n}$, $f$ je kriterijum optimalnosti, $g_{i}\ (i=1,\ldots ,m)$ su ograničenja tipa nejednakosti, a $h_{i}\ (i=1,\ldots ,\ell )$ su ograničenja tipa jednakosti. Broj ograničenja tipa nejednakosti i jedankosti su $m$ i $\ell$ respektivno. Prema problemu optimizacije sa ograničenjima, formira se funkcija Lagranžijan:

$L(\mathbf {x} ,\mathbf {\mu } )=f(\mathbf {x} )+\mathbf {\mu } ^{\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )$

gde je $\mathbf {g} (\mathbf {x} )=\left(g_{1}(\mathbf {x} ),\ldots ,g_{m}(\mathbf {x} )\right)^{\top }$, $\mathbf {h} (\mathbf {x} )=\left(h_{1}(\mathbf {x} ),\ldots ,h_{\ell }(\mathbf {x} )\right)^{\top }$. Karuš–Kun–Takerova teorema onda tvrdi sledeće.

Teorema. Ako je $(\mathbf {x} ^{\ast },\mathbf {\mu } ^{\ast })$ sedlasta tačka $L(\mathbf {x} ,\mathbf {\mu } )$ u $\mathbf {x} \in \mathbf {X}$, $\mathbf {\mu } \geq \mathbf {0}$, onda $\mathbf {x} ^{\ast }$ je optimalan vektor za optimizacioni problem iznad. Pretpostavimo da $f(\mathbf {x} )$ i $g_{i}(\mathbf {x} )$, $i=1,\ldots ,m$, su konkavne funkcije u $\mathbf {x}$ i da postoji $\mathbf {x} _{0}\in \mathbf {X}$ takav da $\mathbf {g} (\mathbf {x} _{0})>0$. Onda sa optimalnim vektorom $\mathbf {x} ^{\ast }$ za optimizacioni problem iznad postoji pridruženi nenegativni vektor $\mathbf {\mu } ^{\ast }$ takav da $L(\mathbf {x} ^{\ast },\mathbf {\mu } ^{\ast })$ je sedlasta tačka $L(\mathbf {x} ,\mathbf {\mu } )$.

Dodatna literatura

• Andreani, R.; Martínez, J. M.; Schuverdt, M. L. (2005). „On the relation between constant positive linear dependence condition and quasinormality constraint qualification”. Journal of Optimization Theory and Applications. 125 (2): 473—485. doi:10.1007/s10957-004-1861-9. 
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover. ISBN 0-486-43227-0. 
• Boyd, S.; Vandenberghe, L. (2004). „Optimality Conditions” (PDF). Convex Optimization. Cambridge University Press. str. 241—249. ISBN 0-521-83378-7. 
• Kemp, Murray C.; Kimura, Yoshio (1978). Introduction to Mathematical Economics. New York: Springer. str. 38–73. ISBN 0-387-90304-6. 
• Nocedal, J.; Wright, S. J. (2006). Numerical Optimization. New York: Springer. ISBN 978-0-387-30303-1. 
• Sundaram, Rangarajan K. (1996). „Inequality Constraints and the Theorem of Kuhn and Tucker”. A First Course in Optimization Theory. New York: Cambridge University Press. str. 145—171. ISBN 0-521-49770-1. 

Spoljašnje veze

• Karush–Kuhn–Tucker conditions with derivation and examples
• Examples and Tutorials on the KKT Conditions