볼록 최적화-볼록 집합
$ S \ subseteq \ mathbb {R} ^ n $ 집합 S의 두 점을 연결하는 선분이 S에도 속한다면, 즉 $ x_1, x_2 \ in S $ 인 경우 집합 S는 볼록하다고합니다. , $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ 여기서 $ \ lambda \ in \ left (0,1 \ right) $.
Note −
- 두 볼록 세트의 결합은 볼록 일 수도 있고 아닐 수도 있습니다.
- 두 볼록 세트의 교차점은 항상 볼록합니다.
Proof
$ S_1 $ 및 $ S_2 $를 두 개의 볼록 세트로 지정합니다.
$ S_3 = S_1 \ cap S_2 $
$ x_1, x_2 \ in S_3 $
$ S_3 = S_1 \ cap S_2 $이므로 $ x_1, x_2 \ in S_1 $ 및 $ x_1, x_2 \ in S_2 $
$ S_i $는 볼록 집합이므로 $ \ forall $ $ i \ in 1,2, $
따라서 $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ 여기서 $ \ lambda \ in \ left (0,1 \ right) $
따라서 $ \ 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 $
따라서 $ S_3 $는 볼록한 집합입니다.
$ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, 여기서 $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ 및 $ \ lambda_i \ geq 0 형식의 가중 평균 , \ forall i \ in \ left [1, k \ right] $는 $ x_1, x_2, .... x_k. $의 원추 조합이라고합니다.
$ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ 형식의 가중 평균, 여기서 $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $은 $ x_1의 아핀 조합이라고합니다. , x_2, .... x_k. $
$ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ 형식의 가중 평균을 $ x_1, x_2, .... x_k. $의 선형 조합이라고합니다.
예
Step 1 − $ S = \ left \ {x \ in \ mathbb {R} ^ n : Cx \ leq \ alpha \ right \} $ 집합이 볼록 집합임을 증명합니다.
해결책
$ x_1 $ 및 $ x_2 \ in S $
$ \ Rightarrow Cx_1 \ leq \ alpha $ 및 $ \ : 및 \ : Cx_2 \ leq \ alpha $
표시하려면 : $ \ : \ : y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \ : \ forall \ : \ lambda \ in \ left (0,1 \ 오른쪽) $
$ 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 $
따라서 $ S $는 볼록한 집합입니다.
Step 2 − $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2 : x_ {1} ^ {2} \ leq 8x_2 \ right \} $ 세트가 볼록 함을 증명합니다. 세트.
해결책
$ x, y \ in S $
$ x = \ left (x_1, x_2 \ right) $ 및 $ y = \ left (y_1, y_2 \ right) $
$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ 및 $ 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) \ right] $
$ 지금, \ 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 $
하지만 $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $
따라서,
$ \ 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 − 각 정수 k에 대해 $ S $의 k 포인트의 모든 볼록 조합이 $ S $에있는 경우에만 $ S \ in \ mathbb {R} ^ n $ 세트가 볼록하다는 것을 보여줍니다.
해결책
$ S $를 볼록 집합이라고합시다. 그런 다음 보여주기 위해;
$ 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 \ in 1,2, ...., k $
귀납법에 의한 증명
$ k = 1, x_1 \ in S, c_1 = 1 \ Rightarrow c_1x_1 \ in S $
$ k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1 $ 및 S는 볼록 집합이므로
$ \ Rightarrow c_1x_1 + c_2x_2 \ in S. $
S의 m 점의 볼록한 조합이 S에 있다고합시다.
$ 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 \ in 1,2, ..., m $
이제 $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $
$ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $
$ 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} $
$ \ Rightarrow x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) y + \ mu_ {m + 1} x_ {m + 1} $
이제 계수의 합이 1이므로 $ y \ in S $입니다.
$ \ Rightarrow x \ in S $는 S가 볼록 집합이고 $ y, x_ {m + 1} \ in S $이기 때문입니다.
따라서 귀납법으로 증명되었습니다.