Optimisation convexe - Ensemble convexe

Soit $ S \ subseteq \ mathbb {R} ^ n $ Un ensemble S est dit convexe si le segment de droite joignant deux points quelconques de l'ensemble S appartient aussi au S, c'est-à-dire si $ x_1, x_2 \ dans S $ , puis $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ où $ \ lambda \ in \ left (0,1 \ right) $.

Note -

L'union de deux ensembles convexes peut être convexe ou non.
L'intersection de deux ensembles convexes est toujours convexe.

Proof

Soit $ S_1 $ et $ S_2 $ deux ensembles convexes.

Soit $ S_3 = S_1 \ cap S_2 $

Soit $ x_1, x_2 \ dans S_3 $

Puisque $ S_3 = S_1 \ cap S_2 $ donc $ x_1, x_2 \ dans S_1 $ et $ x_1, x_2 \ dans S_2 $

Puisque $ S_i $ est un ensemble convexe, $ \ forall $ $ i \ en 1,2, $

Ainsi $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ où $ \ lambda \ in \ left (0,1 \ right) $

Donc, $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_1 \ cap S_2 $

$ \ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_3 $

Par conséquent, $ S_3 $ est un ensemble convexe.

Moyenne pondérée de la forme $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, où $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ et $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ est appelée combinaison conique de $ x_1, x_2, .... x_k. $
Moyenne pondérée de la forme $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, où $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ est appelée combinaison affine de $ x_1 , x_2, .... x_k. $
La moyenne pondérée de la forme $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ est appelée combinaison linéaire de $ x_1, x_2, .... x_k. $

Exemples

Step 1 - Montrer que l'ensemble $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ est un ensemble convexe.

Solution

Soit $ x_1 $ et $ x_2 \ dans S $

$ \ Rightarrow Cx_1 \ leq \ alpha $ et $ \: et \: Cx_2 \ leq \ alpha $

Pour afficher: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ droite) $

$ Cy = C \ gauche (\ lambda x_1 + \ gauche (1- \ lambda \ droite) x_2 \ droite) = \ lambda Cx_1 + \ gauche (1- \ lambda \ droite) Cx_2 $

$ \ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $

$ \ Rightarrow Cy \ leq \ alpha $

$ \ Rightarrow y \ en S $

Par conséquent, $ S $ est un ensemble convexe.

Step 2 - Montrer que l'ensemble $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ est un convexe ensemble.

Solution

Soit $ x, y \ dans S $

Soit $ x = \ left (x_1, x_2 \ right) $ et $ y = \ left (y_1, y_2 \ right) $

$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ et $ y_ {1} ^ {2} \ leq 8y_2 $

Pour afficher - $ \ lambda x + \ left (1- \ lambda \ right) y \ in S \ Rightarrow \ lambda \ left (x_1, x_2 \ right) + \ left (1- \ lambda \ right) \ left (y_1, y_2 \ right) \ in S \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda) y_2] \ in S \ right) \ right] $

$ Maintenant, \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} = \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) x_1y_1 $

Mais $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $

Par conséquent,

$ \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) \ left (x_ {1} ^ {2} + y_ {1} ^ {2} \ right) $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda x_ {1} ^ {2} + \ left (1- \ lambda \ right) y_ {1} ^ {2} $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ lambda x_2 + 8 \ left (1- \ lambda \ right) y_2 $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ left [\ lambda x_2 + \ left (1- \ lambda \ right) y_2 \ right] $

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ in S $

Step 3 - Montrer qu'un ensemble $ S \ in \ mathbb {R} ^ n $ est convexe si et seulement si pour chaque entier k, chaque combinaison convexe de tout k points de $ S $ est dans $ S $.

Solution

Soit $ S $ un ensemble convexe. puis, pour montrer;

$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ in S, \ displaystyle \ sum \ limits_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ...., k $

Preuve par induction

Pour $ k = 1, x_1 \ dans S, c_1 = 1 \ Rightarrow c_1x_1 \ in S $

Pour $ k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1 $ et Puisque S est un ensemble convexe

$ \ Rightarrow c_1x_1 + c_2x_2 \ dans S. $

Soit la combinaison convexe de m points de S dans S ie,

$ c_1x_1 + c_2x_2 + ... + c_mx_m \ in S, \ displaystyle \ sum \ limits_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ..., m $

Maintenant, Soit $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $

Soit $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $

Soit $ x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) \ frac {\ mu_1x_1 + \ mu_2x_2 + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} + \ mu_ {m + 1} x_ {m + 1} $

Soit $ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $

$ \ Flèche droite x = \ gauche (\ mu_1 + \ mu_2 + ... + \ mu_m \ droite) y + \ mu_ {m + 1} x_ {m + 1} $

Maintenant $ y \ dans S $ car la somme des coe ﬀ icients est 1.

$ \ Rightarrow x \ in S $ puisque S est un ensemble convexe et $ y, x_ {m + 1} \ in S $

D'où prouvé par induction.