Karush–Kuhn–Tucker-förhållanden

Inom matematisk optimering är Karush –Kuhn–Tucker (KKT) villkoren , även kända som Kuhn–Tucker villkoren , första derivata tester (ibland kallade första ordningens nödvändiga villkor ) för att en lösning i olinjär programmering ska vara optimal , förutsatt att vissa villkoren för regelbundenhet är uppfyllda.

Genom att tillåta ojämlikhetsbegränsningar generaliserar KKT:s tillvägagångssätt för icke-linjär programmering metoden med Lagrange-multiplikatorer , som endast tillåter jämlikhetsbegränsningar. I likhet med Lagrange-metoden skrivs problemet med begränsad maximering (minimering) om som en Lagrange-funktion vars optimala punkt är en sadelpunkt , dvs ett globalt maximum (minimum) över domänen för valvariablerna och ett globalt minimum (maximum) över multiplikatorer, vilket är anledningen till att Karush–Kuhn–Tuckers sats ibland kallas för sadelpunktssatsen.

KKT-villkoren var ursprungligen uppkallade efter Harold W. Kuhn och Albert W. Tucker , som först publicerade villkoren 1951. Senare forskare upptäckte att de nödvändiga förutsättningarna för detta problem hade angetts av William Karush i sin magisteravhandling 1939.

Icke-linjärt optimeringsproblem

Tänk på följande olinjära minimerings- eller maximeringsproblem :

optimera $f(\mathbf {x} )$

med förbehåll för

$g_{i}(\mathbf {x} )\leq 0,$

$h_{j}(\mathbf {x} )=0.$

där $\mathbf {x} \in \mathbf {X}$ är optimeringsvariabeln vald från en konvex delmängd av ${\displaystyle \mathbb {R} ^{n}} ,$ f $\displaystyle f}$ är objektivet eller hjälpfunktionen , $(i=1,\ldots ,m)}$ \ olikhetsbegränsningsfunktionerna och $h_{j}\ (j=1,\ldots ,\ell )$ är likhetsbegränsningsfunktionerna . Antalet olikheter och likheter betecknas med $m$ respektive $\ell$ . Motsvarande det begränsade optimeringsproblemet kan man bilda den lagrangska funktionen

${\mathcal {L}}(\mathbf {x} ,\mathbf {\mu} ,\mathbf {\lambda } )=f(\mathbf {x} )+\mathbf {\mu } ^ {\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )=L(\mathbf {x} ,\ mathbf {\alpha } )=f(\mathbf {x} )+\mathbf {\alpha } ^{\top }{\begin{pmatrix}\mathbf {g} (\mathbf {x} )\\\mathbf { h} (\mathbf {x} )\end{pmatrix}}$

där ${\displaystyle \mathbf {g} (\mathbf {x} )=\left(g_{1}(\mathbf {x } ),\ldots ,g_{m}(\mathbf {x} )\right)^{\top }} ,$ h $\ displaystyle \mathbf {h} (\mathbf {x} )=\left(h_{1}(\mathbf {x} ),\ldots ,h_{\ell }(\mathbf {x} )\right)^{\ topp }}$ . Karush –Kuhn–Tuckers sats säger sedan följande.

Sats. Om $(\mathbf {x} ^{\ast },\mathbf {\alpha } ^{\ast })$ är en sadelpunkt för $L(\mathbf {x} ,\mathbf {\alpha } )$ i $\mathbf {x} \in \mathbf {X}$ , $\mathbf {\alpha } \geq \mathbf {0}$ , då är $\mathbf {x} ^{\ast }$ en optimal vektor för ovanstående optimeringsproblem. Antag att $f(\mathbf {x} )$ och $g_{i}(\mathbf {x} )$ , $\displaystyle i=1,\ldots ,m}$ , är konvexa i $\mathbf {x}$ och att det finns $\mathbf {x} _{0}\i \mathbf {X}$ så att $\mathbf {g} (\mathbf {x} _{0})<0$ . Sedan med en optimal vektor $\mathbf {x} ^{\ast }$ för ovanstående optimeringsproblem associeras en icke-negativ vektor $\mathbf {\alpha } ^{\ast }$ så att $(\mathbf {x} ^{\ast },\mathbf {\alpha } ^{\ast })$ är en sadelpunkt för ${ \displaystyle L(\mathbf {x} ,\mathbf {\alpha } )}$ .

