Ottimizzazione convessa - Set convesso
Sia $ S \ subseteq \ mathbb {R} ^ n $ Un insieme S si dice convesso se il segmento di linea che unisce due punti qualsiasi dell'insieme S appartiene anche a S, cioè se $ x_1, x_2 \ in S $ , quindi $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ dove $ \ lambda \ in \ left (0,1 \ right) $.
Note -
- L'unione di due insiemi convessi può o non può essere convessa.
- L'intersezione di due insiemi convessi è sempre convessa.
Proof
Siano $ S_1 $ e $ S_2 $ due insiemi convessi.
Sia $ S_3 = S_1 \ cap S_2 $
Siano $ x_1, x_2 \ in S_3 $
Poiché $ S_3 = S_1 \ cap S_2 $ quindi $ x_1, x_2 \ in S_1 $ e $ x_1, x_2 \ in S_2 $
Poiché $ S_i $ è un insieme convesso, $ \ forall $ $ i \ in 1,2, $
Quindi $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ dove $ \ lambda \ in \ left (0,1 \ right) $
Quindi, $ \ 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 $
Quindi, $ S_3 $ è un insieme convesso.
Media ponderata della forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, dove $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ e $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ è chiamata combinazione conica di $ x_1, x_2, .... x_k. $
Media ponderata della forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, dove $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ è chiamata combinazione affine di $ x_1 , x_2, .... x_k. $
La media ponderata della forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ è chiamata combinazione lineare di $ x_1, x_2, .... x_k. $
Esempi
Step 1 - Dimostra che l'insieme $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ è un insieme convesso.
Soluzione
Siano $ x_1 $ e $ x_2 \ in S $
$ \ Rightarrow Cx_1 \ leq \ alpha $ e $ \: e \: Cx_2 \ leq \ alpha $
Per mostrare: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ a destra) $
$ Cy = C \ sinistra (\ lambda x_1 + \ sinistra (1- \ lambda \ destra) x_2 \ destra) = \ lambda Cx_1 + \ sinistra (1- \ lambda \ destra) Cx_2 $
$ \ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $
$ \ Freccia destra Cy \ leq \ alpha $
$ \ Freccia destra y \ in S $
Pertanto, $ S $ è un insieme convesso.
Step 2 - Dimostra che l'insieme $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ è convesso impostato.
Soluzione
Siano $ x, y \ in S $
Siano $ x = \ left (x_1, x_2 \ right) $ e $ y = \ left (y_1, y_2 \ right) $
$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ e $ y_ {1} ^ {2} \ leq 8y_2 $
Per mostrare - $ \ 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 \ destra) \ in S \ Freccia destra \ sinistra [\ lambda x_1 + \ sinistra (1- \ lambda) y_2] \ in S \ destra) \ destra] $
$ Ora, \ 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 $
Ma $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $
Perciò,
$ \ 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) $
$ \ Freccia destra \ sinistra [\ lambda x_1 + \ sinistra (1- \ lambda \ destra) y_1 \ destra] ^ {2} \ leq \ lambda x_ {1} ^ {2} + \ sinistra (1- \ lambda \ destra) y_ {1} ^ {2} $
$ \ Freccia destra \ sinistra [\ lambda x_1 + \ sinistra (1- \ lambda \ destra) y_1 \ destra] ^ {2} \ leq 8 \ lambda x_2 + 8 \ sinistra (1- \ lambda \ destra) 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 - Mostra che un insieme $ S \ in \ mathbb {R} ^ n $ è convesso se e solo se per ogni intero k, ogni combinazione convessa di qualsiasi k punti di $ S $ è in $ S $.
Soluzione
Sia $ S $ un insieme convesso. poi, per mostrare;
$ 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 $
Prova per induzione
Per $ k = 1, x_1 \ in S, c_1 = 1 \ Freccia destra c_1x_1 \ in S $
Per $ k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1 $ e Poiché S è un insieme convesso
$ \ Freccia destra c_1x_1 + c_2x_2 \ in S. $
Lascia che la combinazione convessa di m punti di S sia in S cioè,
$ 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 $
Ora, Sia $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $
Sia $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $
Sia $ 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} $
Sia $ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $
$ \ Freccia destra x = \ sinistra (\ mu_1 + \ mu_2 + ... + \ mu_m \ destra) y + \ mu_ {m + 1} x_ {m + 1} $
Ora $ y \ in S $ perché la somma dei coefficienti è 1.
$ \ Freccia destra x \ in S $ poiché S è un insieme convesso e $ y, x_ {m + 1} \ in S $
Quindi dimostrato per induzione.