Condições suficientes e necessárias para Global Optima
Teorema
Seja f função duas vezes diferenciável. Se $ \ bar {x} $ é um mínimo local, então $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ e a matriz Hessiana $ H \ left (\ bar {x} \ right) $ é um semidefinido positivo.
Prova
Seja $ d \ in \ mathbb {R} ^ n $. Como f é duas vezes diferenciável em $ \ bar {x} $.
Portanto,
$ f \ left (\ bar {x} + \ lambda d \ right) = f \ left (\ bar {x} \ right) + \ lambda \ bigtriangledown f \ left (\ bar {x} \ right) ^ T d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d + $
$ \ lambda ^ 2 \ left \ | d \ right \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ right) $
Mas $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ e $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $
$ \ Rightarrow f \ left (\ bar {x} + \ lambda d \ right) -f \ left (\ bar {x} \ right) = \ lambda ^ 2d ^ TH \ left (\ bar {x} \ right) d $
Como $ \ bar {x} $ é um mínimo local, existe um $ \ delta> 0 $ tal que $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right ), \ forall \ lambda \ in \ left (0, \ delta \ right) $
Teorema
Seja $ f: S \ rightarrow \ mathbb {R} ^ n $ onde $ S \ subset \ mathbb {R} ^ n $ seja duas vezes diferenciável em S. Se $ \ bigtriangledown f \ left (x \ right) = 0 $ e $ H \ left (\ bar {x} \ right) $ é semi-definido positivo, para todos $ x \ em S $, então $ \ bar {x} $ é uma solução ótima global.
Prova
Como $ H \ left (\ bar {x} \ right) $ é semidefinido positivo, f é uma função convexa sobre S. Já que f é diferenciável e convexa em $ \ bar {x} $
$ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ leq f \ left (x \ right) -f \ left (\ bar {x} \ right), \ forall x \ in S $
Como $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0, f \ left (x \ right) \ geq f \ left (\ bar {x} \ right) $
Portanto, $ \ bar {x} $ é um ótimo global.
Teorema
Suponha que $ \ bar {x} \ in S $ seja uma solução ótima local para o problema $ f: S \ rightarrow \ mathbb {R} $ onde S é um subconjunto não vazio de $ \ mathbb {R} ^ n $ e S é convexo. $ min \: f \ left (x \ right) $ onde $ x \ em S $.
Então:
$ \ bar {x} $ é uma solução ótima global.
Se $ \ bar {x} $ é estritamente mínimo local ou f é função estritamente convexa, então $ \ bar {x} $ é a solução ótima global única e também é mínimo local forte.
Prova
Seja $ \ bar {x} $ outra solução ótima global para o problema de forma que $ x \ neq \ bar {x} $ e $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right) $
Como $ \ hat {x}, \ bar {x} \ em S $ e S é convexo, então $ \ frac {\ hat {x} + \ bar {x}} {2} \ em S $ e f é estritamente convexo.
$ \ Rightarrow f \ left (\ frac {\ hat {x} + \ bar {x}} {2} \ right) <\ frac {1} {2} f \ left (\ bar {x} \ right) + \ frac {1} {2} f \ left (\ hat {x} \ right) = f \ left (\ hat {x} \ right) $
Isso é contradição.
Portanto, $ \ hat {x} $ é uma solução ótima global única.
Corolário
Seja $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ uma função convexa diferenciável onde $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ é um conjunto convexo. Considere o problema $ min f \ left (x \ right), x \ in S $, então $ \ bar {x} $ é uma solução ótima se $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $
Prova
Seja $ \ bar {x} $ uma solução ótima, ou seja, $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S $
$ \ Rightarrow f \ left (x \ right) = f \ left (\ bar {x} \ right) \ geq 0 $
$ f \ left (x \ right) = f \ left (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ direita) + \ esquerda \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $
onde $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0 $ as $ x \ rightarrow \ bar {x} $
$ \ Rightarrow f \ left (x \ right) -f \ left (\ bar {x} \ right) = \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x } \ right) \ geq 0 $
Corolário
Seja f uma função convexa diferenciável em $ \ bar {x} $, então $ \ bar {x} $ é o mínimo global iff $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $
Exemplos
$ f \ left (x \ right) = \ left (x ^ 2-1 \ right) ^ {3}, x \ in \ mathbb {R} $.
$ \ bigtriangledown f \ left (x \ right) = 0 \ Rightarrow x = -1,0,1 $.
$ \ bigtriangledown ^ 2f \ left (\ pm 1 \ right) = 0, \ bigtriangledown ^ 2 f \ left (0 \ right) = 6> 0 $.
$ f \ left (\ pm 1 \ right) = 0, f \ left (0 \ right) = - 1 $
Portanto, $ f \ left (x \ right) \ geq -1 = f \ left (0 \ right) \ Rightarrow f \ left (0 \ right) \ leq f \ left (x \ right) \ forall x \ in \ mathbb {R} $
$ f \ left (x \ right) = x \ log x $ definido em $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.
$ {f} 'x = 1 + \ log x $
$ {f} '' x = \ frac {1} {x}> 0 $
Portanto, essa função é estritamente convexa.
$ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ é estritamente convexo.