Eftersom idén med detta tillvägagångssätt är att hitta ett stödjande hyperplan på den möjliga mängden ${\displaystyle \mathbf {\Gamma } =\left \{\mathbf {x} \in \mathbf {X} :g_{i}(\mathbf {x} )\leq 0,i=1,\ldots ,m\right\}} , beviset på$ Karush– Kuhn–Tuckers teorem använder sig av hyperplanseparationssatsen .

Systemet av ekvationer och ojämlikheter som motsvarar KKT-förhållandena löses vanligtvis inte direkt, förutom i de få speciella fall där en sluten lösning kan härledas analytiskt. I allmänhet kan många optimeringsalgoritmer tolkas som metoder för att numeriskt lösa KKT-systemet av ekvationer och ojämlikheter.

Nödvändiga förutsättningar

Antag att objektivfunktionen $f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$$g_{ i}\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$ begränsningsfunktionerna och $h_{j}\colon \mathbb {R} ^{n}\rightarrow \ mathbb {R}$ har underderivator i en punkt $x^{*}\i \mathbb {R} ^{n}$ . Om $x^{*}$ är ett lokalt optimum och optimeringsproblemet uppfyller vissa regularitetsvillkor (se nedan), så finns det konstanter $\mu _ {i}\ (i=1,\ldots ,m)$ och $\lambda _{j}\ (j=1,\ldots ,\ell )$ , kallas KKT-multiplikatorer, så att följande fyra grupper av villkor gäller:

Ojämlikhetsbegränsningsdiagram för optimeringsproblem

Stationaritet

För att minimera $f(x)$ : ${\displaystyle \partial f(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\partial h_{j}(x^{*})+ \sum _{i=1}^{m}\mu _{i}\partial g_{i}(x^{*})\ni \mathbf {0} } För att maximera f ( x$

) $( x)}$ : $-\partial f( x^{*})+\summa _{j=1}^{\ell }\lambda _{j}\partial h_{j}(x^{*})+\summa _{i=1}^{ m}\mu _{i}\partial g_{i}(x^{*})\ni \mathbf {0}$

Primal genomförbarhet

$h_{j}(x^{*})=0,{\text{ för }}j=1,\ldots ,\ell \,\!$

${\displaystyle g_{i}(x^{*})\leq 0,{\text{ for }}i=1,\ldots ,m} Dubbel$

genomförbarhet

${ \displaystyle \mu _{i}\geq 0,{\text{ for }}i=1,\ldots ,m} Komplementär$

slackness

$\ summa _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0.$

Det sista villkoret skrivs ibland i ekvivalent form: $\mu _{i}g_{i}(x^{*})=0,{\text{ för }}i=1,\ldots ,m.$

I det speciella fallet $m=0$ , dvs när det inte finns några olikhetsbegränsningar, förvandlas KKT-villkoren till Lagrange-villkor, och KKT-multiplikatorerna kallas Lagrange-multiplikatorer .

Anmärkning om underdifferentialer

Notera att även om $f$ är differentierbar, behöver dess subdifferential inte nödvändigtvis vara $\{\nabla f\}$ . Faktum är $\partial f(x)=\{\nabla f(x)\}$ om $f$ är lägre avgränsad av sin linjära approximation vid $x$ , som

$$f(x')\geq f(x)+\nabla f(x)(x'-x)$$

och annars, $\partial f(x)=\emptyset$ .

Bevis

Teorem — (tillräcklighet) Om det finns en lösning $x^{*}$ till det ursprungliga problemet, en lösning $(u^{*},v^{*} )$ till det dubbla problemet, så att de tillsammans uppfyller KKT-villkoren, då har problemparet stark dualitet, och $x^{*},(u^{*} ,v^{*})$ är ett lösningspar på prim- och dubbla problem.

(nödvändighet) Om problemparet har stark dualitet, då för valfri lösning $x^{*}$ till det primära problemet och vilken lösning som helst $(u^{*}, v^{*})$ till det dubbla problemet måste paret $x^{*},(u^{*},v^{*})$ uppfylla KKT villkor.

Bevis

