Kondisi yang Diperlukan Karush-Kuhn-Tucker Optimal

Pertimbangkan masalahnya -

$ min \: f \ left (x \ right) $ sedemikian sehingga $ x \ dalam X $, di mana X adalah himpunan terbuka di $ \ mathbb {R} ^ n $ dan $ g_i \ left (x \ right) \ leq 0, i = 1, 2, ..., m $

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

Misalkan $ \ hat {x} \ dalam S $ dan $ f $ dan $ g_i, i \ in I $ dapat dibedakan pada $ \ hat {x} $ dan $ g_i, i \ in J $ kontinu pada $ \ hat {x} $. Selanjutnya, $ \ bigtriangledown g_i \ left (\ hat {x} \ right), i \ in I $ independen linier. Jika $ \ hat {x} $ memecahkan masalah di atas secara lokal, maka ada $ u_i, i \ in I $ sehingga

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

Jika $ g_i, i \ in J $ juga dapat dibedakan pada $ \ hat {x} $. lalu $ \ hat {x} $, lalu

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

$ u_ig_i \ kiri (\ topi {x} \ kanan) = 0, \ untuk semua i = 1,2, ..., m $

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

Contoh

Pertimbangkan masalah berikut -

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

sedemikian rupa sehingga $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5 $,

$ x_1,2x_2 \ geq 0 $ dan $ \ topi {x} = \ kiri (2,1 \ kanan) $

Misalkan $ g_1 \ kiri (x_1, x_2 \ kanan) = x_ {1} ^ {2} + x_ {2} ^ {2} -5 $,

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

$ g_3 \ kiri (x_1, x_2 \ kanan) = - x_ {1} $ dan $ g_4 \ kiri (x_1, x_2 \ kanan) = - x_2 $

Dengan demikian kendala di atas dapat ditulis sebagai -

$ g_1 \ kiri (x_1, x_2 \ kanan) \ leq 0, g_2 \ kiri (x_1, x_2 \ kanan) \ leq 0 $

$ g_3 \ kiri (x_1, x_2 \ kanan) \ leq 0, $ dan $ g_4 \ kiri (x_1, x_2 \ kanan) \ leq 0 $ Jadi, $ I = \ kiri \ {1,2 \ kanan \} $ oleh karena itu , $ u_3 = 0, \: \: u_4 = 0 $

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

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

Jadi dengan menempatkan nilai-nilai ini pada kondisi pertama dari kondisi Karush-Kuhn-Tucker, kita mendapatkan -

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

Dengan demikian kondisi Karush-Kuhn-Tucker terpenuhi.