kReese.net

Karush-Kuhn-Tucker (EZ) sąlygos, kartais nurodoma kaip Kuhn-Tucker sąlygomis, sąlygos, kad Netiesinė Programavimas problema turi atitikti siekiant būti optimalus. KKT sąlygos išplečia Lagrangian skleidėjus metodą, leidžiant nelygybės apribojimus, , palyginti su Lagranžo daugiklis, kuris tik leidžia apribojimų lygybės.

Panagrinėkime netiesinio optimizavimo problemą:

Minimizuoti $f(x)$
atsižvelgiant į: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Mes leis $x^{*}$ santykinę minimalią tašką mūsų problema, kuri taip pat atitinka tam tikrą kvalifikaciją apribojimo. Su šiuo, tada mes galime daryti prielaidą, kad kiekvieno elemento egzistuoja vektorius $\lambda_j \left ( j = 1, \ldots, l \right )$ , kur l yra apribojimų lygybės, ir $\mu_i\left ( i = 1, \ldots, m \right )$ , kur m atspindi nelygybės apribojimų skaičių. Šios konstantos, $\lambda_j$ ir $\mu_i$ , KKT skleidėjais.

Kad KKT sąlygomis laikomų netiesinio programavimo uždavinio (NLP), tada kiekvienas turi būti įvykdytos trys sąlygos [1-4]. Primal Galimybių kartoja, kas teigiama, problema, kad nelygybė ir lygybė apribojimai $x^*$ turi būti tenkinamos, kad problemos būtų optimalus:

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

Antroji sąlyga yra žinomas kaip dviejų galimybių būklės. Šią sąlygą, o verbosely, kad kiekvienas elementas $\mu_i$ turi būti didesnis už nulį, ir kad turi būti lygi problemos stacionarumas 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)}$

Problemos stacionarumas yra:

$\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$

Nors kiti du yra tiesiog sąlygos, kad l ir m turi atitikti tam, kad $x^*$ būti optimali.

Yra žinomas kaip papildomos tingumas trečioji sąlyga, kad turi būti laikomasi. Ši sąlyga tik nurodo, kad kiekvienam mu ir nelygybė suvaržymus, dviejų produktas turėtų sukelti nulio:

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

Kai šios trys sąlygos yra tenkinamos, mes susitiko su KKT sąlygas ir mūsų sprendimas, $x^*$ , NLP problemos optimalus sprendimas. Yra gal ir daugiau nei vienas x erdvėje, kuri atitinka sąlygas,. Bet problemos erdvės taškas, kuriame kiekvienas elementaslirm, toks, kad Tuple (x, l, m) patenkinti KKT sąlygas KKT taškų. Išvada šiuos apribojimus galima rasti [1,2]

Apribojimų kvalifikacijų

Kaip minėta anksčiau, taškai, kad mes bandymai turi atitikti tam tikrą kvalifikaciją tam, kad taško, turi būti laikoma. Labiausiai žinomas apribojimas Kvalifikacijos Linijinis Nepriklausomybės apribojimas Kvalifikacijos (Licq), kuris tik nurodo, kad $h_{j}(x^*)$ ir $g_{i}(x^*)$ yra tiesiškai nepriklausomi nuo taške $x^*$ . Mangasarian-Fromovitz apribojimas kvalifikacija (MFCQ) teigia panašiai teigiamas-lineraly nepriklausomas to licq $x^*$ . [5]

Tačiau yra kitas suvaržymas apibūdinimų kad atsipalaiduoti licq. Slater apribojimas Qualifier gali būti naudojamas cilindro problemų. Jei egzistuoja taško X, kad $h_{j}(x^*) =$ ir $g_{i}(x^*) < 0$ visiems i,j aktyvus in $x^*$ , tada šiferis sąlyga turi. [5,6]

Kiti tipai ribojantys apibūdinimų egzistuoja, tačiau šie trys atrodo, dažniausiai naudojamas KKT kvalifikacijos.

[1] Kuhn, O. ir Tucker, A., “Netiesinė Programavimas” Proceedings of 2 Berkeley simpoziumo 1951, PP. 481-492.
[2] Karush, W., “Minimumai kelių kintamųjų funkcijų nelygybę suvaržymus”. M.Sc. Disertacija, Univ. Čikagos, Čikaga, Il, 1939.
[3] Kuhn, M. “Karush-Kuhn-Tucker théorème”, Internetas: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Uni. Manheimas, 2006.
[4]McCarl, B. ir Spreen, T., “Netiesiniai Optimizavimo sąlygos”, Ch. 12, Taikomieji Matematinis programavimas Naudojant Algebrinė struktūra. Internetas: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Justas, R. Karas, Ji. ir Ribeiro, A. Netiesinio programavimo apribojimas Kvalifikacijos, Technika Pranešti, Univ. Paranos.
[6] Atvykti, D. ir Zalinescu, C. “Apie kai kuriuos suvaržymus kvalifikacijai keliamus reikalavimus, Iškilioji programavimo Būtinybė”, Iškilioji analizė leidinys, 11 (1), 2004. PP 95-110.

Kompiuterių mokslo ir mokymo leidinys

Naujausios žinutės

Karush-Kuhn-Tucker sąlygos

Apribojimų kvalifikacijų