Karush-Kuhn-Tucker Tính tối ưu Các điều kiện cần thiết

Xem xét vấn đề -

$ min \: f \ left (x \ right) $ sao cho $ x \ in X $, trong đó X là tập hợp mở trong $ \ mathbb {R} ^ n $ và $ g_i \ left (x \ right) \ leq 0, i = 1, 2, ..., m $

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

Giả sử $ \ hat {x} \ trong S $ và cho $ f $ và $ g_i, i \ in I $ có thể phân biệt được ở $ \ hat {x} $ và $ g_i, i \ trong J $ liên tục ở $ \ hat {x} $. Hơn nữa, $ \ bigtriangledown g_i \ left (\ hat {x} \ right), i \ in I $ độc lập tuyến tính. Nếu $ \ hat {x} $ giải quyết cục bộ vấn đề trên, thì có $ u_i, i \ in I $ sao cho

$ \ bigtriangledown f \ left (x \ right) + \ displaystyle \ sum \ limit_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $, $ \: \: u_i \ geq 0, tôi trong I $

Nếu $ g_i, i \ in J $ cũng có thể phân biệt được ở $ \ hat {x} $. sau đó $ \ hat {x} $, sau đó

$ \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $

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

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

Thí dụ

Hãy xem xét vấn đề sau -

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

sao cho $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5 $,

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

Cho $ 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} $ và $ g_4 \ left (x_1, x_2 \ right) = - x_2 $

Do đó, các ràng buộc trên có thể được viết là:

$ 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, $ và $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Do đó, $ I = \ left \ {1,2 \ right \} $ , $ 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 ) $ và

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

Do đó, đặt các giá trị này trong điều kiện đầu tiên của điều kiện Karush-Kuhn-Tucker, chúng tôi nhận được -

$ u_1 = \ frac {1} {3} $ và $ u_2 = \ frac {2} {3} $

Như vậy điều kiện Karush-Kuhn-Tucker được thỏa mãn.