kReese.net

Karush-Kuhn, Tucker (EZ) podmínky, někdy označováno jako Kuhn, Tucker podmínky, jsou podmínky, které nelineární programování problém, je třeba splnit, aby byla optimální. KKT podmínky rozšiřuje metoda Lagrangeových multiplikátorů tím, že pro omezení nerovností, na rozdíl od Lagrange násobiče, které umožňují pouze rovnost omezení.

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

Minimalizovat $f(x)$
předmětem: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Dáme $x^{*}$ představují relativní minimální bod pro náš problém, , která splňuje i několik omezení způsobilosti. S touto, pak můžeme předpokládat, že pro každý prvek existuje vektor $\lambda_j \left ( j = 1, \ldots, l \right )$ , kde l představuje počet žen a mužů omezení, a $\mu_i\left ( i = 1, \ldots, m \right )$ , kde m představuje počet nerovnosti omezení. Tyto konstanty, $\lambda_j$ a $\mu_i$ , se nazývají KKT mínění.

K tomu, aby KKT podmínky, které se uskuteční v nelineární programování problém (NLP), pak každý tři podmínky musí být splněny [1-4]. Primal proveditelnosti připomíná v čem je problém státy, že nerovnost žen a mužů a omezení $x^*$ musí být splněny, aby tento problém za optimální:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

Druhá podmínka je známá jako dual proveditelnosti podmínku. V tomto stavu státech, spíše verbosely, , že každý prvek $\mu_i$ musí být větší než nula, a že stacionarita tohoto problému musí být rovna 0.

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

Stacionarita tohoto problému je:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

Zatímco ostatní dva jsou prostě podmínky, které l a m musí splňovat, aby $x^*$ za optimální.

Třetí podmínkou, která musí být splněna, je znám jako komplementární ochablost. Tento stav pouze uvádí, že pro každou MU a jeho příslušné omezení nerovností, součin dvou by měla vést k nule:

$\mu_i g_{i} \left ( x^* \right ) = 0$

Jsou-li splněny tyto tři podmínky, Setkali jsme se s KKT podmínky a naše řešení, $x^*$ , je optimální řešení problému NLP. Tam možná i více než jeden x v prostoru, které splňují podmínky. Jakýkoli bod v prostoru, kde tento problém každý prveklam, takové, že n-tice (x, l, m) splňovat KKT podmínky se nazývají KKT body. Původ těchto omezení lze najít v [1,2]

Omezení kvalifikace

Jak bylo zmíněno dříve, body, které jsme testování je třeba splnit určité kvalifikace, aby bod, je třeba zvážit. Nejznámější omezení způsobilosti je lineární nezávislost omezení způsobilosti (Licq), , který pouze uvádí, že $h_{j}(x^*)$ a $g_{i}(x^*)$ jsou lineárně nezávislé na ostatních v bodě $x^*$ . Mangasarian-Fromovitz omezení způsobilosti (MFCQ) Stejně tak státy Licq s přidáním být pozitivní, lineraly nezávislý na $x^*$ . [5]

Existují však jiné omezení kvalifikátorů, které uvolňují Licq. Omezení Slater kvalifikace mohou být použity v konvexní problémy. Jestliže existuje bod x tak, že $h_{j}(x^*) =$ a $g_{i}(x^*) < 0$ i pro všechny,j aktivní $x^*$ , pak břidlice podmínka platí. [5,6]

Jiné druhy omezení kvalifikace existují, ale tyto tři se zdají být nejvíce běžně používaný v KKT kvalifikace.

[1] Kuhn, H. a Tucker, A., “Nelineární programování” Sborník z 2. Berkeley sympozium 1951, pp. 481-492.
[2] Karush, W., “Extrémy funkcí více proměnných s nerovností, omezení na straně”. M. Sc. Disertační práce, Univ. of Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “Karush-Kuhn, Tucker teorém”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Británie. Mannheim, 2006.
[4]McCarl, B. a Spreen, T., “Nelineární optimalizace podmínky”, Ch. 12, Aplikovaná Matematické programování pomocí algebraických systémů. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. a Ribeiro, A. Omezení způsobilosti pro nelineární programování, Tech zprávy, Univ. Parana.
[6] Přijet, D. a Zalinescu, C. “Na nutnosti určitých podmínek omezení Kvalifikace v konvexní programování”, Časopis konvexní analýzy, 11 (1), 2004. pp 95-110.

Výpočetní technika a výuka věstníku

Poslední příspěvky

Karush-Kuhn, Tucker podmínky

Omezení kvalifikace