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.