För det första, för $x^{*},(u^{*},v^{*})$ för att uppfylla KKT-villkoren motsvarar de att de är en Nash-jämvikt .

Fixa $(u^{*},v^{*})$ , och variera $x$ : jämvikt är ekvivalent med primal stationaritet.

Fixa $x^{*}$ , och variera $(u,v)$ : jämvikt är ekvivalent med primal genomförbarhet och komplementär slapphet.

Tillräcklighet: lösningsparet $x^{*},(u^{*},v^{*})$ uppfyller KKT-villkoren, alltså är en Nash-jämvikt, och stänger därför dualitetsgapet.

Nödvändighet: alla lösningspar $x^{*},(u^{*},v^{*})$ måste stänga dualitetsgapet, så de måste utgöra en Nash jämvikt (eftersom ingen av sidorna kunde göra det bättre), så uppfyller de KKT-villkoren.

Tolkning: KKT-villkor som balanserande tvångskrafter i statens rum

Primalproblemet kan tolkas som att man flyttar en partikel i utrymmet $x$ , och utsätter den för tre typer av kraftfält:

• $f$ är ett potentiellt fält som partikeln minimerar. Kraften som genereras av $f$ är $-\partial f$ .
• $g_{i}$ är ensidiga begränsningsytor. Partikeln tillåts röra sig inuti $g_{i}\leq 0$ , men när den nuddar $g_{i}=0$ skjuts den inåt.
• $h_{j}$ är tvåsidiga begränsningsytor. Partikeln tillåts endast röra sig på ytan $h_{j}$ .

Primal stationaritet anger att "kraften" för $\partial f(x^{*})$ är exakt balanserad av en linjär summa av krafter $\partial h_{j}(x^{*})$ och $\partial g_{i}(x^{*})$ .

Dubbel genomförbarhet anger dessutom att alla $\partial g_{i}(x^{*})$ krafter måste vara ensidiga och peka inåt i den möjliga uppsättningen för $x$ .

Dubbel slackness anger att om $g_{i}(x^{*})<0$ , då $x ^{*})}$ kraft måste vara noll, eftersom partikeln inte är på gränsen, kan den ensidiga tvångskraften inte aktiveras.

Matrisrepresentation

De nödvändiga villkoren kan skrivas med jakobianska matriser för begränsningsfunktionerna. Låt $\mathbf {g} (x):\,\!\mathbb {R} ^{n}\högerpil \mathbb {R} ^{m}$ definieras som $\mathbf {g} (x)=\left(g_{1}(x),\ldots ,g_{ m}(x)\right)^{\top }$ och låt $\mathbf {h} (x):\,\!\mathbb {R} ^{n }\rightarrow \mathbb {R} ^{\ell }$ definieras som $\mathbf {h} (x)= \left(h_{1}(x),\ldots ,h_{\ell }(x)\right)^{\top }$ . Låt ${\boldsymbol {\mu }}=\left(\mu _{1},\ldots ,\mu _{m}\right)^{\ top }$ och ${\boldsymbol {\lambda }}=\left(\lambda _{1},\ldots ,\lambda _{\ell }\right )^{\top }$ . Då kan de nödvändiga villkoren skrivas som:

Stationaritet

För att maximera $f(x)$ : $\partial f(x^ {*})-D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}-D\mathbf {h} (x^{*})^{\top } {\boldsymbol {\lambda }}=\mathbf {0}$

För att minimera $f(x)$ : $\partial f(x^{*})+D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}+D\mathbf { h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0}$

Primal genomförbarhet

$\mathbf {g} (x^{* })\leq \mathbf {0}$

$\mathbf {h} (x^{*})=\mathbf {0}$

Dubbel genomförbarhet

${\boldsymbol {\ mu }}\geq \mathbf {0}$

Komplementär slackness

${\boldsymbol {\mu }}^{\top }\mathbf {g} (x^{*} )=0.$

Regelmässighetsvillkor (eller begränsningskvalifikationer)

