Optimisation convexe - coque

L'enveloppe convexe d'un ensemble de points dans S est la limite de la plus petite région convexe qui contient tous les points de S à l'intérieur ou sur sa frontière.

OU

Soit $ S \ subseteq \ mathbb {R} ^ n $ L'enveloppe convexe de S, notée $ Co \ left (S \ right) $ by est la collection de toutes les combinaisons convexes de S, c'est-à-dire $ x \ dans Co \ left (S \ right) $ si et seulement si $ x \ in \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $, où $ \ displaystyle \ sum \ limits_ {1} ^ n \ lambda_i = 1 $ et $ \ lambda_i \ geq 0 \ forall x_i \ en S $

Remark - La coque conve d'un ensemble de points en S dans le plan définit un polygone convexe et les points de S sur la frontière du polygone définissent les sommets du polygone.

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 \} $ Montrer qu'une coque convexe est un ensemble convexe.

Preuve

Soit $ x_1, x_2 \ in Co \ left (S \ right) $, puis $ x_1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $ et $ x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ \ gamma x_i $ où $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ et $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Pour $ \ 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 \ gauche (1- \ theta \ droite) 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) \ droite] x_i $

Compte tenu des coefficients,

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

Par conséquent, $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Ainsi, une coque convexe est un ensemble convexe.