凸最適化-ハル

Sの点のセットの凸包は、その内部または境界上のSのすべての点を含む最小の凸領域の境界です。

または

$ S \ subseteq \ mathbb {R} ^ n $とします。$ Co \ left（S \ right）$で表されるSの凸包は、Sのすべての凸結合の集合です。つまり、$ x \ in Co \ left （S \ right）$ $ x \ in \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $の場合に限り、$ \ displaystyle \ sum \ limits_ {1} ^ n \ lambda_i = 1 $および$ \ lambda_i \ geq 0 \ forall x_i \ in S $

Remark −平面内のSの点のセットの凸面は凸多角形を定義し、多角形の境界上のSの点は多角形の頂点を定義します。

Theorem $ Co \ left（S \ right）= \ left \ {x：x = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i、x_i \ in S、\ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1、\ lambda_i \ geq 0 \ right \} $凸包が凸集合であることを示します。

証明

$ x_1、x_2 \ in Co \ left（S \ right）$とし、次に$ x_1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $および$ x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ \ gamma x_i $ここで、$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1、\ lambda_i \ geq 0 $、および$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = 1、\ gamma_i \ geq0 $

$ \ theta \ in \ left（0,1 \ right）、\ theta x_1 + \ left（1- \ theta \ right）x_2 = \ theta \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i + \ leftの場合（1- \ theta \ right）\ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_ix_i $

$ \ theta x_1 + \ left（1- \ theta \ right）x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i \ theta x_i + \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i \左（1- \ theta \ right）x_i $

$ \ theta x_1 + \ left（1- \ theta \ right）x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left（1- \ theta \ right）\右] x_i $

係数を考慮すると、

$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left（1- \ theta \ right）\ right] = \ theta \ displaystyle \ sum \ limits_ {i = 1 } ^ n \ lambda_i + \ left（1- \ theta \ right）\ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = \ theta + \ left（1- \ theta \ right）= 1 $

したがって、$ \ theta x_1 + \ left（1- \ theta \ right）x_2 \ in Co \ left（S \ right）$

したがって、凸包は凸集合です。