Man kan fråga sig om en minimeringspunkt $x^{*}$ för det ursprungliga, begränsade optimeringsproblemet (förutsatt att ett sådant existerar) måste uppfylla ovanstående KKT-villkor. Detta liknar att fråga under vilka förhållanden minimeraren $x^{*}$ för en funktion $f(x)$ i ett obegränsat problem måste uppfylla villkoret $\nabla f(x^{*})=0$ . För det begränsade fallet är situationen mer komplicerad, och man kan ange en mängd olika (allt mer komplicerade) "regelbundenhet"-förhållanden under vilka en begränsad minimerare också uppfyller KKT-villkoren. Några vanliga exempel på tillstånd som garanterar detta finns i tabellerna nedan, där LICQ är den mest använda:

Begränsning	Akronym	Påstående
Linjäritetsbegränsningskvalifikation	LCQ	Om $g_{i}$ och $h_{j}$ är affina funktioner behövs inget annat villkor.
Linjär oberoende kvalifikation	LICQ	Gradienterna för de aktiva ojämlikhetsrestriktionerna och gradienterna för likhetsrestriktionerna är linjärt oberoende vid $x^{*}$ .
Mangasarian-Fromovitz begränsningskvalifikation	MFCQ	Gradienterna för likhetsbegränsningarna är linjärt oberoende vid $x^{*}$ och det finns en vektor $d\in \mathbb {R} ^{n}$ så att $\nabla g_{i}(x^{*})^{\top }d<0$ för alla aktiva ojämlikhetsbegränsningar och ${ \displaystyle \nabla h_{j}(x^{*})^{\top }d=0}$ för alla likhetsbegränsningar.
Konstant rangkvalificering	CRCQ	För varje delmängd av gradienterna för de aktiva ojämlikhetsbegränsningarna och gradienterna för likhetsbegränsningarna är rangordningen i närheten av $x^{*}$ konstant.
Konstant positiv linjär beroendekvalifikation	CPLD	För varje delmängd av gradienter av aktiva olikhetsrestriktioner och gradienter av likhetsrestriktioner, om delmängden av vektorer är linjärt beroende vid $x^{*}$ med icke-negativa skalärer associerade med ojämlikhetsrestriktionerna, så förblir den linjärt beroende i en omgivning av $x^{*}$ .
Kvasinormalitetskvalifikation	QNCQ	Om gradienterna för de aktiva ojämlikhetsrestriktionerna och gradienterna för likhetsrestriktionerna är linjärt beroende vid $x^{*}$ med tillhörande multiplikatorer $\lambda _{j}$ för likheter och $\mu _{i}\geq 0$ för olikheter, då finns det ingen sekvens $x_{k}\to x^{*}$ så att $\lambda _{j}\neq 0\Rightarrow \lambda _{j}h_{j}(x_{k})>0$ och $\mu _{i}\neq 0\Högerpil \mu _{i}g_{i}(x_{k})>0.$
Slaters tillstånd	SC	För ett konvext problem (dvs. om man antar minimering, $f,g_{i}$ är konvexa och $h_{j}$ affin), finns det en punkt $x$ så att $h(x)=0$ och ${\displaystyle g_{i}(x)<0.$

De strikta konsekvenserna kan visas

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

och

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

I praktiken föredras kvalifikationer med svagare begränsningar eftersom de gäller ett bredare urval av problem.

Tillräckliga förutsättningar

I vissa fall är de nödvändiga förutsättningarna också tillräckliga för optimalitet. I allmänhet är de nödvändiga villkoren inte tillräckliga för optimalitet och ytterligare information krävs, såsom Second Order Sufficient Conditions (SOSC). För smidiga funktioner involverar SOSC andraderivatan, vilket förklarar dess namn.

De nödvändiga förutsättningarna är tillräckliga för optimalitet om objektivfunktionen $f$ för ett maximeringsproblem är en konkav funktion , olikhetsbegränsningarna $g_{j}$ är kontinuerligt differentierbara konvexa funktioner och likhetsbegränsningarna $h_{i}$ är affina funktioner . På liknande sätt, om objektivfunktionen $f$ för ett minimeringsproblem är en konvex funktion , är de nödvändiga villkoren också tillräckliga för optimalitet.

Det visades av Martin 1985 att den bredare klassen av funktioner där KKT-förhållanden garanterar global optimalitet är de så kallade Typ 1- invexfunktionerna .

Andra ordningens tillräckliga villkor

För jämna, icke-linjära optimeringsproblem ges ett andra ordningens tillräckligt villkor enligt följande.

Lösningen $x^{*},\lambda ^{*},\mu ^{*}$ som finns i avsnittet ovan är ett begränsat lokalt minimum om för lagrangian,

$L(x,\lambda ,\ mu )=f(x)+\summa _{i=1}^{m}\mu _{i}g_{i}(x)+\summa _{j=1}^{\ell }\lambda _ {j}h_{j}(x)$

sedan,

$s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{* },\mu ^{*})s\geq 0$

