Otimização convexa - problema de programação
Existem quatro tipos de problemas de programação convexa -
Step 1 - $ min \: f \ left (x \ right) $, onde $ x \ em S $ e S é um conjunto convexo não vazio definido em $ \ mathbb {R} ^ n $ e $ f \ left (x \ right ) $ é uma função convexa.
Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ sujeito a
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ e $ g_i \ left (x \ right) $ é uma função convexa.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ e $ g_i \ left (x \ right) $ é uma função côncava.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ e $ g_i \ left (x \ right) $ é uma função linear.
onde $ f \ left (x \ right) $ é uma função convexa.
Step 3 - $ max \: f \ left (x \ right) $ onde $ x \ in S $ e S é um conjunto convexo não vazio definido em $ \ mathbb {R} ^ n $ e $ f \ left (x \ right) $ é uma função côncava.
Step 4 - $ min \: f \ left (x \ right) $, onde $ x \ in \ mathbb {R} ^ n $ sujeito a
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ e $ g_i \ left (x \ right) $ é uma função convexa.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ e $ g_i \ left (x \ right) $ é uma função côncava.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ e $ g_i \ left (x \ right) $ é uma função linear.
onde $ f \ left (x \ right) $ é uma função côncava.
Cone de direção viável
Seja S um conjunto não vazio em $ \ mathbb {R} ^ n $ e seja $ \ hat {x} \ in \: Closure \ left (S \ right) $, então o cone de direção viável de S em $ \ hat {x} $, denotado por D, é definido como $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
Cada vetor diferente de zero $ d \ em D $ é chamado de direção viável.
Para uma dada função $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ o cone de direção de melhoria em $ \ hat {x} $ é denotado por F e é 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 direção $ d \ em F $ é chamada de direção de melhoria ou direção descendente de f em $ \ hat {x} $
Teorema
Necessary Condition
Considere o problema $ min f \ left (x \ right) $ tal que $ x \ in S $ onde S é um conjunto não vazio em $ \ mathbb {R} ^ n $. Suponha que f seja diferenciável em um ponto $ \ hat {x} \ in S $. Se $ \ hat {x} $ é uma solução ótima local, então $ F_0 \ cap D = \ phi $ onde $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ e D é um cone de direção viável.
Sufficient Condition
Se $ F_0 \ cap D = \ phi $ f é uma função pseudoconvex em $ \ hat {x} $ e existe uma vizinhança de $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varejpsilon> 0 $ tal que $ d = x- \ hat {x} \ in D $ para qualquer $ x \ in S \ cap N_ \ varejpsilon \ left (\ hat {x} \ right) $, então $ \ hat {x} $ é a solução ótima local.
Prova
Necessary Condition
Seja $ F_0 \ cap D \ neq \ phi $, ou seja, existe um $ d \ em F_0 \ cap D $ tal que $ d \ em F_0 $ e $ d \ em D $
Como $ d \ em D $, portanto existe $ \ delta_1> 0 $ tal que $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $
Como $ d \ in F_0 $, portanto $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Assim, 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) $
Deixe $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
Então $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ em f \ left (0, \ delta \ right) $
Mas $ \ hat {x} $ é a solução ótima local.
Portanto, é uma contradição.
Assim, $ F_0 \ cap D = \ phi $
Sufficient Condition
Seja $ F_0 \ cap D \ neq \ phi $ nd seja f uma função pseudoconvexa.
Deixe existir uma vizinhança de $ \ hat {x}, N _ {\ varejpsilon} \ left (\ hat {x} \ right) $ tal que $ d = x- \ hat {x}, \ forall x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $
Seja $ \ hat {x} $ não uma solução ótima local.
Assim, existe $ \ bar {x} \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ tal que $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $
Por suposição em $ 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 $
$ \ Rightarrow d \ in F_0 $
portanto $ F_0 \ cap D \ neq \ phi $
o que é uma contradição.
Portanto, $ \ hat {x} $ é a solução ótima local.
Considere o seguinte problema: $ min \: f \ left (x \ right) $ onde $ x \ em 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 $ e X é um conjunto aberto em $ \ mathbb {R} ^ n $
Seja $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
Seja $ \ hat {x} \ in X $, então $ M = \ left \ {1,2, ..., m \ right \} $
Seja $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $ onde I é chamado de conjunto de índice para todas as restrições ativas em $ \ hat {x } $
Seja $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $ onde J é chamado de conjunto de índices para todas as restrições ativas em $ \ hat {x } $.
Seja $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
Seja $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
ou $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Lema
Se $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ e X não está vazio aberto definido em $ \ mathbb {R } ^ n $. Seja $ \ hat {x} \ in S $ e $ g_i $ sejam diferentes em $ \ hat {x}, i \ in I $ e seja $ g_i $ onde $ i \ in J $ são contínuos em $ \ hat {x } $, então $ G_0 \ subseteq D $.
Prova
Seja $ d \ em G_0 $
Dado que $ \ hat {x} \ in X $ e X é um conjunto aberto, existe $ \ delta_1> 0 $ tal que $ \ hat {x} + \ lambda d \ in X $ para $ \ lambda \ in \ esquerda (0, \ delta_1 \ direita) $
Além disso, como $ g_ \ hat {x} <0 $ e $ g_i $ são contínuos em $ \ hat {x}, \ forall i \ em J $, existe $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
Como $ d \ em G_0 $, portanto, $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ portanto 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 $
Deixe $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
portanto, $ \ 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 $
$ \ Rightarrow d \ in D $
$ \ Rightarrow G_0 \ subseteq D $
Daí provado.
Teorema
Necessary Condition
Sejam $ f $ e $ g_i, i \ in I $, diferentes em $ \ hat {x} \ in S, $ e $ g_j $ são contínuos em $ \ hat {x} \ in S $. Se $ \ hat {x} $ são mínimos locais de $ S $, então $ F_0 \ cap G_0 = \ phi $.
Sufficient Condition
Se $ F_0 \ cap G_0 = \ phi $ e f é uma função pseudoconvexa em $ \ left (\ hat {x}, g_i 9x \ right), i \ in I $ são estritamente funções pseudoconvexas sobre alguns $ \ varepsilon $ - vizinhança de $ \ hat {x}, \ hat {x} $ é uma solução ótima local.
Observações
Seja $ \ hat {x} $ um ponto viável tal que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, então $ F_0 = \ phi $. Assim, $ F_0 \ cap G_0 = \ phi $ mas $ \ hat {x} $ não é uma solução ótima
Mas se $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, então $ G_0 = \ phi $, portanto $ F_0 \ cap G_0 = \ phi $
Considere o problema: min $ f \ left (x \ right) $ tal que $ g \ left (x \ right) = 0 $.
Como $ g \ left (x \ right) = 0 $, então $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ e $ g_2 \ left (x \ right) = - g \ esquerda (x \ direita) \ leq 0 $.
Seja $ \ hat {x} \ em S $, então $ g_1 \ left (\ hat {x} \ right) = 0 $ e $ g_2 \ left (\ hat {x} \ right) = 0 $.
Mas $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Assim, $ G_0 = \ phi $ e $ F_0 \ cap G_0 = \ phi $.