Metodo del Gradiente · 2019-11-20 · Metodi del Gradiente CONSEGUENZE DEL TEOREMA: Ogni volta che...

Metodi del Gradiente

Metodo del Gradiente

Stefano GualandiUniversità di Pavia, Dipartimento di Matematica

email: [email protected]: @famo2spaghiblog: http://stegua.github.com


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


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.



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.


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)



xk+1 = xk − αk∇f (xk) (2)

DOMANDA: Come scegliamo il passo αk?

Possiamo approssimare f (x) con una funzione quadratica (Taylor):


2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)


φ(α) =

f (xk + αdk) ≈ f (xk) + αdTk ∇f (xk) + 1

2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)


φ(α) = f (xk + αdk) ≈

f (xk) + αdTk ∇f (xk) + 1

2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)



2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)



2α2dT

k ∇2f (xk)dk


φ′(α) =

dTk ∇f (xk) + αdT

k ∇2f (xk)dk



dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)



2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)



2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk


α =

− dTk ∇f (xk)

dTk ∇2f (xk)dk






xk+1 = xk − αk∇f (xk) (2)



2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk

=

∇f (xk)T∇f (xk)∇f (xk)∇2f (xk)∇f (xk) e quindi l’iterata diventa





xk+1 = xk − αk∇f (xk) (2)



2α2dT

k ∇2f (xk)dk



k ∇2f (xk)dk



dTk ∇2f (xk)dk





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)


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:


)∇f (xk)


12 ||x − x∗||2A = f (x)− f (x∗) (4)


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:


)∇f (xk)


12 ||x − x∗||2A = f (x)− f (x∗) (4)


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



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?




||xk+1 − x∗||2A ≤(λM − λmλM + λm

)2||xk − x∗||2A (5)


CONSEGUENZE DEL TEOREMA:

Il metodo del gradiente hauna velocità di convergenza LINEARE.DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?




||xk+1 − x∗||2A ≤(λM − λmλM + λm

)2||xk − x∗||2A (5)


CONSEGUENZE DEL TEOREMA: Il metodo del gradiente hauna velocità di convergenza LINEARE.

DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?




||xk+1 − x∗||2A ≤(λM − λmλM + λm

)2||xk − x∗||2A (5)


CONSEGUENZE DEL TEOREMA: Il metodo del gradiente hauna velocità di convergenza LINEARE.DOMANDA: Qual’è il caso più fortunato possibile per ilmetodo del gradiente?

Metodo del Gradiente · 2019-11-20 · Metodi del Gradiente CONSEGUENZE DEL TEOREMA: Ogni volta che...

Documents

Transcript of Metodo del Gradiente · 2019-11-20 · Metodi del Gradiente CONSEGUENZE DEL TEOREMA: Ogni volta che...