Выпуклая оптимизация — корпус

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

ИЛИ ЖЕ

Пусть $S \ subseteq \ mathbb {R} ^ n$ Выпуклая оболочка S, обозначаемая как $Co \ left (S \ right)$ by, является совокупностью всех выпуклых комбинаций S, т. Е. $X \ in Co \ left. (S \ right)$ тогда и только тогда, когда $x \ in \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i$, где $\ displaystyle \ sum \ limit_ {1} ^ n \ lambda_i = 1$ и $\ lambda_i \ geq 0 \ forall x_i \ in S$

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

Теорема $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 \}$ Показать, что выпуклая оболочка является выпуклым множеством.

доказательство

Пусть $x_1, x_2 \ in Co \ left (S \ right)$, затем $x_1 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i$ и $x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ \ gamma x_i$, где $\ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0$ и $\ displaystyle \ sum \ limit_ {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 \ limit_ {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 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i \ theta x_i + \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_i \ слева (1- \ theta \ right) x_i$

$\ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ правильно] x_i$

Учитывая коэффициенты,

$\ displaystyle \ sum \ limit_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ right] = \ theta \ displaystyle \ sum \ limit_ {i = 1 } ^ n \ lambda_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limit_ {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)$

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