där $s\neq 0$ är en vektor som uppfyller följande,

${\displaystyle \left[\nabla _{x}g_{i}(x^{*}),\nabla _$

där endast de aktiva olikhetsbegränsningarna $g_{i}(x)$ som motsvarar strikt komplementaritet (dvs där $\displaystyle \mu _{i}>0} )$ tillämpas. Lösningen är ett strikt begränsat lokalt minimum om ojämlikheten också är strikt.

Om $s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{ *},\mu ^{*})s=0$ , tredje ordningens Taylor-expansion av Lagrangian ska användas för att verifiera om $x^{*}$ är ett lokalt minimum. Minimeringen av $f(x_{1},x_{2})=(x_{2} -x_{1}^{2})(x_{2}-3x_{1}^{2})$ är ett bra motexempel, se även Peano-yta .

Ekonomi

Se även: Vinstmaximering

Ofta inom matematisk ekonomi används KKT-metoden i teoretiska modeller för att få kvalitativa resultat. Tänk till exempel på ett företag som maximerar sina försäljningsintäkter med en lägsta vinstbegränsning. Låter $Q$ vara mängden producerad produktion (som ska väljas), $R(Q)$ är försäljningsintäkter med en positiv förstaderivata och med ett nollvärde vid noll produktion, $C(Q)$ vara produktionskostnader med en positiv förstaderivata och med ett icke-negativt värde vid noll utdata, och $G_{\min }$ vara den positiva minsta acceptabla vinstnivån , då är problemet meningsfullt om intäktsfunktionen planar ut så att den till slut blir mindre brant än kostnadsfunktionen. Problemet uttryckt i den tidigare givna minimeringsformuläret är

Minimera $-R(Q)$

beroende av

$G_{\min }\leq R(Q)-C(Q)$

$Q\geq 0,$

och KKT-villkoren är

${\begin{aligned}&\left({\frac { {\text{d}}R}{{\text{d}}Q}}\höger)(1+\mu )-\mu \left({\frac {{\text{d}}C}{{ \text{d}}Q}}\right)\leq 0,\\[5pt]&Q\geq 0,\\[5pt]&Q\left[\left({\frac {{\text{d}}R }{{\text{d}}Q}}\right)(1+\mu )-\mu \left({\frac {{\text{d}}C}{{\text{d}}Q} }\right)\right]=0,\\[5pt]&R(Q)-C(Q)-G_{\min }\geq 0,\\[5pt]&\mu \geq 0,\\[5pt ]&\mu [R(Q)-C(Q)-G_{\min }]=0.\end{aligned}}$

Eftersom $Q=0$ skulle bryta mot minimivinstbegränsningen, har vi $Q>0$ och det tredje villkoret innebär att det första villkoret gäller med likhet. Att lösa den jämställdheten ger

${\frac {{\text{d}}R}{{\text{d}}Q}}={\frac {\mu }{1+\mu }}\left({\frac {{ \text{d}}C}{{\text{d}}Q}}\höger).$

Eftersom det gavs att ${\text{d}}R/{\text{d}}Q$ och ${\text{d}}C/{ \text{d}}Q$ är strikt positiva, denna ojämlikhet tillsammans med icke-negativitetsvillkoret på $\mu$ garanterar att $\mu$ är positiv och därför verkar det intäktsmaximerande företaget på en outputnivå vid vilken marginalintäkten ${\text{d}}R/{\text{d}}Q$ är mindre än marginalkostnaden ${\text{ d}}C/{\text{d}}Q$ — ett resultat som är av intresse eftersom det står i kontrast till beteendet hos ett vinstmaximerande företag, som verkar på en nivå där de är lika.

Värdefunktion

Om vi ​​omprövar optimeringsproblemet som ett maximeringsproblem med konstanta ojämlikhetsbegränsningar:

