Каруш-Кун-Такерови услови

У математичкој оптимизацији, Каруш-Кун-Такерови услови (ККТ), познати и као Кун-Такерови услови, су потребни услови да би решење у нелинеарном програмирању било оптимално, под условом да су неки услови регуларности испуњени.

Допуштајући ограничења неједнакости, ККТ приступ нелинеарном програмирању генерализује методу Лагранжевих множитеља, која омогућава само ограничења једнакости. Слично Лагранжовом приступу, проблем ограничене оптимизације преписује се као Лагранжева функција чија је оптимална тачка седласта, тј. глобални максимум (минимум) над доменом изабраних варијабли и глобални минимум (максимум) над множитељима, због чега се теорема Каруш-Кун–Такер понекад назива и теоремом седла.

ККТ услови су првобитно названи по Харолду В. Куну и Алберту В. Такеру, који су први објавили услове 1951. године. Научници су касније открили да је неопходне услове за овај проблем навео Вилијам Каруш у свом мастер раду 1939. године.

Проблем нелинеарне оптимизације

Претпоставимо да имамо следећи проблем минимизације или максимизације:

Оптимизујте $f(\mathbf {x} )$

према

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

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

где је $\mathbf {x} \in \mathbf {X}$ оптимизациона варијабла изабрана из конвексног подскупа $\mathbb {R} ^{n}$, $f$ је критеријум оптималности, $g_{i}\ (i=1,\ldots ,m)$ су ограничења типа неједнакости, а $h_{i}\ (i=1,\ldots ,\ell )$ су ограничења типа једнакости. Број ограничења типа неједнакости и једанкости су $m$ и $\ell$ респективно. Према проблему оптимизације са ограничењима, формира се функција Лагранжијан:

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

где је $\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 }$. Каруш–Кун–Такерова теорема онда тврди следеће.

Теорема. Ако је $(\mathbf {x} ^{\ast },\mathbf {\mu } ^{\ast })$ седласта тачка $L(\mathbf {x} ,\mathbf {\mu } )$ у $\mathbf {x} \in \mathbf {X}$, $\mathbf {\mu } \geq \mathbf {0}$, онда $\mathbf {x} ^{\ast }$ је оптималан вектор за оптимизациони проблем изнад. Претпоставимо да $f(\mathbf {x} )$ и $g_{i}(\mathbf {x} )$, $i=1,\ldots ,m$, су конкавне функције у $\mathbf {x}$ и да постоји $\mathbf {x} _{0}\in \mathbf {X}$ такав да $\mathbf {g} (\mathbf {x} _{0})>0$. Онда са оптималним вектором $\mathbf {x} ^{\ast }$ за оптимизациони проблем изнад постоји придружени ненегативни вектор $\mathbf {\mu } ^{\ast }$ такав да $L(\mathbf {x} ^{\ast },\mathbf {\mu } ^{\ast })$ је седласта тачка $L(\mathbf {x} ,\mathbf {\mu } )$.

Додатна литература

• 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. стр. 241—249. ISBN 0-521-83378-7. 
• Kemp, Murray C.; Kimura, Yoshio (1978). Introduction to Mathematical Economics. New York: Springer. стр. 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. стр. 145—171. ISBN 0-521-49770-1. 

Спољашње везе

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