Convex-optimization-caratheodory-theorem

カラテオドリ定理

Sを$ \ mathbb \ {R} ^ n $の任意のセットとします。$ x \ in Co \ left（S \ right）$の場合、$ x \ in Co \ left（x_1、x_2、…​. 、x_n、x _ \ {n + 1} \ right）$。

証明

$ x \ in Co \ left（S \ right）$であるため、$ x $はSの有限個の点の凸の組み合わせ、つまり、

$ x = \ displaystyle \ sum \ limits _ \ {j = 1} ^ k \ lambda_jx_j、\ displaystyle \ sum \ limits _ \ {j = 1} ^ k \ lambda_j = 1、\ lambda_j \ geq 0 $および$ x_j \ in S、\ forall j \ in \ left（1、k \ right）$

$ k \ leq n + 1 $の場合、得られる結果は明らかに真です。

$ k \ geq n + 1 $の場合、$ \ left（x_2-x_1 \ right）\ left（x_3-x_1 \ right）、…​..、\ left（x_k-x_1 \ right）$は線形依存。

$ \ Rightarrow \ exists \ mu _j \ in \ mathbb \ {R}、2 \ leq j \ leq k $（すべてゼロではない）$ \ displaystyle \ sum \ limits _ \ {j = 2} ^ k \ mu _j \ left（x_j-x_1 \ right）= 0 $

$ \ mu_1 =-\ displaystyle \ sum \ limits _ \ {j = 2} ^ k \ mu _j $を定義し、次に$ \ displaystyle \ sum \ limits _ \ {j = 1} ^ k \ mu_j x_j = 0、\ displaystyle \を定義しますsum \ limits _ \ {j = 1} ^ k \ mu_j = 0 $

ここで、すべての$ \ mu_j’s $がゼロに等しいわけではありません。 $ \ displaystyle \ sum \ limits _ \ {j = 1} ^ k \ mu_j = 0 $なので、少なくとも$ \ mu_j> 0,1 \ leq j \ leq k $のいずれか

次に、$ x = \ displaystyle \ sum \ limits _ \ {1} ^ k \ lambda_j x_j + 0 $

$ x = \ displaystyle \ sum \ limits _ \ {1} ^ k \ lambda_j x_j- \ alpha \ displaystyle \ sum \ limits _ \ {1} ^ k \ mu_j x_j $

$ x = \ displaystyle \ sum \ limits _ \ {1} ^ k \ left（\ lambda_j- \ alpha \ mu_j \ right）x_j $

$ \ alpha = min \ left \\ {\ frac \ {\ lambda_j} \ {\ mu_j}、\ mu_j \ geq 0 \ right \} = \ frac \ {\ lambda_j} \ {\ mu _j}、$の一部の$ i = 1,2、…​、k $

$ \ mu_j \ leq 0の場合、\ lambda_j- \ alpha \ mu_j \ geq 0 $

$ \ mu_j> 0の場合、\：\ frac \ {\ lambda _j} \ {\ mu_j} \ geq \ frac \ {\ lambda_i} \ {\ mu _i} = \ alpha \ Rightarrow \ lambda_j- \ alpha \ mu_j \ geq 0、j = 1、2、…​ k $

特に、$ \ lambda $の定義により、$ \ lambda_i- \ alpha \ mu_i = 0 $

$ x = \ displaystyle \ sum \ limits _ \ {j = 1} ^ k \ left（\ lambda_j- \ alpha \ mu_j \ right）x_j $、ここで

$ \ lambda_j- \ alpha \ mu_j \ geq0 $および$ \ displaystyle \ sum \ limits _ \ {j = 1} ^ k \ left（\ lambda_j- \ alpha \ mu_j \ right）= 1 $および$ \ lambda_i- \ alpha \ mu_i = 0 $

したがって、xは最大（k-1）点の凸の組み合わせとして表すことができます。

この縮小プロセスは、xが（n + 1）要素の凸の組み合わせとして表されるまで繰り返すことができます。