kReese.net

Den Karush-Kuhn-Tucker (KKT) villkor, ibland kallad Kuhn-Tucker villkor, är de villkor som en ickelinjär programmering problemet behöver uppfylla för att vara optimalt. Den KKT villkoren förlänger metod Lagrangian multiplikatorer genom att tillåta ojämlikhet begränsningar, i motsats till den Lagrange multiplikatorer, som endast tillåter jämlikhet begränsningar.

Låt oss betrakta en ickelinjär optimeringsproblem:

Minimera $f(x)$
under förutsättning att: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Vi kommer att låta $x^{*}$ utgör en relativt lägsta punkt för vårt problem, som uppfyller också några hinder examen. Med den här, då kan vi anta att för varje element det finns en vektor $\lambda_j \left ( j = 1, \ldots, l \right )$ , där l representerar antalet jämlikhet begränsningar, och $\mu_i\left ( i = 1, \ldots, m \right )$ , där m representerar antalet ojämlikhet begränsningar. Dessa konstanter, $\lambda_j$ och $\mu_i$ , kallas KKT opinionsbildare.

För att KKT villkor som ska hållas i en ickelinjär programmering problem (UFO), då vart och ett av tre villkor måste vara uppfyllda [1-4]. Den Primal Genomförbarhet upprepar vad problemet stater, att den ojämlikhet och begränsningar jämlikhet på $x^*$ måste vara uppfyllda för det problem som skall optimala:

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

Det andra villkoret är känd som den dubbla möjligheten skick. I detta tillstånd stater, snarare verbosely, att varje element i $\mu_i$ måste vara större än noll, och att stationaritet av problemet måste vara lika med 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)}$

Den stationaritet till problemet är:

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

Medan de andra två är helt enkelt förhållanden som l och m måste uppfylla för att $x^*$ att vara optimalt.

Det tredje villkoret som måste uppfyllas är känt som ett komplement slapphet. Detta tillstånd anger helt enkelt att för varje mu och dess respektive ojämlikhet tvång, produkten av de två bör resultera i noll:

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

När dessa tre villkor är, vi har med KKT villkoren och vår lösning, $x^*$ , är en optimal lösning för NLP problemet. Det kanske mer än en x i utrymmet som uppfyller villkoren. Varje punkt i problemet utrymme där varje element ilochm, så att tupel (x, l, m) uppfyller KKT villkoren kallas KKT poäng. Härledning av dessa begränsningar finns i [1,2]

Constraint Kvalifikationer

Som nämnts tidigare, de punkter som vi testar behöver träffa några kvalifikationer för att den punkt som anses vara. Den mest kända begränsning Qualification är linjärt oberoende tvång Qualification (Licq), som säger helt enkelt att $h_{j}(x^*)$ och $g_{i}(x^*)$ är linjärt oberoende från de andra vid punkt $x^*$ . Den Mangasarian-Fromovitz tvång examen (MFCQ) stater Likaså licq med tillägg av att vara positiv-lineraly oberoende vid $x^*$ . [5]

Det finns dock andra begränsning kval att slappna av licq. Den Slater begränsning kvalmatch kan användas i konvexa problem. Om det finns en punkt x så att $h_{j}(x^*) =$ och $g_{i}(x^*) < 0$ för alla i,j aktiv i $x^*$ , då skiffer tillståndet har. [5,6]

Andra typer av tvång kval existerar, men dessa tre verkar vara den vanligaste i KKT kvalificering.

[1] Kuhn, H. och Tucker, A., “Nonlinear Programming” Proceedings of 2: a Berkeley Symposium 1951, PP. 481-492.
[2] Karush, W., “Minima av funktioner av flera variabler med ojämlikheter som Side Begränsningar”. M. Sc. Disputation, Univ.. av Chicago, Chicago, Den, 1939.
[3] Kuhn, M. “Den Karush-Kuhn-Tucker teorem”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM universitet. Mannheim, 2006.
[4]McCarl, B. och Spreen, T., “Ickelinjär optimering Villkor”, Ch. 12, Tillämpad matematisk programmering med algebraiska system. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. och Ribeiro, En. Constraint Kvalificering för ickelinjär programmering, Tech Report, Univ.. of Parana.
[6] Ankomst, D. och Zalinescu, C. “Om nödvändigheten av att vissa villkor Constraint Yrkesexamen i Konvex programmering”, Journal of Konvex Analys, 11 (1), 2004. PP 95-110.

En Datavetenskap och undervisning tidning

Senaste inlägg

Karush-Kuhn-Tucker villkor

Constraint Kvalifikationer