Karush-Kuhn-Tuckerovy podmínky

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V matematice, Karush-Kuhn-Tuckerovy podmínky (také známé jako Kuhn-Tucker nebo KKT podmínky), jsou nutné podmínky pro hledání optimálního řešení úlohy nelineárního programování, za předpokladu, že i některé další podmínky jsou splněny. Je to zobecnění metody Lagrangeových multiplikátorů na omezující podmínky neobsahující rovnost (může tedy obsahovat nerovnosti). Podmínky jsou pojmenovány po William Karush, Harold W. Kuhn a Albert W. Tucker.

Uvažujme následující nelineární optimalizační problém:

 \mbox{Minimalizujte }\; f(x)
 \mbox{aby platilo: }\
 g_i(x) \le 0 , h_j(x) = 0

kde f (x) je funkce, kterou minimalizujeme, g_i (x)\ (i = 1, \ldots,m) jsou omezující podmínky s nerovnostmi a h_j (x)\ (j = 1,\ldots,l) jsou omezující podmínky s rovnostmi a m, respektive l je počet omezujících podmínek s, respektive bez rovností.

Nezbytné podmínky pro tento problém s obecně danými omezujícími podmínkami byl poprvé zveřejněn v Magisterské práci Williama Karushe [1], i když vešlo ve všeobecnou známost až po zveřejnění prací pánů Harold W. Kuhn a Albert W. Tucker.[2]

Nutné podmínky[editovat | editovat zdroj]

Předpokládejme, že účelová funkce, tj. funkce určená k minimalizaci, je f : \mathbb{R} ^ n \rightarrow \mathbb{R} a funkce v omezeních jsou g_i: \,\!\mathbb{R}^n \rightarrow \mathbb{R} a h_j: \,\!\mathbb{R}^n \rightarrow \mathbb{R}. Dále předpokládejme, že jsou to funkce hladké v bodě x^*. Pokud je x^* lokální minimum, které splňuje určité podmínky regularity, potom existují konstanty \mu_i\ (i = 1,\ldots,m) a \lambda_j\ (j = 1,\ldots,l) takové, že platí podmínky [3]

Podmínka optimality (stacionarity)
\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda_j \nabla h_j(x^*) = 0,
Podmínky přípustnosti
g_i(x^*) \le 0, \mbox{ pro všechna } i = 1, \ldots, m
h_j(x^*) = 0, \mbox{ pro všechna } j = 1, \ldots, l \,\!
Podmínka duality
\mu_i \ge 0, \mbox{ pro všechna } i = 1, \ldots, m
Podmínka komplementarity
\mu_i g_i (x^*) = 0, \mbox{pro všechna}\; i = 1,\ldots,m.

Reference[editovat | editovat zdroj]

  1. W. Karush. Parametr "periodikum" je povinný! .  
  2. In [s. l.] : [s. n.]
  3. .  

Související články[editovat | editovat zdroj]