Karush-Kuhn-Takker forhold

I optimeringsteori er Karush-Kuhn-Tucker-betingelser ( Karush-Kuhn-Tucker-betingelser , KKT) nødvendige betingelser for at løse et ikke-lineært programmeringsproblem . For at løsningen bliver optimal, skal nogle regularitetsbetingelser være opfyldt. Metoden er en generalisering af Lagrange multiplikatormetoden . I modsætning hertil er de begrænsninger, der pålægges variabler, ikke ligninger , men uligheder .

Historie

Kuhn og Tucker generaliserede Lagrange-multiplikatormetoden (til brug ved konstruktion af optimalitetskriterier for problemer med lighedsbegrænsninger) til tilfældet med et generelt ikke-lineært programmeringsproblem med både ligheds- og ulighedsbegrænsninger [1] .

Nødvendige betingelser for et lokalt minimum for problemer med begrænsninger har været undersøgt i lang tid. En af de vigtigste er overførslen af begrænsninger til den objektive funktion foreslået af Lagrange. Kuhn-Tucker-betingelserne er også afledt af dette princip [2] .

Udtalelse af problemet

I problemet med ikke-lineær optimering er det nødvendigt at finde værdien af den multidimensionelle variabel , hvilket minimerer den objektive funktion: $x=(x^{{(1)}},...,x^{{(n)}})$

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

under forhold, hvor begrænsninger af ulighedstype er pålagt variablen: $x$

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

og vektorkomponenterne er ikke-negative [3] . $x$

William Karush fandt i sit specialearbejde de nødvendige betingelser i det generelle tilfælde, hvor de pålagte betingelser kan indeholde både ligninger og uligheder. Uafhængigt af ham kom Harold Kuhn og Albert Tucker til de samme konklusioner .

Nødvendige betingelser for minimum af en funktion

Hvis , under de pålagte begrænsninger, er en løsning på problemet, så er der en vektor af Lagrange-multiplikatorer , således at følgende betingelser er opfyldt for Lagrange-funktionen : ${\hat {x}}\in \arg \min f$ $\lambda \in \mathbb{R} ^{m}$ $L(x)=f(x)+\sum _{{i=1}}^{m}\lambda _{i}g_{i}(x)$

stationaritet : ; $\min _{x}L(x)=L({\hat {x)))$
komplementær ikke-stivhed : ; $\lambda _{i}g_{i}({\hat {x)))=0,\;i=1\ldots m$
ikke - negativitet :. $\lambda _{i}\geqslant 0,\;i=1\ldots m$

Tilstrækkelige betingelser for minimum af en funktion

De anførte nødvendige betingelser for minimumsfunktionen i det generelle tilfælde er ikke tilstrækkelige. Forudsat at funktionerne og er konvekse, er der flere muligheder for yderligere betingelser, der gør betingelserne fra Karush-Kuhn-Tucker-sætningen tilstrækkelige: $f$ ${\displaystyle g_{1},\dots ,g_{m))$

Simpel formulering

Hvis et tilladt punkt opfylder betingelserne for stationaritet, komplementær ikke-stivhed og ikke-negativitet, og også , så . ${\hat {x}}$ $\lambda _{1}>0$ ${\hat {x}}\in \arg \min f$

Svagere forhold

Hvis betingelserne for stationaritet, komplementær ikke-stivhed og ikke-negativitet og også ( Slaters betingelse ) er opfyldt for et tilladt punkt , så er . ${\hat {x}}$ $\eksisterer {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ ${\hat {x}}\in \arg \min f$

Noter

↑ Kuhn-Tucker-forhold . Hentet 7. februar 2011. Arkiveret fra originalen 24. januar 2011. (ubestemt)
↑ Zhiliniskas A., Shaltyanis V. Søg efter det optimale: computeren udvider mulighederne. — M.: Nauka, 1989, s. 76, ISBN 5-02-006737-7
↑ Mathematical Foundations of Cybernetics, 1980 , s. 253.

Se også

Operationsforskning

Litteratur

J. Hadley. Ikke-lineær og dynamisk programmering. - M . : Mir, 1967. - 506 s.
Korshunov Yu. M. Matematiske grundlag for kybernetik. - M . : Energi, 1980. - 424 s.