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 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 redigera

 
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   och   är lokala minima och alla tre markerade punkter uppfyller KKT-villkoren.

Antag att man har en funktion som ska minimeras med vissa bivillkor.

 

I sådana fall uppfyller en tillåten punkt som är funktionens optimum (punkten x*) följande villkor:

 

Där koefficenterna  . Endast aktiva bivillkor ska påverka, så:

 

Det vill säga, antingen är koefficienterna noll eller så är bivillkoret aktivt.

Källor redigera

  • Jan Lundgren, Mikael Rönnquist, Peter Värbrand (2003). Optimeringslära (2. upplagan). Lund: Studentlitteratur. ISBN 91-44-03104-1