${\text{Maximera }}\;f(x)$

${\text{subject to }}\$

$g_{i}(x)\leq a_{i},h_{j}(x)=0.$

Värdefunktionen definieras som

$V(a_{1},\ldots ,a_{n})=\sup \limits _{x}f(x)$

${\text{subject to }}\$

$g_{i}(x)\leq a_{i},h_{j} (x)=0$

$j\in \{1,\ldots ,\ell \},i\in \{1 ,\ldots ,m\},$

så domänen för $V$ är $\{a\in \mathbb {R} ^{m}\mid {\text{för vissa }}x\in X,g_{i}(x)\leq a_{i},i\in \ {1,\ldots ,m\}\}.$

Givet denna definition är varje koefficient $\mu _{i}$ hastigheten med vilken värdefunktionen ökar när $a_{i}$ ökar. Således om varje $a_{i}$ tolkas som en resursrestriktion, talar koefficienterna om hur mycket ökning av en resurs kommer att öka det optimala värdet av vår funktion f {\ $f}$ . Denna tolkning är särskilt viktig inom ekonomi och används till exempel i nyttomaximeringsproblem .

Generaliseringar

Med en extra multiplikator $\mu _{0}\geq 0$ , som kan vara noll (så länge som $(\mu _{0},\mu , \lambda )\neq 0$ ), framför $\nabla f(x^{*})$ blir KKTs stationaritetsförhållanden till

${\begin{aligned}&\mu _{0}\,\nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\,\nabla g_{i}(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\,\nabla h_{j}(x^ {*})=0,\\[4pt]&\mu _{j}g_{i}(x^{*})=0,\quad i=1,\dots ,m,\end{aligned}}$

som kallas Fritz John-villkoren . Dessa optimalitetsvillkor gäller utan begränsningskvalifikationer och det motsvarar optimalitetsvillkoret KKT eller (ej-MFCQ) .

KKT-villkoren tillhör en bredare klass av första ordningens nödvändiga villkor (FONC), som tillåter icke-släta funktioner med hjälp av subderivator .

Se även

• Farkas lemma
• Lagrange multiplikator
• Big M-metoden , för linjära problem, som utökar simplexalgoritmen till problem som innehåller "större-än"-begränsningar.
• Interior-point-metod en metod för att lösa KKT-förhållandena.
• Slack variabel

Vidare läsning

•   Andreani, R.; Martinez, JM; Schuverdt, ML (2005). "Om förhållandet mellan konstant positivt linjärt beroendetillstånd och kvasinormalitetskvalifikation". Journal of Optimization Theory and Applications . 125 (2): 473–485. doi : 10.1007/s10957-004-1861-9 . S2CID 122212394 .
•   Avriel, Mordecai (2003). Icke-linjär programmering: analys och metoder . Dover. ISBN 0-486-43227-0 .
•   Boltyanski, V.; Martini, H.; Soltan, V. (1998). "Kuhn-Tuckers sats" . Geometriska metoder och optimeringsproblem . New York: Springer. s. 78–92. ISBN 0-7923-5454-0 .
•   Boyd, S.; Vandenberghe, L. (2004). "Optimalitetsförhållanden" (PDF) . Konvex optimering . Cambridge University Press. s. 241–249. ISBN 0-521-83378-7 .
•   Kemp, Murray C.; Kimura, Yoshio (1978). Introduktion till matematisk ekonomi . New York: Springer. s. 38–73 . ISBN 0-387-90304-6 .
•   Rau, Nicholas (1981). "Lagrange multiplikatorer". Matriser och matematisk programmering . London: Macmillan. s. 156–174. ISBN 0-333-27768-6 .
•   Nocedal, J.; Wright, SJ (2006). Numerisk optimering . New York: Springer. ISBN 978-0-387-30303-1 .
•   Sundaram, Rangarajan K. (1996). "Ojämlikhetsbegränsningar och Kuhns och Tuckers sats" . En första kurs i optimeringsteori . New York: Cambridge University Press. s. 145–171. ISBN 0-521-49770-1 .

externa länkar

• Karush–Kuhn–Tucker-förhållanden med härledning och exempel
• Exempel och handledning om KKTs villkor