Optymalizacja wypukła - zestaw wypukły

Niech $ S \ subseteq \ mathbb {R} ^ n $ A zbiór S jest wypukły, jeśli odcinek linii łączący dowolne dwa punkty zbioru S również należy do S, tj. Jeśli $ x_1, x_2 \ in S $ , a następnie $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $, gdzie $ \ lambda \ in \ left (0,1 \ right) $.

Note -

  • Połączenie dwóch wypukłych zbiorów może być wypukłe lub nie.
  • Przecięcie dwóch wypukłych zbiorów jest zawsze wypukłe.

Proof

Niech $ S_1 $ i $ S_2 $ będą dwoma wypukłymi zbiorami.

Niech $ S_3 = S_1 \ cap S_2 $

Niech $ x_1, x_2 \ in S_3 $

Ponieważ $ S_3 = S_1 \ cap S_2 $, więc $ x_1, x_2 \ in S_1 $ i $ x_1, x_2 \ in S_2 $

Ponieważ $ S_i $ jest wypukłe, $ \ for all $ $ i \ in 1,2, $

Zatem $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ gdzie $ \ lambda \ in \ left (0,1 \ right) $

Dlatego $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_1 \ cap S_2 $

$ \ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_3 $

Stąd $ S_3 $ jest zbiorem wypukłym.

  • Średnia ważona z postaci $ \ Displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, gdzie $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ i $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ nazywa się stożkową kombinacją $ x_1, x_2, .... x_k. $

  • Średnia ważona z postaci $ \ Displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, gdzie $ \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1 $ nazywa się połączeniem afinicznym $ x_1 , x_2, .... x_k. $

  • Średnia ważona z postaci $ \ Displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ nazywa się liniową kombinacją $ x_1, x_2, .... x_k $

Przykłady

Step 1 - Udowodnij, że zbiór $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ jest zbiorem wypukłym.

Rozwiązanie

Niech $ x_1 $ i $ x_2 \ in S $

$ \ Rightarrow Cx_1 \ leq \ alpha $ i $ \: oraz \: Cx_2 \ leq \ alpha $

Aby pokazać: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ po prawej) $

$ Cy = C \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = \ lambda Cx_1 + \ left (1- \ lambda \ right) Cx_2 $

$ \ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $

$ \ Rightarrow Cy \ leq \ alpha $

$ \ Rightarrow y \ in S $

Dlatego $ S $ jest zbiorem wypukłym.

Step 2 - Udowodnij, że zestaw $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ jest wypukły zestaw.

Rozwiązanie

Niech $ x, y \ w S $

Niech $ x = \ left (x_1, x_2 \ right) $ i $ y = \ left (y_1, y_2 \ right) $

$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ i $ y_ {1} ^ {2} \ leq 8y_2 $

Aby pokazać - $ \ 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) \ right] $

$ Now, \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} = \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) x_1y_1 $

Ale 2x_1y_1 $ \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $

W związku z tym,

$ \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 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 \ right) 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 \ right] $

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ in S $

Step 3 - Pokaż, że zbiór $ S \ in \ mathbb {R} ^ n $ jest wypukły wtedy i tylko wtedy, gdy dla każdej liczby całkowitej k każda wypukła kombinacja dowolnych k punktów $ S $ jest w $ S $.

Rozwiązanie

Niech $ S $ będzie zbiorem wypukłym. następnie, aby pokazać;

$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ w S, \ Displaystyle \ suma \ limit_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall ja \ in 1,2, ...., k $

Dowód przez indukcję

Dla $ k = 1, x_1 \ in S, c_1 = 1 \ Rightarrow c_1x_1 \ in S $

Dla $ k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1 $ i Ponieważ S jest zbiorem wypukłym

$ \ Rightarrow c_1x_1 + c_2x_2 \ in S. $

Niech wypukła kombinacja m punktów S jest w S ie,

$ c_1x_1 + c_2x_2 + ... + c_mx_m \ w S, \ Displaystyle \ suma \ limity_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall ja \ in 1,2, ..., m $

Teraz niech $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $

Niech $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $

Niech $ 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} $

Niech $ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $

$ \ Rightarrow x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) y + \ mu_ {m + 1} x_ {m + 1} $

Teraz $ y \ w S $, ponieważ suma współczynników wynosi 1.

$ \ Rightarrow x \ in S $, ponieważ S jest zbiorem wypukłym, a $ y, x_ {m + 1} \ w S $

Stąd udowodniono przez indukcję.