Podmínky Karush-Kuhn-Takker

V teorii optimalizace jsou Karush-Kuhn-Tuckerovy podmínky ( Karush-Kuhn-Tuckerovy podmínky , KKT) nezbytnými podmínkami pro řešení problému nelineárního programování . Aby bylo řešení optimální, musí být splněny určité podmínky pravidelnosti. Metoda je zobecněním metody Lagrangeova multiplikátoru . Naproti tomu omezení uvalená na proměnné nejsou rovnice , ale nerovnosti .

Historie

Kuhn a Tucker zobecnili Lagrangeovu multiplikační metodu (pro použití při konstrukci kritérií optimality pro problémy s omezeními rovnosti) na případ obecného problému nelineárního programování s omezeními rovnosti i nerovnosti [1] .

Nezbytné podmínky pro lokální minimum pro problémy s omezeními byly studovány již dlouhou dobu. Jedním z hlavních je přenesení omezení na účelovou funkci, kterou navrhl Lagrange. Z tohoto principu jsou odvozeny i Kuhn-Tuckerovy podmínky [2] .

Prohlášení o problému

V problému nelineární optimalizace je nutné najít hodnotu vícerozměrné proměnné a minimalizovat účelovou funkci: $x=(x^{{(1)}},...,x^{{(n)}})$

\min \limits _{{x\in X}}f(x)

za podmínek, kdy jsou na proměnnou uvalena omezení typu nerovnosti: $X$

g_{i}(x)\leqslant 0,\;i=1\ldots m

a složky vektoru jsou nezáporné [3] . $X$

William Karush ve své diplomové práci našel potřebné podmínky v obecném případě, kdy vložené podmínky mohou obsahovat jak rovnice, tak nerovnice. Nezávisle na něm došli ke stejným závěrům Harold Kuhn a Albert Tucker .

Nezbytné podmínky pro minimum funkce

Pokud je , pod uloženými omezeními, řešením problému, pak existuje vektor Lagrangeových multiplikátorů takový, že pro Lagrangeovu funkci jsou splněny následující podmínky : ${\hat {x}}\in \arg \min f$ $\lambda \in \mathbb{R} ^{m}$ $L(x)=f(x)+\součet _{{i=1}}^{m}\lambda _{i}g_{i}(x)$

stacionárnost : ; $\min _{x}L(x)=L({\klobouček {x)))$
doplňková nerigidita : ; $\lambda _{i}g_{i}({\hat {x)))=0,\;i=1\ldots m$
nezápornost : . $\lambda _{i}\geqslant 0,\;i=1\ldots m$

Dostatečné podmínky pro minimum funkce

Uvedené nezbytné podmínky pro minimální funkci v obecném případě nestačí. Za předpokladu, že funkce a jsou konvexní, existuje několik možností pro dodatečné podmínky, díky nimž jsou podmínky z Karush-Kuhn-Tuckerovy věty dostatečné: $F$ ${\displaystyle g_{1},\tečky ,g_{m))$

Jednoduchá formulace

Pokud přípustný bod splňuje podmínky stacionarity, doplňkové nerigidity a nezápornosti a také , pak . ${\klobouk {x}}$ $\lambda _{1}>0$ ${\hat {x}}\in \arg \min f$

Slabší podmínky

Pokud jsou pro přípustný bod splněny podmínky stacionarity, komplementární nerigidity a nezápornosti a také ( Slaterova podmínka ), pak . ${\klobouk {x}}$ $\exists {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ ${\hat {x}}\in \arg \min f$

Poznámky

↑ Kuhn-Tuckerovy podmínky . Získáno 7. února 2011. Archivováno z originálu 24. ledna 2011. (neurčitý)
↑ Zhiliniskas A., Shaltyanis V. Hledání optima: počítač rozšiřuje možnosti. — M.: Nauka, 1989, s. 76, ISBN 5-02-006737-7
↑ Matematické základy kybernetiky, 1980 , s. 253.

Viz také

Operační výzkum

Literatura

J. Hadley. Nelineární a dynamické programování. - M .: Mir, 1967. - 506 s.
Korshunov Yu.M. Matematické základy kybernetiky. - M .: Energie, 1980. - 424 s.