Optimización convexa: conjunto convexo
Sea $ S \ subseteq \ mathbb {R} ^ n $ Se dice que un conjunto S es convexo si el segmento de línea que une dos puntos cualesquiera del conjunto S también pertenece al S, es decir, si $ x_1, x_2 \ in S $ , luego $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ donde $ \ lambda \ in \ left (0,1 \ right) $.
Note -
- La unión de dos conjuntos convexos puede ser convexa o no.
- La intersección de dos conjuntos convexos es siempre convexa.
Proof
Sean $ S_1 $ y $ S_2 $ dos conjuntos convexos.
Sea $ S_3 = S_1 \ cap S_2 $
Sea $ x_1, x_2 \ en S_3 $
Dado que $ S_3 = S_1 \ cap S_2 $ entonces $ x_1, x_2 \ en S_1 $ y $ x_1, x_2 \ en S_2 $
Como $ S_i $ es un conjunto convexo, $ \ forall $ $ i \ in 1,2, $
Por tanto $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ donde $ \ lambda \ in \ left (0,1 \ right) $
Por lo tanto, $ \ 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 $
Por tanto, $ S_3 $ es un conjunto convexo.
Promedio ponderado de la forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, donde $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ y $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ se llama combinación cónica de $ x_1, x_2, .... x_k. $
Promedio ponderado de la forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, donde $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ se llama combinación afín de $ x_1 , x_2, .... x_k. $
El promedio ponderado de la forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ se llama combinación lineal de $ x_1, x_2, .... x_k. $
Ejemplos
Step 1 - Demuestre que el conjunto $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ es un conjunto convexo.
Solución
Deje $ x_1 $ y $ x_2 \ en S $
$ \ Rightarrow Cx_1 \ leq \ alpha $ y $ \: y \: Cx_2 \ leq \ alpha $
Para mostrar: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ derecha) $
$ Cy = C \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = \ lambda Cx_1 + \ left (1- \ lambda \ right) Cx_2 $
$ \ Flecha derecha Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $
$ \ Flecha derecha Cy \ leq \ alpha $
$ \ Flecha derecha y \ en S $
Por tanto, $ S $ es un conjunto convexo.
Step 2 - Demuestra que el conjunto $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ es un convexo conjunto.
Solución
Sea $ x, y \ en S $
Sea $ x = \ left (x_1, x_2 \ right) $ y $ y = \ left (y_1, y_2 \ right) $
$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ y $ y_ {1} ^ {2} \ leq 8y_2 $
Para mostrar - $ \ 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] $
$ Ahora, \ 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 $
Pero $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $
Por lo tanto,
$ \ 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] PS
$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ in S $
Step 3 - Demuestre que un conjunto $ S \ in \ mathbb {R} ^ n $ es convexo si y solo si para cada entero k, cada combinación convexa de cualesquiera k puntos de $ S $ está en $ S $.
Solución
Sea $ S $ un conjunto convexo. luego, mostrar;
$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ en S, \ Displaystyle \ sum \ limits_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ...., k PS
Prueba por inducción
Para $ k = 1, x_1 \ en S, c_1 = 1 \ Flecha derecha c_1x_1 \ en S $
Para $ k = 2, x_1, x_2 \ en S, c_1 + c_2 = 1 $ y Dado que S es un conjunto convexo
$ \ Flecha derecha c_1x_1 + c_2x_2 \ en S. $
Sea la combinación convexa de m puntos de S en S, es decir,
$ c_1x_1 + c_2x_2 + ... + c_mx_m \ en S, \ Displaystyle \ sum \ limits_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ..., m $
Ahora, supongamos que $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $
Sea $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $
Sea $ 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} $
Sea $ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $
$ \ Rightarrow x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) y + \ mu_ {m + 1} x_ {m + 1} $
Ahora $ y \ en S $ porque la suma de los coeficientes es 1.
$ \ Rightarrow x \ in S $ ya que S es un conjunto convexo y $ y, x_ {m + 1} \ in S $
Por lo tanto probado por inducción.