凸最適化-凸セット

$ S \ subseteq \ mathbb \ {R} ^ n $とする$、次に$ \ lambda x_1 + \ left（1- \ lambda \ right）x_2 \ in S $ここで$ \ lambda \ in \ left（0,1 \ right）$。

注-

2つの凸集合の和集合は凸である場合とそうでない場合があります。
2つの凸集合の交点は常に凸です。

証明

$ 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。$の線形結合と呼ばれます。

例

ステップ1 *-$ S = \ left \\ {x \ in \ mathbb \ {R} ^ n：Cx \ leq \ alpha \ right \} $が凸集合であることを証明する

溶液

$ x_1 $と$ x_2を\ 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 $は凸集合です。

ステップ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 $

ステップ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はS $になります。

Sは凸集合であり、$ y、x _ \ {m + 1} \ in S $であるため、$ \ Rightarrow x \ in S $

したがって、誘導によって証明されました。

Convex-optimization-set

目次

凸最適化-凸セット

例

溶液

溶液

溶液