Karush-Kuhn-Takker-förhållanden

I optimeringsteorin är Karush -Kuhn-Tucker-förhållanden ( Karush-Kuhn-Tucker-förhållanden , KKT) nödvändiga förutsättningar för att lösa ett icke-linjärt programmeringsproblem . För att lösningen ska bli optimal måste vissa regularitetsvillkor uppfyllas. Metoden är en generalisering av Lagrange multiplikatormetoden . Däremot är de begränsningar som läggs på variabler inte ekvationer , utan ojämlikheter .

Historik

Kuhn och Tucker generaliserade Lagrange-multiplikatormetoden (för användning för att konstruera optimalitetskriterier för problem med likhetsbegränsningar) till fallet med ett allmänt icke-linjärt programmeringsproblem med både likhets- och ojämlikhetsbegränsningar [1] .

Nödvändiga förutsättningar för ett lokalt minimum för problem med begränsningar har studerats under lång tid. En av de viktigaste är överföringen av begränsningar till den objektiva funktion som Lagrange föreslagit. Kuhn-Tucker-villkoren härleds också från denna princip [2] .

Förklaring av problemet

I problemet med icke-linjär optimering krävs det att hitta värdet på den flerdimensionella variabeln , vilket minimerar objektivfunktionen: $x=(x^{{(1)}},...,x^{{(n)}})$

\min \limits _{{x\in X}}f(x)

under förhållanden när begränsningar av ojämlikhetstyp åläggs variabeln: $x$

g_{i}(x)\leqslant 0,\;i=1\ldots m

och vektorkomponenterna är icke-negativa [3] . $x$

William Karush fann i sitt examensarbete de nödvändiga förutsättningarna i det allmänna fallet, när de pålagda villkoren kan innehålla både ekvationer och ojämlikheter. Oberoende av honom kom Harold Kuhn och Albert Tucker till samma slutsatser .

Nödvändiga villkor för minimum av en funktion

Om , under de pålagda restriktionerna, är en lösning på problemet, så finns det en vektor av Lagrange-multiplikatorer så att följande villkor är uppfyllda för Lagrange-funktionen : ${\hat {x}}\in \arg \min f$ $\lambda \in \mathbb{R} ^{m}$ $L(x)=f(x)+\summa _{{i=1}}^{m}\lambda _{i}g_{i}(x)$

stationaritet : ; $\min _{x}L(x)=L({\hat {x)))$
kompletterande icke-stelhet : ; $\lambda _{i}g_{i}({\hat {x)))=0,\;i=1\ldots m$
icke - negativitet :. $\lambda _{i}\geqslant 0,\;i=1\ldots m$

Tillräckliga villkor för minimum av en funktion

De angivna nödvändiga villkoren för minimifunktionen i det allmänna fallet är inte tillräckliga. Förutsatt att funktionerna och är konvexa, finns det flera alternativ för ytterligare villkor som gör att villkoren från Karush-Kuhn-Tucker-satsen är tillräckliga: $f$ ${\displaystyle g_{1},\dots ,g_{m))$

Enkel formulering

Om en tillåten punkt uppfyller villkoren för stationaritet, kompletterande icke-rigiditet och icke-negativitet, och även , då . ${\hat {x}}$ $\lambda _{1}>0$ ${\hat {x}}\in \arg \min f$

Svagare förhållanden

Om för en godtagbar punkt villkoren för stationaritet, komplementär icke-rigiditet och icke-negativitet samt ( Slaters villkor ) är uppfyllda, då . ${\hat {x}}$ $\exists {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ ${\hat {x}}\in \arg \min f$

Anteckningar

↑ Kuhn-Tucker villkor . Hämtad 7 februari 2011. Arkiverad från originalet 24 januari 2011. (obestämd)
↑ Zhiliniskas A., Shaltyanis V. Sök efter det optimala: datorn utökar möjligheterna. — M.: Nauka, 1989, sid. 76, ISBN 5-02-006737-7
↑ Mathematical Foundations of Cybernetics, 1980 , sid. 253.

Se även

Operationsforskning

Litteratur

J. Hadley. Icke-linjär och dynamisk programmering. - M . : Mir, 1967. - 506 sid.
Korshunov Yu. M. Matematiska grunder för cybernetik. - M . : Energi, 1980. - 424 sid.