Tối ưu hóa lồi - Bộ lồi
Cho $ S \ subseteq \ mathbb {R} ^ n $ Một tập hợp S được cho là lồi nếu đoạn thẳng nối hai điểm bất kỳ của tập hợp S cũng thuộc S, tức là nếu $ x_1, x_2 \ in S $ , sau đó $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ trong đó $ \ lambda \ in \ left (0,1 \ right) $.
Note -
- Hợp của hai tập lồi có thể lồi hoặc không lồi.
- Giao của hai tập lồi luôn lồi.
Proof
Cho $ S_1 $ và $ S_2 $ là hai tập lồi.
Cho $ S_3 = S_1 \ cap S_2 $
Cho $ x_1, x_2 \ trong S_3 $
Vì $ S_3 = S_1 \ cap S_2 $ nên $ x_1, x_2 \ in S_1 $ và $ x_1, x_2 \ in S_2 $
Vì $ S_i $ là tập lồi nên $ \ forall $ $ i \ in 1,2, $
Do đó $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ trong đó $ \ lambda \ in \ left (0,1 \ right) $
Trước đó, $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ trong S_1 \ cap S_2 $
$ \ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ trong S_3 $
Do đó, $ S_3 $ là một tập hợp lồi.
Trung bình có trọng số của dạng $ \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i $, trong đó $ \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1 $ và $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ được gọi là kết hợp conic của $ x_1, x_2, .... x_k. $
Trung bình có trọng số của dạng $ \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i $, trong đó $ \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1 $ được gọi là kết hợp liên kết của $ x_1 , x_2, .... x_k. $
Trung bình có trọng số của dạng $ \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i $ được gọi là kết hợp tuyến tính của $ x_1, x_2, .... x_k. $
Ví dụ
Step 1 - Chứng minh rằng tập hợp $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ là một tập hợp lồi.
Giải pháp
Cho $ x_1 $ và $ x_2 \ trong S $
$ \ Rightarrow Cx_1 \ leq \ alpha $ và $ \: và \: Cx_2 \ leq \ alpha $
Để hiển thị: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ trong S \: \ forall \: \ lambda \ in \ left (0,1 \ đúng) $
$ 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 \ trong S $
Do đó, $ S $ là một tập lồi.
Step 2 - Chứng minh rằng tập hợp $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ là một tập lồi bộ.
Giải pháp
Cho $ x, y \ trong S $
Cho $ x = \ left (x_1, x_2 \ right) $ và $ y = \ left (y_1, y_2 \ right) $
$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ và $ y_ {1} ^ {2} \ leq 8y_2 $
Để hiển thị - $ \ 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) \ trong S \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda) y_2] \ trong 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 $
Nhưng $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $
Vì thế,
$ \ 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 \ trong S $
Step 3 - Chứng tỏ rằng một tập hợp $ S \ in \ mathbb {R} ^ n $ là lồi khi và chỉ khi với mỗi số nguyên k, mọi tổ hợp lồi của k điểm bất kỳ của $ S $ đều bằng $ S $.
Giải pháp
Cho $ S $ là một tập lồi. sau đó, để hiển thị;
$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ in S, \ displaystyle \ sum \ limit_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ...., k $
Chứng minh bằng quy nạp
Với $ k = 1, x_1 \ in S, c_1 = 1 \ Rightarrow c_1x_1 \ in S $
Với $ k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1 $ và Vì S là một tập lồi
$ \ Rightarrow c_1x_1 + c_2x_2 \ in S. $
Gọi tổ hợp lồi của m điểm của S thuộc S tức là
$ c_1x_1 + c_2x_2 + ... + c_mx_m \ in S, \ displaystyle \ sum \ limit_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ..., m $
Bây giờ, cho $ x_1, x_2 ...., x_m, x_ {m + 1} \ trong S $
Cho $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $
Cho $ 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} $
Cho $ 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} $
Bây giờ $ y \ tính bằng S $ vì tổng các hệ số là 1.
$ \ Mũi tên phải x \ trong S $ vì S là tập lồi và $ y, x_ {m + 1} \ trong S $
Do đó được chứng minh bằng quy nạp.