kReese.net

A Karush-Kuhn-Tucker (KKT) körülmények, nevezik a Kuhn-Tucker feltételek, azok a feltételek, hogy egy lineáris programozási feladat, meg kell felelniük annak érdekében, hogy optimális. A KKT feltételeit kiterjeszti a Lagrange szorzók módszere, lehetővé téve az egyenlőtlenség korlátokat, ellentétben a Lagrange szorzók, amely csak akkor engedi egyenlőség megszorítások.

Nézzünk egy nemlineáris optimalizálási feladat:

Kis méret $f(x)$
hatálya alá tartozó: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Hadd $x^{*}$ képviselnek relatív minimum pont a mi problémánk, amely szintén megfelel bizonyos kényszert képesítés. Ezzel, akkor feltételezhetjük, hogy minden elem létezik egy vektor $\lambda_j \left ( j = 1, \ldots, l \right )$ , ahol l számát jelenti, az egyenlőség megszorítások, és $\mu_i\left ( i = 1, \ldots, m \right )$ , ahol m számát jelenti az egyenlőtlenség megszorítások. Ezek a konstansok, $\lambda_j$ és $\mu_i$ , nevezzük KKT multiplikátorok.

Annak érdekében, hogy a KKT feltételek tartott egy nemlineáris programozási feladat (NLP), Ezután mind a három feltételnek kell teljesülnie [1-4]. A Primal megvalósíthatósági újfent kijelenti, hogy mi a probléma, hogy az egyenlőtlenség és egyenlőség megszorítások $x^*$ teljesülniük kell ahhoz, hogy a probléma, hogy az optimális:

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

A második feltétel az úgynevezett kettős megvalósíthatósági feltételt. Ebben az állapotban Államokban, meglehetősen bőbeszédű, hogy minden eleme $\mu_i$ nagyobbnak kell lennie nullánál, és hogy a stacionaritását a problémát meg kell egyeznie 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)}$

A stacionaritását a probléma:

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

Míg a másik kettő egyszerűen feltételek l és m kell teljesíteniük ahhoz, hogy $x^*$ optimálisnak.

A harmadik feltétel, hogy meg kell felelni az úgynevezett kiegészítő lazaság. Ez az állapot egyszerűen kimondja, hogy minden egyes mű és saját egyenlőtlenség megszorítás, A termék a két nullát kell eredményeznie:

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

Ha e három feltétel teljesül, találkoztunk a KKT feltételeket és a megoldás, $x^*$ , egy optimális megoldás a problémára NLP. Ott talán több x A tér, amely megfelel a feltételeknek. Minden pont a problémát térben, ahol minden elemétlésm, úgy, hogy a leírónak (x, l, m) megfelelnek a feltételeknek nevezzük KKT KKT pont. Származtatása ezek a korlátok megtalálható [1,2]

Megszorítás Képesítési

Mint korábban említettük, pontok, hogy mi tesztelünk, meg kell felelniük bizonyos képesítést ahhoz, hogy a pontot kell figyelembe venni. A legismertebb kvalifikáció kényszer a lineáris függetlenség korlát selejtező (Licq), amely egyszerűen kimondja, hogy $h_{j}(x^*)$ és $g_{i}(x^*)$ lineárisan független a többi pontban $x^*$ . A Mangasarian-Fromovitz megszorítás képesítés (MFCQ) kimondja, hasonlóan a Licq azzal a kiegészítéssel, hogy pozitív-at független lineraly $x^*$ . [5]

Vannak azonban egyéb korlátozások selejtezők, amelyek ellazítják a Licq. A megszorítás Slater selejtezőn használható domború problémák. Ha létezik olyan x pontot, hogy $h_{j}(x^*) =$ és $g_{i}(x^*) < 0$ minden i,j aktív $x^*$ , akkor a pala állapotban tartja. [5,6]

Más típusú kényszer selejtezők léteznek, de ez a három úgy tűnik, hogy a leggyakrabban használt minősítési KKT.

[1] Kuhn, H. Tucker és, A., “Nemlineáris programozás” Proceedings of the Berkeley 2. Szimpózium 1951, pp. 481-492.
[2] Karush, W., “Minimumai funkciói több Változók egyenlőtlenségek oldali korlátozások”. M.Sc. Értekezés, Univ. A Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “A Karush-Kuhn-Tucker-tétel”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Egyetem. Mannheim, 2006.
[4]McCarl, B. és Spreen, T., “Nemlineáris optimalizálás feltételek”, Ch. 12, Alkalmazott Matematikai Programozás Algebrai Rendszerek. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustace, R. Karas, E. és Ribeiro, Egy. Megszorítás jogosultság Nemlineáris programozás, Tech Report, Univ. A Parana.
[6] Tiba, D. és Zalinescu, C. “Annak szükségességéről, néhány Constraint képzettségi feltételeit a konvex programozás”, Konvex analízis Lapja, 11 (1), 2004. pp 95-110.

A Computer Science and Teaching Journal

Legutóbbi hozzászólások

Karush-Kuhn-Tucker feltételek

Megszorítás Képesítési