Optymalizacja wypukła - kadłub

Wypukły kadłub zbioru punktów w S jest granicą najmniejszego obszaru wypukłego, który zawiera wszystkie punkty S wewnątrz niego lub na jego granicy.

LUB

Niech $ S \ subseteq \ mathbb {R} ^ n $ Wypukły kadłub S, oznaczony $ Co \ left (S \ right) $ by jest zbiorem wszystkich wypukłych kombinacji S, tj. $ X \ in Co \ left (S \ dobrze) $ wtedy i tylko wtedy, gdy $ x \ w \ Displaystyle \ sum \ limity_ {i = 1} ^ n \ lambda_ix_i $, gdzie $ \ displaystyle \ sum \ limit_ {1} ^ n \ lambda_i = 1 $ i $ \ lambda_i \ geq 0 \ forall x_i \ in S $

Remark - Zbiera kadłub ze zbioru punktów w S na płaszczyźnie definiuje wypukły wielokąt, a punkty S na granicy wielokąta definiują wierzchołki wielokąta.

Theorem $ Co \ lewo (S \ prawo) = \ lewo \ {x: x = \ Displaystyle \ suma \ limit_ {i = 1} ^ n \ lambda_ix_i, x_i \ w S \ Displaystyle \ suma \ limity_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 \ right \} $ Pokaż, że wypukła łuska jest zbiorem wypukłym.

Dowód

Niech $ x_1, x_2 \ w Co \ lewo (S \ w prawo) $, a następnie $ x_1 = \ Displaystyle \ suma \ limit_ {i = 1} ^ n \ lambda_ix_i $ i $ x_2 = \ Displaystyle \ suma \ limity_ {i = 1} ^ n \ lambda_ \ gamma x_i $ gdzie $ \ Displaystyle \ suma \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ i $ \ Displaystyle \ suma \ limit_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Dla $ \ theta \ in \ lewo (0,1 \ prawej), \ theta x_1 + \ lewo (1- \ teta \ prawej) x_2 = \ teta \ Displaystyle \ suma \ limity_ {i = 1} ^ n \ lambda_ix_i + \ lewo (1- \ theta \ dobrze) \ Displaystyle \ sum \ limity_ {i = 1} ^ n \ gamma_ix_i $

$ \ theta x_1 + \ lewo (1- \ teta \ prawej) x_2 = \ Displaystyle \ sum \ limity_ {i = 1} ^ n \ lambda_i \ teta x_i + \ Displaystyle \ suma \ limity_ {i = 1} ^ n \ gamma_i \ left (1- \ theta \ right) x_i $

$ \ theta x_1 + \ lewo (1- \ teta \ prawej) x_2 = \ Displaystyle \ suma \ limit_ {i = 1} ^ n \ lewo [\ lambda_i \ teta + \ gamma_i \ lewo (1- \ theta \ prawej) \ po prawej] x_i $

Biorąc pod uwagę współczynniki,

$ \ Displaystyle \ suma \ limity_ {i = 1} ^ n \ lewo [\ lambda_i \ teta + \ gamma_i \ lewo (1- \ theta \ prawej) \ prawej] = \ theta \ displaystyle \ sum \ limity_ {i = 1 } ^ n \ lambda_i + \ lewo (1- \ theta \ prawej) \ Displaystyle \ suma \ limit_ {i = 1} ^ n \ gamma_i = \ theta + \ lewo (1- \ theta \ prawej) = 1 $

Stąd $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Zatem wypukły kadłub jest zbiorem wypukłym.