kReese.net

De Karush-Kuhn-Tucker (EZ) voorwaarden, soms aangeduid als de Kuhn-Tucker voorwaarden, zijn de voorwaarden die een niet-lineaire programmeren probleem moet voldoen om te worden optimaal. De KKT voorwaarden breidt de methode van Lagrange multipliers, doordat voor ongelijkheid beperkingen, in tegenstelling tot de Lagrange multiplicatoren, die staan alleen gelijkheid beperkingen.

Laten we eens een niet-lineaire optimalisatie probleem:

Een minimum te beperken $f(x)$
onderworpen aan: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

We zullen laten $x^{*}$ vertegenwoordigen een relatief minimum punt voor ons probleem, die voldoet aan ook een aantal beperkingen kwalificatie. Met deze, dan kunnen we aannemen dat voor elk element is er een vector bestaat $\lambda_j \left ( j = 1, \ldots, l \right )$ , waar de staat voor het aantal van gelijkheid beperkingen, en $\mu_i\left ( i = 1, \ldots, m \right )$ , waar m staat voor het aantal van de ongelijkheid beperkingen. Deze constanten, $\lambda_j$ en $\mu_i$ , worden genoemd KKT multipliers.

Om de KKT voorwaarden die moeten worden gehouden in een niet-lineaire programmering probleem (NLP), dan elk van de drie voorwaarden moet worden voldaan [1-4]. De Primal Haalbaarheid herhaalt wat het probleem staten, dat de ongelijkheid en gelijkheid beperkingen op $x^*$ moet worden voldaan om voor het probleem dat moet worden optimaal:

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

De tweede voorwaarde is bekend als de dubbele voorwaarde haalbaarheid. In deze toestand staten, eerder verbosely, dat elk element in $\mu_i$ moet groter zijn dan nul, en dat de stationariteit van het probleem moet gelijk zijn aan 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)}$

De stationariteit van het probleem is:

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

Terwijl de andere twee zijn gewoon voorwaarden die l en m moet voldoen om voor $x^*$ te worden optimale.

De derde voorwaarde waaraan moet worden voldaan is bekend als complementair losheid. Deze voorwaarde staat gewoon dat voor elk mu en de respectieve ongelijkheid beperking, het product van de twee zou moeten leiden tot nul:

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

Wanneer deze drie voorwaarden is voldaan, we have met the KKT conditions and our solution, $x^*$ , is een optimale oplossing voor de NLP probleem. Er misschien meer dan een x in de ruimte die voldoen aan de voorwaarden. Elk punt in het probleem ruimte waar elk element vanlenm, zodanig dat de tupel (x, l, m) voldoen aan de KKT voorwaarden worden genoemd KKT punten. Afleiding van deze beperkingen kan worden gevonden in [1,2]

Constraint Kwalificaties

Zoals eerder vermeld, de punten die we testen noodzaak om een aantal kwalificatie te ontmoeten voor het punt te worden beschouwd. De meest bekende beperking Kwalificatie is de lineaire onafhankelijkheid constraint Kwalificatie (Licq), waarin staat gewoon dat $h_{j}(x^*)$ en $g_{i}(x^*)$ zijn lineair onafhankelijk van de andere in punt $x^*$ . De Mangasarian-Fromovitz constraint kwalificatie (MFCQ) Ook de staten Licq met de toevoeging van positief-lineraly onafhankelijk op $x^*$ . [5]

Er zijn echter andere beperking qualifiers die de Licq ontspannen. De Slater beperking kwalificatie kan worden gebruikt in convexe problemen. Als er een punt x zodanig dat $h_{j}(x^*) =$ en $g_{i}(x^*) < 0$ voor alle i,j die actief zijn in $x^*$ , dan is de lei conditie houdt. [5,6]

Andere vormen van dwang qualifiers bestaan, maar deze drie lijken de meest gebruikte in de KKT kwalificatie.

[1] Kuhn, H. en Tucker, A., “Niet-lineaire programmeren” Werkzaamheden van de 2e Berkeley Symposium 1951, pp. 481-492.
[2] Karush, W., “Minima van functies van meerdere variabelen met ongelijkheid als zijde Constraints”. M. Sc. Proefschrift, Univ. van Chicago, Chicago, De, 1939.
[3] Kuhn, M. “De Karush-Kuhn-Tucker theorema”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Koninkrijk. Mannheim, 2006.
[4]McCarl, B. en Spreen, T., “Niet-lineaire optimalisatie Voorwaarden”, Ch. 12, Applied Mathematical Programming Met behulp van algebraïsche Systems. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. Ribeiro en, Een. Beperking Kwalificatie voor lineaire programmeren, Tech Report, Univ. van Parana.
[6] Aankomen, D. en Zalinescu, C. “Over de noodzaak van sommige Constraint Kwalificatie Voorwaarden in Convex Programming”, Tijdschrift voor Convex Analyse, 11 (1), 2004. pp 95-110.

Een Informatica en Onderwijs Journal

Recente berichten

Karush-Kuhn-Tucker voorwaarden

Constraint Kwalificaties