Ottimizzazione convessa - Funzione differenziabile
Sia S un insieme aperto non vuoto in $ \ mathbb {R} ^ n $, allora $ f: S \ rightarrow \ mathbb {R} $ si dice differenziabile in $ \ hat {x} \ in S $ se esiste un vettore $ \ bigtriangledown f \ left (\ hat {x} \ right) $ chiamato vettore gradiente e una funzione $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tale che
$ f \ sinistra (x \ destra) = f \ sinistra (\ hat {x} \ destra) + \ bigtriangledown f \ sinistra (\ hat {x} \ destra) ^ T \ sinistra (x- \ hat {x} \ destra) + \ sinistra \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ in S $ dove
$ \ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ partial f} {\ partial x_1} \ frac {\ partial f} {\ partial x_2} ... \ frac {\ partial f} {\ partial x_n} \ right] _ {x = \ hat {x}} ^ {T} $
Teorema
sia S un convesso non vuoto, aperto in $ \ mathbb {R} ^ n $ e $ f: S \ rightarrow \ mathbb {R} $ sia differenziabile su S. Allora, f è convesso se e solo se per $ x_1, x_2 \ in S, \ bigtriangledown f \ sinistra (x_2 \ destra) ^ T \ sinistra (x_1-x_2 \ destra) \ leq f \ sinistra (x_1 \ destra) -f \ sinistra (x_2 \ destra) $
Prova
Sia f una funzione convessa. cioè, per $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $
$ f \ sinistra [\ lambda x_1 + \ sinistra (1- \ lambda \ destra) x_2 \ destra] \ leq \ lambda f \ sinistra (x_1 \ destra) + \ sinistra (1- \ lambda \ destra) f \ sinistra (x_2 \ destra) $
$ \ Freccia destra f \ sinistra [\ lambda x_1 + \ sinistra (1- \ lambda \ destra) x_2 \ destra] \ leq \ lambda \ sinistra (f \ sinistra (x_1 \ destra) -f \ sinistra (x_2 \ destra) \ destra ) + f \ sinistra (x_2 \ destra) $
$ \ Freccia destra \ lambda \ sinistra (f \ sinistra (x_1 \ destra) -f \ sinistra (x_2 \ destra) \ destra) \ geq f \ sinistra (x_2 + \ lambda \ sinistra (x_1-x_2 \ destra) \ destra) - f \ sinistra (x_2 \ destra) $
$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 \ right) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ sinistra (x_1-x_2 \ destra) \ lambda + $
$ \ sinistra \ | \ lambda \ sinistra (x_1-x_2 \ destra) \ destra \ | \ alpha \ sinistra (x_2, \ lambda \ sinistra (x_1 - x_2 \ destra) -f \ sinistra (x_2 \ destra) \ destra) $
dove $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ come $ \ lambda \ rightarrow 0 $
Dividendo per $ \ lambda $ su entrambi i lati, otteniamo -
$ f \ sinistra (x_1 \ destra) -f \ sinistra (x_2 \ destra) \ geq \ bigtriangledown f \ sinistra (x_2 \ destra) ^ T \ sinistra (x_1-x_2 \ destra) $
conversare
Lascia per $ x_1, x_2 \ in S, \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $
Per mostrare che f è convesso.
Poiché S è convesso, $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $
Poiché $ x_1, x_3 \ in S $, quindi
$ f \ sinistra (x_1 \ destra) -f \ sinistra (x_3 \ destra) \ geq \ bigtriangledown f \ sinistra (x_3 \ destra) ^ T \ sinistra (x_1 -x_3 \ destra) $
$ \ Freccia destra f \ sinistra (x_1 \ destra) -f \ sinistra (x_3 \ destra) \ geq \ bigtriangledown f \ sinistra (x_3 \ destra) ^ T \ sinistra (x_1 - \ lambda x_1- \ sinistra (1- \ lambda \ destra) x_2 \ destra) $
$ \ Freccia destra f \ sinistra (x_1 \ destra) -f \ sinistra (x_3 \ destra) \ geq \ sinistra (1- \ lambda \ destra) \ bigtriangledown f \ sinistra (x_3 \ destra) ^ T \ sinistra (x_1 - x_2 \ destra) $
Poiché, quindi $ x_2, x_3 \ in S $
$ f \ sinistra (x_2 \ destra) -f \ sinistra (x_3 \ destra) \ geq \ bigtriangledown f \ sinistra (x_3 \ destra) ^ T \ sinistra (x_2-x_3 \ destra) $
$ \ Freccia destra f \ sinistra (x_2 \ destra) -f \ sinistra (x_3 \ destra) \ geq \ bigtriangledown f \ sinistra (x_3 \ destra) ^ T \ sinistra (x_2- \ lambda x_1- \ sinistra (1- \ lambda \ destra) x_2 \ destra) $
$ \ Freccia destra f \ sinistra (x_2 \ destra) -f \ sinistra (x_3 \ destra) \ geq \ sinistra (- \ lambda \ destra) \ bigtriangledown f \ sinistra (x_3 \ destra) ^ T \ sinistra (x_1-x_2 \ a destra) $
Quindi, combinando le equazioni di cui sopra, otteniamo:
$ \ lambda \ sinistra (f \ sinistra (x_1 \ destra) -f \ sinistra (x_3 \ destra) \ destra) + \ sinistra (1- \ lambda \ destra) \ sinistra (f \ sinistra (x_2 \ destra) -f \ sinistra (x_3 \ destra) \ destra) \ geq 0 $
$ \ Freccia destra f \ sinistra (x_3 \ destra) \ leq \ lambda f \ sinistra (x_1 \ destra) + \ sinistra (1- \ lambda \ destra) f \ sinistra (x_2 \ destra) $
Teorema
sia S un insieme convesso aperto non vuoto in $ \ mathbb {R} ^ n $ e $ f: S \ rightarrow \ mathbb {R} $ sia differenziabile su S, allora f è convesso su S se e solo se per qualsiasi $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $
Prova
sia f una funzione convessa, quindi usando il teorema precedente -
$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $ e
$ \ bigtriangledown f \ sinistra (x_1 \ destra) ^ T \ sinistra (x_2-x_1 \ destra) \ leq f \ sinistra (x_2 \ destra) -f \ sinistra (x_1 \ destra) $
Aggiungendo le due equazioni precedenti, otteniamo:
$ \ bigtriangledown f \ sinistra (x_2 \ destra) ^ T \ sinistra (x_1-x_2 \ destra) + \ bigtriangledown f \ sinistra (x_1 \ destra) ^ T \ sinistra (x_2-x_1 \ destra) \ leq 0 $
$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $
$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $
conversare
Lascia per qualsiasi $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $
Per mostrare che f è convesso.
Siano $ x_1, x_2 \ in S $, quindi per teorema del valore medio, $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ right), x \ in \ left (x_1-x_2 \ right) \ Rightarrow x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ perché S è un insieme convesso.
$ \ Freccia destra f \ sinistra (x_1 \ destra) - f \ sinistra (x_2 \ destra) = \ sinistra (\ bigtriangledown f \ sinistra (x \ destra) ^ T \ destra) \ sinistra (x_1-x_2 \ destra) $
per $ x, x_1 $, sappiamo -
$ \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x-x_1 \ right) \ geq 0 $
$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2- x_1 \ destra) \ geq 0 $
$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (1- \ lambda \ right) \ left (x_2-x_1 \ right ) \ geq 0 $
$ \ Rightarrow \ bigtriangledown f \ left (x \ right) ^ T \ left (x_2-x_1 \ right) \ geq \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) $
Combinando le equazioni di cui sopra, otteniamo -
$ \ Rightarrow \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $
Quindi usando l'ultimo teorema, f è una funzione convessa.
Funzione due volte differenziabili
Sia S un sottoinsieme non vuoto di $ \ mathbb {R} ^ n $ e $ f: S \ rightarrow \ mathbb {R} $ allora f si dice differenziabile due volte in $ \ bar {x} \ in S $ se esiste un vettore $ \ bigtriangledown f \ left (\ bar {x} \ right), una \: nXn $ matrice $ H \ left (x \ right) $ (chiamata matrice hessiana) e una funzione $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tale che $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ sinistra (\ bar {x} \ destra) + \ bigtriangledown f \ sinistra (\ bar {x} \ destra) ^ T \ sinistra (x- \ bar {x} \ destra) + \ frac {1} {2} \ sinistra (x- \ bar {x} \ destra) H \ sinistra (\ bar {x} \ destra) \ sinistra (x- \ bar {x} \ destra) $
dove $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $