Visa källa för Karush–Kuhn–Tucker-villkor

'''Karush–Kuhn–Tucker-villkor''' (eller '''KKT-villkor''') är ett villkor som måste vara uppfyllt för att en punkt ska vara en [[optimallösning]] till ett [[Optimeringslära|optimeringsproblem]]. Villkoret är nödvändigt men inte tillräckligt, det vill säga om villkoret är uppfyllt så behöver det inte betyda att punkten är optimum. Dock är det säkert att optimum uppfyller villkoret så en punkt som inte uppfyller villkoret kan inte vara optimum.

== Villkoren ==
[[Fil:KKT two restraints.png|miniatyr|Funktionen f med gradient enligt bilden och bivillkoren rött (utanför cirkeln) och grönt (innanför cirkeln). Det tillåtna området är grårandigt. Punkterna <math>x^1</math> och <math>x^3</math> är lokala minima och alla tre markerade punkter uppfyller KKT-villkoren.]]
Antag att man har en funktion som ska minimeras med vissa bivillkor.
:<math>\mbox{min} f(x) \text{ med bivillkoren } g_i(x) \le b_i</math>
I sådana fall uppfyller en tillåten punkt som är funktionens optimum (punkten x<sup>*</sup>) följande villkor:
:<math>\nabla f(x^*) + \sum_{i=1}^m v_i \nabla g_i(x^*) = 0</math>
Där koefficenterna <math>v_i \ge 0</math>. Endast aktiva bivillkor ska påverka, så:
:<math>v_i \ (g_i (x^*) - b_i) = 0.</math>
Det vill säga, antingen är koefficienterna noll eller så är bivillkoret aktivt.

== Källor ==
* {{Bokref|författare=Jan Lundgren, Mikael Rönnquist, Peter Värbrand|titel=Optimeringslära|år=2003|upplaga=2. upplagan|utgivare=Studentlitteratur|utgivningsort=Lund|id={{ISBN|91-44-03104-1}}}}

[[Kategori:Optimeringslära]]
[[Kategori:Matematiska och kvantitativa metoder (nationalekonomi)]]

[[de:Konvexe Optimierung#Karush-Kuhn-Tucker-Bedingungen]]