Condizioni sufficienti e necessarie per Global Optima
Teorema
Sia f una funzione differenziabile due volte. Se $ \ bar {x} $ è un minimo locale, allora $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ e la matrice Hessiana $ H \ left (\ bar {x} \ right) $ è un semidefinito positivo.
Prova
Sia $ d \ in \ mathbb {R} ^ n $. Poiché f è differenziabile due volte in $ \ bar {x} $.
Perciò,
$ f \ sinistra (\ bar {x} + \ lambda d \ destra) = f \ sinistra (\ bar {x} \ destra) + \ lambda \ bigtriangledown f \ sinistra (\ bar {x} \ destra) ^ T d + \ lambda ^ 2d ^ TH \ sinistra (\ bar {x} \ destra) d + \ lambda ^ 2d ^ TH \ sinistra (\ bar {x} \ destra) d + $
$ \ lambda ^ 2 \ sinistra \ | d \ right \ | ^ 2 \ beta \ left (\ bar {x}, \ lambda d \ right) $
Ma $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ e $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ come $ \ lambda \ rightarrow 0 $
$ \ Freccia destra f \ sinistra (\ bar {x} + \ lambda d \ destra) -f \ sinistra (\ bar {x} \ destra) = \ lambda ^ 2d ^ TH \ sinistra (\ bar {x} \ destra) d $
Poiché $ \ bar {x} $ è un minimo locale, esiste un $ \ delta> 0 $ tale che $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right ), \ forall \ lambda \ in \ left (0, \ delta \ right) $
Teorema
Sia $ f: S \ rightarrow \ mathbb {R} ^ n $ dove $ S \ subset \ mathbb {R} ^ n $ differenziabile due volte su S. Se $ \ bigtriangledown f \ left (x \ right) = 0 $ e $ H \ left (\ bar {x} \ right) $ è semi-definito positivo, per tutti i $ x \ in S $, allora $ \ bar {x} $ è una soluzione ottimale globale.
Prova
Poiché $ H \ left (\ bar {x} \ right) $ è semidefinito positivo, f è una funzione convessa su S. Poiché f è differenziabile e convessa in $ \ 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 $
Dato che $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0, f \ left (x \ right) \ geq f \ left (\ bar {x} \ right) $
Quindi, $ \ bar {x} $ è un optima globale.
Teorema
Supponiamo che $ \ bar {x} \ in S $ sia una soluzione ottimale locale al problema $ f: S \ rightarrow \ mathbb {R} $ dove S è un sottoinsieme non vuoto di $ \ mathbb {R} ^ n $ e S è convesso. $ min \: f \ sinistra (x \ destra) $ dove $ x \ in S $.
Poi:
$ \ bar {x} $ è una soluzione ottimale globale.
Se $ \ bar {x} $ è un minimo strettamente locale oppure f è una funzione strettamente convessa, allora $ \ bar {x} $ è l'unica soluzione ottimale globale ed è anche un minimo locale forte.
Prova
Sia $ \ bar {x} $ un'altra soluzione ottimale globale al problema tale che $ x \ neq \ bar {x} $ e $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right) $
Poiché $ \ hat {x}, \ bar {x} \ in S $ e S è convesso, allora $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $ ed f è strettamente convesso.
$ \ Freccia destra f \ sinistra (\ 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) $
Questa è una contraddizione.
Quindi, $ \ hat {x} $ è una soluzione ottimale globale unica.
Corollario
Sia $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ una funzione convessa differenziabili dove $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ è un insieme convesso. Considera il problema $ min f \ left (x \ right), x \ in S $, quindi $ \ bar {x} $ è una soluzione ottimale se $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $
Prova
Sia $ \ bar {x} $ una soluzione ottimale, cioè $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S $
$ \ Freccia destra f \ sinistra (x \ destra) = f \ sinistra (\ bar {x} \ destra) \ geq 0 $
$ f \ sinistra (x \ destra) = f \ sinistra (\ bar {x} \ destra) + \ bigtriangledown f \ sinistra (\ bar {x} \ destra) ^ T \ sinistra (x- \ bar {x} \ destra) + \ sinistra \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $
dove $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow 0 $ come $ x \ rightarrow \ bar {x} $
$ \ Freccia destra f \ sinistra (x \ destra) -f \ sinistra (\ bar {x} \ destra) = \ bigtriangledown f \ sinistra (\ bar {x} \ destra) ^ T \ sinistra (x- \ bar {x } \ right) \ geq 0 $
Corollario
Sia f una funzione convessa differenziabile in $ \ bar {x} $, allora $ \ bar {x} $ è il minimo globale se e solo se $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $
Esempi
$ f \ sinistra (x \ destra) = \ sinistra (x ^ 2-1 \ destra) ^ {3}, x \ in \ mathbb {R} $.
$ \ bigtriangledown f \ left (x \ right) = 0 \ Rightarrow x = -1,0,1 $.
$ \ bigtriangledown ^ 2f \ sinistra (\ pm 1 \ destra) = 0, \ bigtriangledown ^ 2 f \ sinistra (0 \ destra) = 6> 0 $.
$ f \ sinistra (\ pm 1 \ destra) = 0, f \ sinistra (0 \ destra) = - 1 $
Quindi, $ f \ sinistra (x \ destra) \ geq -1 = f \ sinistra (0 \ destra) \ Freccia destra f \ sinistra (0 \ destra) \ leq f \ sinistra (x \ destra) \ forall x \ in \ mathbb {R} $
$ f \ left (x \ right) = x \ log x $ definito su $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.
$ {f} 'x = 1 + \ log x $
$ {f} '' x = \ frac {1} {x}> 0 $
Pertanto, questa funzione è strettamente convessa.
$ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ è strettamente convesso.