Post on 22-Feb-2020
Metodi del Gradiente
Metodo del Gradiente
Stefano GualandiUniversità di Pavia, Dipartimento di Matematica
email: stefano.gualandi@unipv.ittwitter: @famo2spaghiblog: http://stegua.github.com
Metodi del Gradiente
Convergenza dei metodi di ricerca lineare
Theorem 1 (Dispense: Teorema 5)
Sia data una funzione f limitata inferiormente in Rn, di classe C1 in un insiemeaperto S contenente l’insieme di livello Lf (x0) = {x : f (x) ≤ f (x0)}, dove x0 èil punto di partenza di un algoritmo iterativo. Si supponga che ad ogniiterazione k la direzione dk soddisfi la condizione d’angolo ed il passo αksoddisfi le condizioni di Wolfe, per opportuni valori dei parametri ρ, σ, e ε. Sisupponga inoltre che il gradiente ∇f (x) sia Lipschitziano in S, cioè che esistauna costante L > 0 tale che il gradiente ∇f (x) soddisfi la seguente relazione
||∇f (x)−∇f (x̃)||2 ≤ L ||x − x̃ ||2 , per tutte le coppie di punti x , x̃ ∈ S
Allora la successione dei punti {xk} è tale che il gradiente di f (x) si annulla inun numero finito di passi o converge a zero asintoticamente:
esiste k con: ∇f(xk) = 0oppure la successione: {∇f(xk)} → 0
Metodi del Gradiente
CONSEGUENZE DEL TEOREMA: Ogni volta che abbiamo unmetodo iterativo che determina l’iterata successiva xk+1, chesoddisfa tutte le condizione del teorema, allora abbiamo unmetodo iterativo che converge ad un punto stazionario.
Metodi del Gradiente
Metodi del Gradiente
Data la generica direzione di discesa
dk = −B−1k ∇f (xk), (1)
diverse scelte della matrice Bk portano a diversi metodi:
1 Bk = I: se Bk è la matrice identità, otteniamo il metodo dimassima discesa, chiamato anche metodo del (anti) gradiente.
2 Bk = ∇2f (xk): se Bk è pari alla matrice Hessiana valutataall’iterata corrente, otteniamo il metodo di Newton.
3 Bk ≈ ∇2f (xk): se Bk è solo un’approssimazione della matriceHessiana all’iterata corrente, allora abbiamo un metodo diquasi-Newton.
Metodi del Gradiente
Metodi del Gradiente
Data la generica direzione di discesa
dk = −B−1k ∇f (xk), (1)
diverse scelte della matrice Bk portano a diversi metodi:
1 Bk = I: se Bk è la matrice identità, otteniamo il metodo dimassima discesa, chiamato anche metodo del (anti) gradiente.
2 Bk = ∇2f (xk): se Bk è pari alla matrice Hessiana valutataall’iterata corrente, otteniamo il metodo di Newton.
3 Bk ≈ ∇2f (xk): se Bk è solo un’approssimazione della matriceHessiana all’iterata corrente, allora abbiamo un metodo diquasi-Newton.
Metodi del Gradiente
Metodi del Gradiente
Data la generica direzione di discesa
dk = −B−1k ∇f (xk), (1)
diverse scelte della matrice Bk portano a diversi metodi:
1 Bk = I: se Bk è la matrice identità, otteniamo il metodo dimassima discesa, chiamato anche metodo del (anti) gradiente.
2 Bk = ∇2f (xk): se Bk è pari alla matrice Hessiana valutataall’iterata corrente, otteniamo il metodo di Newton.
3 Bk ≈ ∇2f (xk): se Bk è solo un’approssimazione della matriceHessiana all’iterata corrente, allora abbiamo un metodo diquasi-Newton.
Metodi del Gradiente
Metodi del Gradiente
Data la generica direzione di discesa
dk = −B−1k ∇f (xk), (1)
diverse scelte della matrice Bk portano a diversi metodi:
1 Bk = I: se Bk è la matrice identità, otteniamo il metodo dimassima discesa, chiamato anche metodo del (anti) gradiente.
2 Bk = ∇2f (xk): se Bk è pari alla matrice Hessiana valutataall’iterata corrente, otteniamo il metodo di Newton.
3 Bk ≈ ∇2f (xk): se Bk è solo un’approssimazione della matriceHessiana all’iterata corrente, allora abbiamo un metodo diquasi-Newton.
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?
Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) =
f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈
f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) =
dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α =
− dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
=
∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Metodo del GradienteNel metodo del gradiente la direzione di ricerca d coincide con l’antigradiente:d = −∇f (x). In un metodo iterativo si ha quindi
xk+1 = xk − αk∇f (xk) (2)
DOMANDA: Come scegliamo il passo αk?Possiamo approssimare f (x) con una funzione quadratica (Taylor):
φ(α) = f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1
2α2dT
k ∇2f (xk)dk
Calcolando ora la derivata di φ(α) rispetto ad α otteniamo
φ′(α) = dTk ∇f (xk) + αdT
k ∇2f (xk)dk
Se dTk ∇2f (xk)d k 6= 0, allora possiamo imporre φ′(α) = 0 e ricavare
α = − dTk ∇f (xk)
dTk ∇2f (xk)dk
= ∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa
xk+1 = xk −∇f (xk)T∇f (xk)
∇f (xk)T∇2f (xk)∇f (xk)∇f (xk)
Metodi del Gradiente
Velocità di convergenzaStudiamo la velocità di convergenza del metodo del gradiente per una funzioneobiettivo quadratica, con ricerca lineare di αk esatta (caso ideale: il meglio chesi possa fare).
Data la funzione quadratica:
f (x) = 12xTAx − bT x, (3)
in cui A è una matrice simmetrica e definita positiva, pari all’Hessiana di f (x).Il gradiente è pari a ∇f (x) = Ax − b, e il punto di minimo è l’unica soluzionedi Ax = b.Quindi il metodo del gradiente ha come iterata:
xk+1 = xk −(∇f (xk)T∇f (xk)∇f (xk)TA∇f (xk)
)∇f (xk)
Introduciamo la norma pesata ||x||2A = xTAx. Usando la relazione soddisfattadal punto di ottimo Ax∗ = b, si può mostrare che
12 ||x − x∗||2A = f (x)− f (x∗) (4)
Metodi del Gradiente
Velocità di convergenzaStudiamo la velocità di convergenza del metodo del gradiente per una funzioneobiettivo quadratica, con ricerca lineare di αk esatta (caso ideale: il meglio chesi possa fare). Data la funzione quadratica:
f (x) = 12xTAx − bT x, (3)
in cui A è una matrice simmetrica e definita positiva, pari all’Hessiana di f (x).Il gradiente è pari a ∇f (x) = Ax − b, e il punto di minimo è l’unica soluzionedi Ax = b.
Quindi il metodo del gradiente ha come iterata:
xk+1 = xk −(∇f (xk)T∇f (xk)∇f (xk)TA∇f (xk)
)∇f (xk)
Introduciamo la norma pesata ||x||2A = xTAx. Usando la relazione soddisfattadal punto di ottimo Ax∗ = b, si può mostrare che
12 ||x − x∗||2A = f (x)− f (x∗) (4)
Metodi del Gradiente
Velocità di convergenzaStudiamo la velocità di convergenza del metodo del gradiente per una funzioneobiettivo quadratica, con ricerca lineare di αk esatta (caso ideale: il meglio chesi possa fare). Data la funzione quadratica:
f (x) = 12xTAx − bT x, (3)
in cui A è una matrice simmetrica e definita positiva, pari all’Hessiana di f (x).Il gradiente è pari a ∇f (x) = Ax − b, e il punto di minimo è l’unica soluzionedi Ax = b.Quindi il metodo del gradiente ha come iterata:
xk+1 = xk −(∇f (xk)T∇f (xk)∇f (xk)TA∇f (xk)
)∇f (xk)
Introduciamo la norma pesata ||x||2A = xTAx. Usando la relazione soddisfattadal punto di ottimo Ax∗ = b, si può mostrare che
12 ||x − x∗||2A = f (x)− f (x∗) (4)
Metodi del Gradiente
Velocità di convergenzaStudiamo la velocità di convergenza del metodo del gradiente per una funzioneobiettivo quadratica, con ricerca lineare di αk esatta (caso ideale: il meglio chesi possa fare). Data la funzione quadratica:
f (x) = 12xTAx − bT x, (3)
in cui A è una matrice simmetrica e definita positiva, pari all’Hessiana di f (x).Il gradiente è pari a ∇f (x) = Ax − b, e il punto di minimo è l’unica soluzionedi Ax = b.Quindi il metodo del gradiente ha come iterata:
xk+1 = xk −(∇f (xk)T∇f (xk)∇f (xk)TA∇f (xk)
)∇f (xk)
Introduciamo la norma pesata ||x||2A = xTAx. Usando la relazione soddisfattadal punto di ottimo Ax∗ = b, si può mostrare che
12 ||x − x∗||2A = f (x)− f (x∗) (4)
Metodi del Gradiente
Velocità di convergenzaStudiamo la velocità di convergenza del metodo del gradiente per una funzioneobiettivo quadratica, con ricerca lineare di αk esatta (caso ideale: il meglio chesi possa fare). Data la funzione quadratica:
f (x) = 12xTAx − bT x, (3)
in cui A è una matrice simmetrica e definita positiva, pari all’Hessiana di f (x).Il gradiente è pari a ∇f (x) = Ax − b, e il punto di minimo è l’unica soluzionedi Ax = b.Quindi il metodo del gradiente ha come iterata:
xk+1 = xk −(∇f (xk)T∇f (xk)∇f (xk)TA∇f (xk)
)∇f (xk)
Introduciamo la norma pesata ||x||2A = xTAx. Usando la relazione soddisfattadal punto di ottimo Ax∗ = b, si può mostrare che
12 ||x − x∗||2A = f (x)− f (x∗) (4)
Metodi del Gradiente
Velocità di convergenza
Usando la norma pesata ||x||2A = xTAx e notando che∇f (xk) = Axk − b = A(xk − x∗), si può ricavare l’espressione
||xk+1 − x∗||2A ={1− (∇f (xk)T∇f (xk))2
(∇f (xk)TA∇f (xk))(∇f (xk)TA−1∇f (xk))
}||xk − x∗||2A
Siamo arrivati ad avere una relazione del tipo
||xk+1 − x∗||2A||xk − x∗||2A
= costante
Metodi del Gradiente
Velocità di convergenza
Usando la norma pesata ||x||2A = xTAx e notando che∇f (xk) = Axk − b = A(xk − x∗), si può ricavare l’espressione
||xk+1 − x∗||2A ={1− (∇f (xk)T∇f (xk))2
(∇f (xk)TA∇f (xk))(∇f (xk)TA−1∇f (xk))
}||xk − x∗||2A
Siamo arrivati ad avere una relazione del tipo
||xk+1 − x∗||2A||xk − x∗||2A
= costante
Metodi del Gradiente
Velocità di convergenza
Theorem 2Quando il metodo del gradiente con ricerca lineare esatta vieneapplicato alla funzione quadratica convessa (3), la normadell’errore (4) soddisfa la disuguaglianza
||xk+1 − x∗||2A ≤(λM − λmλM + λm
)2||xk − x∗||2A (5)
dove λM e λm > 0 sono rispettivamente l’autovalore massimo eminimo di A.
CONSEGUENZE DEL TEOREMA: Il metodo del gradiente hauna velocità di convergenza LINEARE.DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?
Metodi del Gradiente
Velocità di convergenza
Theorem 2Quando il metodo del gradiente con ricerca lineare esatta vieneapplicato alla funzione quadratica convessa (3), la normadell’errore (4) soddisfa la disuguaglianza
||xk+1 − x∗||2A ≤(λM − λmλM + λm
)2||xk − x∗||2A (5)
dove λM e λm > 0 sono rispettivamente l’autovalore massimo eminimo di A.
CONSEGUENZE DEL TEOREMA:
Il metodo del gradiente hauna velocità di convergenza LINEARE.DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?
Metodi del Gradiente
Velocità di convergenza
Theorem 2Quando il metodo del gradiente con ricerca lineare esatta vieneapplicato alla funzione quadratica convessa (3), la normadell’errore (4) soddisfa la disuguaglianza
||xk+1 − x∗||2A ≤(λM − λmλM + λm
)2||xk − x∗||2A (5)
dove λM e λm > 0 sono rispettivamente l’autovalore massimo eminimo di A.
CONSEGUENZE DEL TEOREMA: Il metodo del gradiente hauna velocità di convergenza LINEARE.
DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?
Metodi del Gradiente
Velocità di convergenza
Theorem 2Quando il metodo del gradiente con ricerca lineare esatta vieneapplicato alla funzione quadratica convessa (3), la normadell’errore (4) soddisfa la disuguaglianza
||xk+1 − x∗||2A ≤(λM − λmλM + λm
)2||xk − x∗||2A (5)
dove λM e λm > 0 sono rispettivamente l’autovalore massimo eminimo di A.
CONSEGUENZE DEL TEOREMA: Il metodo del gradiente hauna velocità di convergenza LINEARE.DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?