Ottimizzazione convessa - Scafo

Lo scafo convesso di un insieme di punti in S è il confine della più piccola regione convessa che contiene tutti i punti di S al suo interno o sul suo confine.

O

Sia $ S \ subseteq \ mathbb {R} ^ n $ Lo scafo convesso di S, indicato con $ Co \ left (S \ right) $ by è la raccolta di tutte le combinazioni convesse di S, cioè $ x \ in Co \ left (S \ right) $ se e solo se $ x \ in \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $, dove $ \ displaystyle \ sum \ limits_ {1} ^ n \ lambda_i = 1 $ e $ \ lambda_i \ geq 0 \ forall x_i \ in S $

Remark - Conve lo scafo di un insieme di punti in S nel piano definisce un poligono convesso e i punti di S sul confine del poligono definisce i vertici del poligono.

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 \} $ Mostra che uno scafo convesso è un insieme convesso.

Prova

Siano $ x_1, x_2 \ in Co \ left (S \ right) $, quindi $ x_1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $ e $ x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ \ gamma x_i $ dove $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ e $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Per $ \ 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 \ sinistra (1- \ theta \ destra) 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) \ destra] x_i $

Considerando i coefficienti,

$ \ 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 $

Quindi, $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Quindi, uno scafo convesso è un insieme convesso.