METODO DEL GRADIENTE1
Il metodo del gradiente (steepest descent “più ripida discesa”) è il più antico, il più noto, uno dei metodi più usati, proposti per la minimizzazione non vincolata di funzioni differenziabili.
Il vettore gradiente f(xk)individua la direzione di più ripida salita della funzione f in x , cioè la k direzione in cui la derivata direzionale è massima. L’idea alla base del metodo del gradiente è di cercare valori di minimo relativo iterativamente, muovendosi ad ogni passo nella direzione opposta a f(xk).
Sia x la soluzione ottenuta alla k-esima iterata, supponendo k f(xk)0, l’iterata successiva è definita da
k k k
k x d
x 1 dove
kk f x
d
è la direzione opposta a quella del gradiente, o antigradiente di f in x . Mi muovo in maniera k opposta (180°) a quella direzione indicata dal gradiente. Il procedimento termina non appena
0 )
(
f xk .
L’algoritmo ora formulato non sembra rivestire particolare interesse poiché risulta molto costoso (ad ogni passo occorre calcolare n derivate direzionali e minimizzare la funzione lungo la direzione individuata). Il metodo diventa efficiente se applicato a problemi quadratici. L’algoritmo della massima discesa si caratterizza come metodo iterativo per la risoluzione anche di sistemi lineari.
1 Metodo della più ripida discesa (steepest descent): è quella direzione che minimizza il prodotto scalare dTf
xk .Si può osservare che la direzione dell’antigradiente (normalizzata) è la direzione che minimizza la derivata direzionale in x tra tutte le direzioni che hanno norma euclidea unitaria (lunghezza 1), k cioè è la soluzione del problema
) ( min
( arg ) (
k T k d
k d f x
x f
x
f
1
2
d 2
Dim.:
utilizziamo le condizioni di ottimalità di Karush-Kuhn-Tucker (i gradienti sono indipendenti) 0
2 )
(
f xk d 3 1
dTd segue
2
) (xk d f
4 2
) ( ) (
2 1 ) ( 2
) 1 (
k T
k
k T
T k
x f x
f
x f x
d f d
2 ) (xk
f
scegliendo 0per un minimo ottengo
2 0 ) 2 (
)
(
f x d
x
f k k
) (
) (
k k
k f x
x d f
4
c.v.d.
2 La norma non è differenziabile, invece lo è la norma al quadrato, useremo 2 1
2
d al posto di 1
2
d .
2
d 2 si può scrivere come dTd.
3 Gradiente della funzione obiettivoper gradiente del vincolo.
4 Sappiamo che cos
) (
)
(
k k
x f
x
f , qual è la direzione che ha il coseno minimo (vicino a 1)?
L’ottimalità locale della direzione f(xk) dipende dalla scelta della norma e che pertanto in un punto fissato x qualsiasi direzione di discesa può interpretarsi come una direzione di discesa più k ripida in una norma opportuna. Se usiamo ad esempio la norma del sup (uniforme o di Chebyshev),
1
è un quadrato, la direzione di discesa più ripida sarà una direzione di discesa che dipende dalla norma utilizzata.
In genere, prendiamo come direzione di discesa più ripida l’antigradiente, perché la norma euclidea è quella più utilizzata.
Nel caso quadratico le curve di livello della funzione f sono ellissoidi concentriche, il gradiente è normale alla retta tangente in x alla curva di livello. k
L’interesse della direzione f(xk) risiede nel fatto che, se il gradiente è continuo essa costituisce una direzione di discesa continua rispetto a x , che si annulla se e solo se x è un punto stazionario.
Questa proprietà assicura che con una scelta opportuna del passo ksia possibile stabilire un risultato di convergenza globale.
Algoritmo di Discesa del Gradiente Dati: scegliamo punto iniziale x0Rn; k0
while una stopping rule non è soddisfatta ( f(xk) 0)5 do dk:f(xk);
Calcola un passo kRlungo d con una tecnica di ricerca unidimensionale k (ad esempio Armijo);
xk1 xkkdk; kk1
end
5 Ci fermiamo quando il gradiente è vicino a zero.
Teorema (Convergenza globale del metodo del gradiente) Sia f :Rn Runa funzione continuamente differenziabile su Rn.
Si supponga che L sia compatto. Sia 0
x la successione prodotta dal metodo del gradiente. Si k supponga inoltre che la ricerca unidimensionale6 sia tale da soddisfare le condizioni:1. f
xk1 f(xk) (monotonicità)7 2. se f(xk)0 k, si ha) 0
lim (
k
k T k
k d
x f
d 8
.
Allora, o il metodo si arresta in un numero finito di iterazioni con f(xk)09, oppure viene prodotta una successione infinita, tale che ogni punto di accumulazione x di
xk L0e soddisfa
0f x 10. Dim.:
Siccome la direzione è l’antigradiente
) ( k
k f x
d
si ha
) ) (
(
k k
k T
k f x
d x f
d 11
Essendo soddisfatte le ipotesi del teorema di convergenza globale (condizione sufficiente), esiste una funzione di forzamento (t)t12 tale che sono soddisfatte le tesi di tale teorema, cioè:
o viene trovato un punto stazionario dopo un numero finito di passi, oppure viene generata una successione infinita di punti tale che13:
1. lim ( )0
k
k f x , la successione dei gradienti converge a zero;
6 Se usiamo la regola di Armijo (è una possibilità), abbiamo la convergenza globale.
7 Sia garantita la discesa.
8 È una ipotesi del teorema di convergenza globale. È una tesi del teorema di convergenza del metodo di Armijo.
9 Tangente orizzontale.
10 Non è garantita la convergenza della successione
xk . I punti limite xsono stazionari.11 Ho moltiplicato 1° e 2° membro per f(xk)e normalizzato dk. Normalizzare un vettore v significa moltiplicare il vettore vper un opportuno scalare scelto in modo tale che v 1 . Per far si che il vettore vabbia norma 1, dobbiamo prendere
v
1
, infatti con tale scelta di abbiamo 1 1 v 1 v v
v .
12(t)t è la funzione identità. Se va a zero la funzione, va a zero anche l’argomento della funzione.
13 O k con f(xk)0, oppure la successione dei gradienti tende a zero
f(xk)
0.
2. ogni punto limite xdi
x soddisfa k f(x)0, limite di ogni sottosuccessione è un punto stazionario.c.v.d.
La convergenza globale può essere assicurata attraverso una tecnica di ricerca unidimensionale tipo- Armijo o Wolfe.
Il metodo del gradiente costituisce il prototipo di algoritmo globalmente convergente e può essere usato, in associazione ad altri metodi dotati di migliori caratteristiche di convergenza locale, per assicurare la convergenza globale.
Teorema (Metodo del gradiente con passo costante k 0)14 Sia f :Rn Runa funzione continuamente differenziabile su Rn.
Se x0L015 compatto e L0 (costante di Lipschitz) tale che Rn
y x y
x y
f x
f
( ) ( ) L , 16
Supponiamo che scegliendo valga la condizione
0 L
2
Allora, o viene trovato un punto stazionario dopo un numero finito di iterazioni, oppure la successione dei gradienti
xk f(xk)
converge a zero17.Dim.:
Per ipotesi il gradiente di f , f(xk), gode di una proprietà più forte della continuità, è Lipschitz continuo.
Per la dimostrazione utilizziamo il seguente Lemma:
xR
, 0, dRn, utilizzando il teorema della media in forma integrale si può scrivere )
(x d
f
01 ) (
)
(x d f x t d dt
f T 18
14è il “learning rate”, il passo è una costante, si usa nelle Reti Neurali. Rispetto al teorema precedente ha ipotesi in più. In questo momento ha grande importanza, è il metodo più usato nell’addestramento di reti neurali multistrato (metodo della backpropagation).
È un metodo molto lento, però ci assicura la convergenza.
15 Rispetto al teorema precedente è stato aggiunto x0.
16 Le variazioni del gradiente non sono troppe elevate nei punti in cui lo valutiamo. È simile alla continuità, ma è più forte. C’è L che dice di quanto varia la funzione per spostarmi da xa y. La lipschitzianità risulta una condizione più forte della continuità e meno forte della differenziabilità. x è Lipschitz continua ma non è differenziabile in O(0;0).
17 O kcon f(xk)0, oppure la successione dei gradienti tende a zero
xkf(xk)
0.) ( )
( )
( )
(
1 0
x f d x
f d dt d t x f d x
f T T T
19
d f x t d d f x
dtx f d x
f( ) T ( ) T ( ) T ( )
1
0
dt x f d t x f d x
f d x
f T
1
0
) ( ) (
) ( )
( 20
L
) ( )
(
1
0
f x dT f x d x t d xdt 21
1
0
L
) ( )
(x d f x d t d dt
f T
2
) L ( )
( 2
2
d x
f d x
f T
22
Supponiamo che sia xkL0, utilizzando il lemma precedente si ha23
k T
kk T k k
k k
k k k k
x f x f x
f x f x
f
x f x
f d x
f x
f
2 ) L ( ) ( )
(
) (
2 1
da qui segue
1
2 2
22 L
k k
k
k f x f x f x
x
f
1
22
1 L k
k
k f x f x
x
f
24
18 ( ) ,per 0ho ( ),per 1ho ( ),
1 0
d x f t
x f t
dt d t x f
dT
descrive tutto il segmento che va da 0 a1.
19 Sommo e sottraggo dTf(x).
20
21 f(xtd)f(x) Lxtdx Lt d
22
2 L L 2
L L
2 2 1
0 2 2 1 2
0
1 0
2 2 t d
d tdt
d dt
d t
d
.
23 e d f(xk). Inoltre d 2 dT d f
xk Tf
xk .24 f
xk1 f xk la vorremmo negativa per avere una successione monotona (decrescente), quindi dobbiamoimporre 0
2 1 L
dal momento che
2 1L
non sta diminuendo e f
xk 2è una quantità positiva.Scegliendo 0, se vogliamo che
2 1L
diminuisca deve essere
2 0 1 L
2 1
L
L
2
oppure
L 2
25
quindi la successione generata dal metodo è monotona (decrescente) perché
èmonotona decrescente 00
1 1 1
f x
f x f
x f x f
x f x
f
k k
k k
k k
Inoltre, se conosciamo L, allora possiamo trovare .
Quindi tutta la successione
x rimane per ipotesi in k L , chiuso e limitato; la successione 0
f
xk
è monotona e limitata, siccome siamo in un compatto avrà minimo e quindi converge26. Inoltre
00 2
1 L
2 1 L
2 1 L
2 2 1
2 1
2 1
k
k k
k
k k
k
k k
k
x f
x f x x f
f
x f x
f x f
x f x
f x f
e questo implica
0 )
(
f xk quindi abbiamo la convergenza del gradiente.
c.v.d.
25 I 2 potrebbero essere diversi, per semplicità abbiamo usato solo un .
26 In questo caso non abbiamo bisogno del teorema di convergenza globale perché abbiamo tutto per dimostrare la convergenza del gradiente.
Rapidità di convergenza del metodo del gradiente
Per valutare la rapidità di convergenza del metodo del gradiente facciamo riferimento al comportamento del metodo nella minimizzazione di una funzione quadratica convessa27. Supponiamo che la funzione quadratica
0 21x Qx Q
x
f T
abbia minimo (locale e globale) nell’origine, il metodo utilizzato sia quello del gradiente )
1 k k ( k
k x f x
x 28
Ik kkQ
xk k x Q x
Calcoliamo l’errore al passo k129
1
* 1 1
e
k k k
x x
x
Quindi
k
kT k
k k k
T k
k k k
x Q I x
x Q I Q I x
x Q I x
2 1
30
27 Usiamo la funzione quadratica, perché localmente rappresenta bene una funzione nell’intorno del punto di minimo.
28
Q x f
c x Q x f
Q x
c Qx x x f
k
k k
T T
) (
) (
0 2
) 1 (
2
29 Lo studio della rapidità di convergenza viene effettuato supponendo che
xk sia una successione convergente aRn
x* e consiste nello stimare la velocità con cui tende a zero l’errore ekdefinito da una norma della differenza tra
xk e x*, ossia ek xk x* . Nel nostro caso la distanza tra xk1 e il punto di ottimo x*che è zero.
30
I kQ
è una matrice, I è la matrice identità. xkè il vecchio iterato. xTk
IkQ
2xk è molto complicata, vogliamo sostituire la matrice Q con autovalori eliminando così la parte matriciale.Sia *l’autovalore massimo della matrice
IkQ
2, ricordando che xx Ax
x x
xT T max T
min
31
abbiamo
k
k Tk kT
k I Q x x x
x 2 * 32
Immaginiamo, per semplicità, che 1,n siano rispettivamente l’autovalore minimo e l’autovalore massimo di Q, allora vale la stima seguente
k k n
k k
n k k
k k
x x
x x
x x
1 , 1
max
1 , 1
max
1 1
* 1
* 1
Togliamo i moduli a max
1k1,1kn
, ricordando che amax
a,a
, abbiamo
1k ,1kn
max 1 =
1
k
,1
k
,1
k
n,1
k
n
max 1 1
ma k 0,1n, quindi
1 1
1 1
1 1
k n
k
n k k
in definitiva abbiamo
k k n
k
k x
x 1 max1 1,1 che è una funzione di
31 minè l’autovalore minimo, maxè l’autovalore massimo.
32 Non conosciamo gli autovalori di
I kQ
2.Indichiamo con *(passo ideale) il migliore caso possibile
n k
k
*1 11 33
n
1
* 2
Al posto di k sostituisco
n
1
2 e ottengo
1 1
2
1 2
1 1 1
1 1 1
1 1 1
1 1
1 1
1
k n n
k n n k
n n k
n k
k
x x x x x x
dove
1
n è il numero di condizionamento della matrice Q.
Osserviamo che, se 1(autovalori max e min sono vicini), la convergenza è molto veloce, la convergenza viene ottenuta in un solo passo da ogni punto iniziale.
Se 1 la convergenza è notevolmente lenta (autovalori max e min distanti tra di loro).
La rapidità di convergenza del metodo del gradiente peggiora quindi, in genere, al crescere di , ossia all’aumentare del mal condizionamento della matrice Q.
33
n k
n k
n k k
n k k
1 1
* 1
1
* 2
0 2
1 1
1 1
.
zig-zagging
Vediamo un esempio pratico, sia f una funzione in due variabili
0 0 , 1
) , (
2 , 1
2
2 2
y x f
y y x
x f
y x
y x f
dove 0. Immaginiamo che
,1 sia il punto di partenza, sappiamo che il passo ottimo k 34 è2 3 2
2 2 2
) (
y x
y x
d Q d
x f d
k T
k k T k k
dopo una serie di calcoli elementari (noiosi), se partiamo da x0 e y0 1 otteniamo
k k
k k
y x
1 1 1 1
1 1
Studiamo la convergenza:
molto veloce se 1
estremamente lenta se 1 o 1, in questo caso abbiamo il cosiddetto “zig-zagging”.
Nella seguente figura è illustrato il fenomeno dello “zig-zagging” relativo alla funzione
2 2
2
,y 1 x y
x
f quando 50
34
Q x f
c x Q x f
Q x c Qx x x f
k
k k
T T
) (
) (
0 2
) 1 (
2
0 :
) (
2 ) 1 (
) (
k T k T
k k T k
k T k k T
k
k k T k k T
k k k
k
d c d Q d x Q d
d c d x Q d
d x c d x Q d x d
x f
k k T
k
k T k k
T k
k T
k
k d f x d
x f d d
Q d
c x Q d
) (
) (
2
come si può osservare, il metodo ripete la stessa direzione una volta si e una volta no, le direzioni sono quasi parallele, in questo caso il metodo è molto inefficiente. Una soluzione allo zig-zagging potrebbe essere quella di “scalare” gli assi in modo da far diventare le curve di livello da ellissoidali a sferiche.
Le considerazioni svolte nel caso quadratico, sono ovviamente indicative anche del comportamento locale del metodo nella minimizzazione di funzioni non quadratiche, come si può osservare nella seguente figura
dove è visibile il cosiddetto “effetto banana”.
In generale, tanto più sono allungate le curve di livello (ellissi appiattite), tanto peggiore è la direzione dell’antigradiente. Inoltre possiamo dire che
se 1
1
n
, le ellissi diventano dei cerchi e la direzione del gradiente passa direttamente per il centro, l’antigradiente punta verso il centro (minimo); il metodo del gradiente convergerà in una sola iterazione;
se 1
1
n
, le ellissi risultano fortemente eccentriche , sono allungate (“effetto banana”), il metodo convergerà lentamente seguendo una traiettoria a zig-zag; gli assi sono uno più corto l’altro più lungo, i semiassi hanno lunghezza inversamente proporzionale ai valori n e 1.
Metodo Heavy Ball o “momentum”35
Il metodo del gradiente (senza memoria) utilizza solo le informazioni relative all’iterazione corrente, e quindi non tiene conto in alcun modo delle informazioni derivanti dalle iterazioni precedenti.
Al fine di accelerare la convergenza può essere conveniente introdurre nella regola di aggiornamento del punto corrente termini che riassumano le informazioni di una o più iterazioni precedenti.
Il metodo “Heavy Ball” (con memoria) è un metodo iterativo multistep a “due passi” (nel senso che utilizza informazioni di due iterazioni, quella corrente e quella precedente) in cui l’aggiornamento del punto corrente avviene con la seguente regola
1
1
k k k k k k
k x f x x x
x
Ci limiteremo ad analizzare ed evidenziare i potenziali vantaggi del metodo (con memoria) Heavy Ball rispetto al metodo (senza memoria) del gradiente, al caso di funzione obiettivo quadratica convessa
0 2
) 1
(x x Qx Q
f T
e scegliendo in modo specifico i valori dei passi e abbiamo
k k n
n
k n
n k
x x x x
1 1
1 1 1
1 1 1
1 1 1
da cui segue che in problemi mal condizionati, fissando un grado di precisione desiderato, il metodo Heavy Ball può richiedere, rispetto al metodo del gradiente, un numero di iterazioni molto più basso.
35 Heavy Ball (palla pesante): se immaginiamo ogni iterazione come un punto della traiettoria di una palla che cade, i punti portano con sé un momento o una velocità. Metodo momentum nella letteratura sulle reti neurali
Teorema (Convergenza finita del metodo del gradiente nel caso quadratico con
k
k
1 )
Si consideri il problema di minimizzare la funzione quadratica strettamente convessa 0
2
min 1xT QxcTx Q
Allora il metodo del gradiente definito dall’iterazione
kk k
k x f x
x 1
con la scelta dei passi uguali agli inversi degli auto valori di Q n k
k
k 1 1,...,
converge al massimo in n iterazioni al punto di minimo della funzione obiettivo.
Dim.:
ricordando l’espressione del gradiente della funzione quadratica, si può scrivere 36
1
1
1
1
1 1
k k
k k
k
k k
k
k k k k k
x f Q I
x f Q x
f
c x f Q x
Q
c x f x
Q
c x Q x
f
Applicando ripetutamente la formula precedente, si può porre
11 1
1 Q f x
I x
f
k
i i
k
Sia v un insieme di autovettori linearmente indipendenti di i Q, associati agli autovalori i, per cui
i i
i v
v Q Possiamo esprimere
x v Rf i
n
i
i
i
1 1
da cui segue che
36 f
xk1
Qxk1c; f
xk Qxk c.
n
j
j j k
i i
k I Q v
x f
1 1 1
1
All’iterata n1abbiamo 37
) (per 0 1
1
1
1
1 1
1 1
1 1
1 1
1
i j v
v
v Q v
v Q I
v Q
I x
f
n
j
n
i
j j i j j
n
j
n
i
j i j j
n
j
n
i
j i
j
n
j
j j n
i i
n
e quindi possiamo concludere che il metodo del gradiente converge in (al più) n passi.
c.v.d.
37
i i
i v
v
Q , Qvj j vj.
![X F ( x ) n X F ( x ) ( n ) X X F ( x ) X X F ( x )=[ F ( x )] n ( n ) X X F ( x ) 1 2 n ( X ,X ,...,X ) ( n ) X](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)