Optimización convexa: problema de programación

Hay cuatro tipos de problemas de programación convexa:

Step 1 - $ min \: f \ left (x \ right) $, donde $ x \ en S $ y S son un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y $ f \ left (x \ right ) $ es una función convexa.

Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ sujeto a

$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ y $ g_i \ left (x \ right) $ es una función convexa.

$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ y $ g_i \ left (x \ right) $ es una función cóncava.

$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ y $ g_i \ left (x \ right) $ es una función lineal.

donde $ f \ left (x \ right) $ es una función convexa.

Step 3 - $ max \: f \ left (x \ right) $ donde $ x \ en S $ y S son un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y $ f \ left (x \ right) $ es una función cóncava.

Step 4 - $ min \: f \ left (x \ right) $, donde $ x \ in \ mathbb {R} ^ n $ sujeto a

$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ y $ g_i \ left (x \ right) $ es una función convexa.

$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ y $ g_i \ left (x \ right) $ es una función cóncava.

$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ y $ g_i \ left (x \ right) $ es una función lineal.

donde $ f \ left (x \ right) $ es una función cóncava.

Cono de dirección factible

Sea S un conjunto no vacío en $ \ mathbb {R} ^ n $ y sea $ \ hat {x} \ in \: Closure \ left (S \ right) $, luego el cono de dirección factible de S en $ \ hat {x} $, denotado por D, se define como $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $

Cada vector distinto de cero $ d \ en D $ se llama dirección factible.

Para una función dada $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ el cono de dirección mejorada en $ \ hat {x} $ se denota por F y viene dado por

$$ F = \ left \ {d: f \ left (\ hat {x} + \ lambda d \ right) \ leq f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left ( 0, \ delta \ right), \ delta> 0 \ right \} $$

Cada dirección $ d \ en F $ se denomina dirección de mejora o dirección de descenso de f en $ \ hat {x} $

Teorema

Necessary Condition

Considere el problema $ min f \ left (x \ right) $ tal que $ x \ en S $ donde S sea un conjunto no vacío en $ \ mathbb {R} ^ n $. Suponga que f es diferenciable en un punto $ \ hat {x} \ en S $. Si $ \ hat {x} $ es una solución local óptima, entonces $ F_0 \ cap D = \ phi $ donde $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ y D es un cono de dirección factible.

Sufficient Condition

Si $ F_0 \ cap D = \ phi $ f es una función pseudoconvexa en $ \ hat {x} $ y existe una vecindad de $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ tal que $ d = x- \ hat {x} \ in D $ para cualquier $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, luego $ \ hat {x} $ es la solución local óptima.

Prueba

Necessary Condition

Sea $ F_0 \ cap D \ neq \ phi $, es decir, existe un $ d \ en F_0 \ cap D $ tal que $ d \ en F_0 $ y $ d \ en D $

Desde $ d \ en D $, existe $ \ delta_1> 0 $ tal que $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $

Desde $ d \ en F_0 $, por lo tanto $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $

Por lo tanto, existe $ \ delta_2> 0 $ tal que $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right) $

Sea $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $

Entonces $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ en f \ left (0, \ delta \ right) $

Pero $ \ hat {x} $ es la solución local óptima.

De ahí que sea una contradicción.

Entonces $ F_0 \ cap D = \ phi $

Sufficient Condition

Sea $ F_0 \ cap D \ neq \ phi $ nd sea f una función pseudoconvexa.

Supongamos que existe una vecindad de $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ tal que $ d = x- \ hat {x}, \ forall x \ in S \ gorra N_ \ varepsilon \ left (\ hat {x} \ right) $

Sea $ \ hat {x} $ no es una solución óptima local.

Por lo tanto, existe $ \ bar {x} \ en S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ tal que $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $

Suponiendo que $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ in D $

Por pseudoconvexo de f,

$$ f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x} - \ hat {x} \ right) <0 $$

$ \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $

$ \ Flecha derecha d \ en F_0 $

por lo tanto $ F_0 \ cap D \ neq \ phi $

lo cual es una contradicción.

Por tanto, $ \ hat {x} $ es la solución local óptima.

Considere el siguiente problema: $ min \: f \ left (x \ right) $ donde $ x \ in X $ tal que $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $

$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ y X es un conjunto abierto en $ \ mathbb {R} ^ n $

Sea $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $

Sea $ \ hat {x} \ in X $, luego $ M = \ left \ {1,2, ..., m \ right \} $

Deje $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M ​​\ right \} $ donde I se llama índice establecido para todas las restricciones activas en $ \ hat {x PS

Sea $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M ​​\ right \} $ donde J se llama índice establecido para todas las restricciones activas en $ \ hat {x PS

Sea $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $

Sea $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $

o $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $

Lema

Si $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ y X es un conjunto abierto no vacío en $ \ mathbb {R } ^ n $. Sea $ \ hat {x} \ in S $ y $ g_i $ diferentes en $ \ hat {x}, i \ in I $ y dejemos que $ g_i $ donde $ i \ in J $ sean continuos en $ \ hat {x } $, luego $ G_0 \ subseteq D $.

Prueba

Sea $ d \ en G_0 $

Como $ \ hat {x} \ in X $ y X es un conjunto abierto, existe $ \ delta_1> 0 $ tal que $ \ hat {x} + \ lambda d \ in X $ para $ \ lambda \ in \ izquierda (0, \ delta_1 \ derecha) $

Además, dado que $ g_ \ hat {x} <0 $ y $ g_i $ son continuos en $ \ hat {x}, \ forall i \ en J $, existe $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $

Desde $ d \ en G_0 $, por lo tanto, $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ entonces existe $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, para $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J PS

Sea $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $

por lo tanto, $ \ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ in M ​​$

$ \ Rightarrow \ hat {x} + \ lambda d \ in S $

$ \ Flecha derecha d \ en D $

$ \ Rightarrow G_0 \ subseteq D $

Por lo tanto probado.

Teorema

Necessary Condition

Sea $ f $ y $ g_i, i \ en I $, diferentes en $ \ hat {x} \ en S, $ y $ g_j $ son continuos en $ \ hat {x} \ en S $. Si $ \ hat {x} $ es el mínimo local de $ S $, entonces $ F_0 \ cap G_0 = \ phi $.

Sufficient Condition

Si $ F_0 \ cap G_0 = \ phi $ yf es una función pseudoconvexa en $ \ left (\ hat {x}, g_i 9x \ right), i \ en I $ son funciones estrictamente pseudoconvexas sobre algunos $ \ varepsilon $ - vecindario de $ \ hat {x}, \ hat {x} $ es una solución local óptima.

Observaciones

  • Sea $ \ hat {x} $ un punto factible tal que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, luego $ F_0 = \ phi $. Por lo tanto, $ F_0 \ cap G_0 = \ phi $ pero $ \ hat {x} $ no es una solución óptima

  • Pero si $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, entonces $ G_0 = \ phi $, entonces $ F_0 \ cap G_0 = \ phi $

  • Considere el problema: min $ f \ left (x \ right) $ tal que $ g \ left (x \ right) = 0 $.

    Dado que $ g \ left (x \ right) = 0 $, entonces $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ y $ g_2 \ left (x \ right) = - g \ izquierda (x \ derecha) \ leq 0 $.

    Deje que $ \ hat {x} \ in S $, luego $ g_1 \ left (\ hat {x} \ right) = 0 $ y $ g_2 \ left (\ hat {x} \ right) = 0 $.

    Pero $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $

    Por lo tanto, $ G_0 = \ phi $ y $ F_0 \ cap G_0 = \ phi $.