Konvexe Optimierung - Rumpf

Die konvexe Hülle einer Menge von Punkten in S ist die Grenze des kleinsten konvexen Bereichs, der alle Punkte von S in sich oder an seiner Grenze enthält.

ODER

Sei $ S \ subseteq \ mathbb {R} ^ n $ Die konvexe Hülle von S, die mit $ Co \ left (S \ right) $ bezeichnet wird, ist die Sammlung aller konvexen Kombinationen von S, dh $ x \ in Co \ left (S \ rechts) $ genau dann, wenn $ x \ in \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n \ lambda_ix_i $, wobei $ \ Anzeigestil \ Summe \ Grenzen_ {1} ^ n \ lambda_i = 1 $ und $ \ lambda_i \ geq 0 \ forall x_i \ in S $

Remark - Konve Rumpf einer Menge von Punkten in S in der Ebene definiert ein konvexes Polygon und die Punkte von S an der Grenze des Polygons definieren die Eckpunkte des Polygons.

Theorem $ Co \ left (S \ right) = \ left \ {x: x = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i, x_i \ in S, \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 \ right \} $ Zeigen Sie, dass eine konvexe Hülle eine konvexe Menge ist.

Beweis

Sei $ x_1, x_2 \ in Co \ left (S \ right) $, dann $ x_1 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i $ und $ x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ \ gamma x_i $ wobei $ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ und $ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Für $ \ theta \ in \ left (0,1 \ right), \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ theta \ displaystyle \ sum \ border_ {i = 1} ^ n \ lambda_ix_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_ix_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n \ Lambda_i \ Theta x_i + \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n \ gamma_i \ links (1- \ Theta \ rechts) x_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ border_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ rechts] x_i $

Unter Berücksichtigung der Koeffizienten,

$ \ Anzeigestil \ Summe \ Grenzen_ {i = 1} ^ n \ links [\ lambda_i \ theta + \ gamma_i \ links (1- \ Theta \ rechts) \ rechts] = \ Theta \ Anzeigestil \ Summe \ Grenzen_ {i = 1 } ^ n \ lambda_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ border_ {i = 1} ^ n \ gamma_i = \ theta + \ left (1- \ theta \ right) = 1 $

Daher ist $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Somit ist eine konvexe Hülle eine konvexe Menge.