Warunki konieczne optymalności Karusha-Kuhna-Tuckera

Rozważ problem -

$ min \: f \ left (x \ right) $ takie, że $ x \ in X $, gdzie X jest zbiorem otwartym w $ \ mathbb {R} ^ n $ i $ g_i \ left (x \ right) \ leq 0, i = 1, 2, ..., m $

Niech $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $

Niech $ \ hat {x} \ in S $ i niech $ f $ i $ g_i, i \ in I $ są różniczkowalne przy $ \ hat {x} $ i $ g_i, i \ in J $ są ciągłe przy $ \ hat {x} $. Co więcej, $ \ bigtriangledown g_i \ left (\ hat {x} \ right), i \ in I $ są liniowo niezależne. Jeśli $ \ hat {x} $ lokalnie rozwiązuje powyższy problem, to istnieje $ u_i, i \ in I $ takie, że

$ \ bigtriangledown f \ lewo (x \ po prawej) + \ Displaystyle \ suma \ limit_ {i \ in I} u_i \ bigtriangledown g_i \ lewo (\ kapelusz {x} \ prawo) = 0 $, $ \: \: u_i \ geq 0, ja \ in I $

Jeśli $ g_i, i \ in J $ są również różniczkowalne w $ \ hat {x} $. potem $ \ hat {x} $, a potem

$ \ bigtriangledown f \ lewo (\ kapelusz {x} \ po prawej) + \ Displaystyle \ sum \ limit_ {i = 1} ^ m u_i \ bigtriangledown g_i \ lewo (\ kapelusz {x} \ prawej) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) = 0, \ forall i = 1,2, ..., m $

$ u_i \ geq 0 \ forall i = 1,2, ..., m $

Przykład

Rozważ następujący problem -

$ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $

takie, że $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5 $,

$ x_1,2x_2 \ geq 0 $ i $ \ hat {x} = \ left (2,1 \ right) $

Niech $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5 $,

$ g_2 \ left (x_1, x_2 \ right) = x_ {1} + 2x_2-4 $

$ g_3 \ left (x_1, x_2 \ right) = - x_ {1} $ i $ g_4 \ left (x_1, x_2 \ right) = - x_2 $

Zatem powyższe ograniczenia można zapisać jako -

$ g_1 \ left (x_1, x_2 \ right) \ leq 0, g_2 \ left (x_1, x_2 \ right) \ leq 0 $

$ g_3 \ left (x_1, x_2 \ right) \ leq 0, $ i $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Zatem $ I = \ left \ {1,2 \ right \} $ dlatego , $ u_3 = 0, \: \: u_4 = 0 $

$ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right) ) $ i

$ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

W ten sposób umieszczając te wartości w pierwszym warunku warunków Karush-Kuhn-Tucker, otrzymujemy -

$ u_1 = \ frac {1} {3} $ i $ u_2 = \ frac {2} {3} $

Zatem warunki Karush-Kuhn-Tuckera są spełnione.