Выпуклая оптимизация - Халл

Выпуклая оболочка множества точек в S - это граница наименьшей выпуклой области, которая содержит все точки S внутри или на ее границе.

ИЛИ

Пусть $ S \ substeq \ mathbb {R} ^ n $ Выпуклая оболочка S, обозначаемая $ Co \ left (S \ right) $, является совокупностью всех выпуклых комбинаций 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} ^ п \ 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- \ тета \ право) \ Displaystyle \ сумма \ limits_ {я = 1} ^ п \ 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_ {я = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ right] = \ theta \ displaystyle \ sum \ limits_ {я = 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) $

Таким образом, выпуклая оболочка - это выпуклое множество.