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

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 {\displaystyle x^{1}} och x 3 {\displaystyle 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.

min f ( x )  med bivillkoren  g i ( x ) ≤ b i {\displaystyle {\mbox{min}}f(x){\text{ med bivillkoren }}g_{i}(x)\leq b_{i}}

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

∇ f ( x ∗ ) + ∑ i = 1 m v i ∇ g i ( x ∗ ) = 0 {\displaystyle \nabla f(x^{*})+\sum _{i=1}^{m}v_{i}\nabla g_{i}(x^{*})=0}

Där koefficenterna v i ≥ 0 {\displaystyle v_{i}\geq 0} . Endast aktiva bivillkor ska påverka, så:

v i   ( g i ( x ∗ ) − b i ) = 0. {\displaystyle v_{i}\ (g_{i}(x^{*})-b_{i})=0.}

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

Källor

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