Karush–Kuhn–Tucker-villkor

Från Wikipedia
(Omdirigerad från Karush-Kuhn-Tucker-villkor)
Hoppa till: navigering, sök

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 behöver inte punkten vara optimum, men optimum uppfyller villkoret.

Villkoren[redigera | redigera wikitext]

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

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

\mbox{min} f(x) \text{ med bivillkoren } g_i(x) \le b_i

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

\nabla f(x^*) + \sum_{i=1}^m v_i \nabla g_i(x^*) = 0

Där koefficenterna v_i \ge 0. Endast aktiva bivillkor ska påverka, så:

v_i \ (g_i (x^*) - b_i) = 0.

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

Källor[redigera | redigera wikitext]

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