凸最適化-凸集合
$ S \ subseteq \ mathbb {R} ^ n $とします。集合Sの任意の2点を結ぶ線分も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 −
- 2つの凸集合の和集合は、凸である場合とそうでない場合があります。
- 2つの凸集合の交点は常に凸です。
Proof
$ S_1 $と$ S_2 $を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 $および$ \：and \：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] $
$ 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 $
しかし、$ 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 $
したがって、誘導によって証明された。