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

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

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

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

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

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

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

према

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

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

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

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

где је ${\displaystyle \mathbf {g} (\mathbf {x} )=\left(g_{1}(\mathbf {x} ),\ldots ,g_{m}(\mathbf {x} )\right)^{\top }}$, ${\displaystyle \mathbf {h} (\mathbf {x} )=\left(h_{1}(\mathbf {x} ),\ldots ,h_{\ell }(\mathbf {x} )\right)^{\top }}$. Каруш–Кун–Такерова теорема онда тврди следеће.

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