Dışbükey Optimizasyon - Dışbükey Küme
$ S \ subseteq \ mathbb {R} ^ n $ A kümesinin, S kümesinin herhangi iki noktasını birleştiren doğru parçası da S'ye aitse, yani S $ 'daki $ x_1, x_2 \ , sonra $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ $ \ lambda \ in \ left (0,1 \ right) $ olduğu yerde S $.
Note -
- İki dışbükey kümenin birleşimi dışbükey olabilir veya olmayabilir.
- İki dışbükey kümenin kesişimi her zaman dışbükeydir.
Proof
$ S_1 $ ve $ S_2 $ iki dışbükey küme olsun.
$ S_3 = S_1 \ cap S_2 $ olsun
$ X_1, x_2 \ S_3 $ içinde
$ S_3 = S_1 \ cap S_2 $ dolayısıyla $ x_1, x_2 \ S_1 $ ve $ x_1, x_2 \ S_2 $ olarak
$ S_i $ dışbükey küme olduğundan, $ \ forall $ $ i \ in 1,2, $
Böylece $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ S_i $ burada $ \ lambda \ in \ left (0,1 \ right) $
Bu nedenle, S_1 \ cap S_2 $ içinde $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \
S_3 $ içinde $ \ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \
Dolayısıyla, $ S_3 $ bir dışbükey kümedir.
$ \ Displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ formunun ağırlıklı ortalaması, burada $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ ve $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $, $ x_1, x_2, .... x_k'nin konik kombinasyonu olarak adlandırılır.
$ \ Displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ biçiminin ağırlıklı ortalaması, burada $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ $ x_1'in bağıntılı kombinasyonu olarak adlandırılır , x_2, .... x_k. $
$ \ Displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ biçiminin ağırlıklı ortalaması, $ x_1, x_2, .... x_k'nin doğrusal kombinasyonu olarak adlandırılır.
Örnekler
Step 1 - $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ kümesinin bir dışbükey küme olduğunu kanıtlayın.
Çözüm
$ X_1 $ ve $ x_2 \ S $
$ \ Rightarrow Cx_1 \ leq \ alpha $ ve $ \: ve \: Cx_2 \ leq \ alpha $
Göstermek için: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ sağ) $
$ Cy = C \ left (\ lambda x_1 + \ left (1- \ lambda \ sağ) x_2 \ sağ) = \ lambda Cx_1 + \ left (1- \ lambda \ sağ) Cx_2 $
$ \ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $
$ \ Rightarrow Cy \ leq \ alpha $
S $ içinde $ \ Rightarrow y \
Bu nedenle, $ S $ bir dışbükey kümedir.
Step 2 - \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ içinde $ S = \ left \ {\ left (x_1, x_2 \ right) \ kümesinin bir dışbükey olduğunu kanıtlayın Ayarlamak.
Çözüm
S $ da $ x, y \ olsun
$ X = \ left (x_1, x_2 \ right) $ ve $ y = \ left (y_1, y_2 \ right) $ olsun
$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ ve $ y_ {1} ^ {2} \ leq 8y_2 $
- $ \ lambda x + \ left (1- \ lambda \ right) y \ in S \ Rightarrow \ lambda \ left (x_1, x_2 \ right) + \ left (1- \ lambda \ right) \ left (y_1, y_2 \ right) \ in S \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda) y_2] \ in S \ right) \ sağ] $
$ Şimdi, \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} = \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ sağ) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) x_1y_1 $
Ancak $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $
Bu nedenle,
$ \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ sağ) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) \ left (x_ {1} ^ {2} + y_ {1} ^ {2} \ right) $
$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda x_ {1} ^ {2} + \ left (1- \ lambda \ sağ) y_ {1} ^ {2} $
$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ lambda x_2 + 8 \ left (1- \ lambda \ right) y_2 $
$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ left [\ lambda x_2 + \ left (1- \ lambda \ right) y_2 \ sağ] $
$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ S $ içinde
Step 3 - Bir $ S \ in \ mathbb {R} ^ n $ kümesinin dışbükey olduğunu gösterin, ancak ve ancak her tamsayı için $ S $ 'nın herhangi bir k noktasının her dışbükey kombinasyonu $ S $' dır.
Çözüm
$ S $ bir dışbükey küme olsun. sonra göstermek için;
$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ in S, \ displaystyle \ sum \ limits_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ 1,2, ...., k $
Tümevarım ile kanıt
$ K = 1, x_1 \ için S, c_1 = 1 \ Rightarrow c_1x_1 \ S $ için
S'de $ k = 2, x_1, x_2 \ için, c_1 + c_2 = 1 $ ve S bir dışbükey küme olduğu için
$ \ Rightarrow c_1x_1 + c_2x_2 \, S. $
S'nin m noktasının dışbükey kombinasyonu S'de olsun, yani,
$ c_1x_1 + c_2x_2 + ... + c_mx_m \ in S, \ displaystyle \ sum \ limits_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ 1,2, ..., m $
Şimdi, S $ içinde $ x_1, x_2 ...., x_m, x_ {m + 1} \
$ X = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $ olsun
$ X = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) \ frac {\ mu_1x_1 + \ mu_2x_2 + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} + \ mu_ {m + 1} x_ {m + 1} $
$ Y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $ olsun
$ \ Rightarrow x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) y + \ mu_ {m + 1} x_ {m + 1} $
Şimdi $ y \ S $ cinsinden çünkü katsayıların toplamı 1'dir.
S $ bir dışbükey küme olduğundan $ \ Rightarrow x \ ve S $ içinde $ y, x_ {m + 1} \
Dolayısıyla tümevarımla kanıtlanmıştır.