4.5 Metodo del gradiente
Si cerca un punto stazionario di f : Rn → R con f ∈ C 1 .
Metodo del gradiente con ricerca 1-D esatta:
Scegliere x 0 , porre k := 0
Iterazione:
d k := −∇f (x k )
Determinare αk > 0 tale che minα≥0 φ(α) = f (x k + αd k )
x k+1 := x k + αk d k
k := k + 1
Criteri di arresto: k∇f (x k )k < ε o |f (x k ) − f (x k+1 )| < ε o kx k+1 − x k k < ε.
Propriet`
a: Se ricerca 1-D esatta, le direzioni successive sono ortogonali.
Poich´e αk tale che minα≥0 φ(α) = f (x k + αd k ),
φ′ (αk ) = ∇t f (x k + αk d k )d k = ∇t f (x k+1 )d k = 0.
e quindi d tk+1 d k = −∇t f (x k+1 )d k = 0.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
1 / 12
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
Esempio: traiettoria a zig zag, convergenza molto lenta
Consideriamo prima le propriet`
a di convergenza per le funzioni quadratiche strettamente
convesse.
Caso importante perch´e qualsiasi funzione C 2 pu`
o essere bene approssimata intorno ad
un minimo locale/globale da una funzione quadratica.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
2 / 12
Funzioni quadratiche strettamente convesse:
f (x) =
1 t
x Qx − b t x
2
con Q simmetrica e definita positiva.
o
Minimo globale `e l’unica soluzione di ∇f (x) = Qx − b = 0 (quindi di Qx = b) e αk pu`
essere determinato esplicitamente:
1
φ(α) = f (x k − α∇f (x k )) = (x k − α∇f (x k ))t Q(x k − α∇f (x k )) − b t (x k − α∇f (x k ))
2
φ′ (α) = −∇t f (x k )Q(x k − α∇f (x k )) + b t ∇f (x k ) = 0
Visto che ∇tx f (x k ) = x tk Q − b t implica b t = −∇t f (x k ) + x tk Q
−∇t f (x k )Qx k + α∇t f (x k )Q∇f (x k ) + (−∇t f (x k ) + x tk Q)∇f (x k ) = 0
quindi
αk =
∇t f (x k )∇f (x k )
∇t f (x k )Q∇f (x k )
e in termini di d k :
αk =
Edoardo Amaldi (PoliMI)
d tk d k
.
d tk Qd k
Ottimizzazione
A.A. 2013-14
3 / 12
Rapidit`
a di convergenza
Spesso si considera la rapidit`
a di convergenza con la quale f (x k ) → f (x ∗ ) invece di
∗
kx k − x k → 0 quando k → ∞.
Proposizione: Se H(x ∗ ) definita positiva, x k converge (super)linearmente ad x ∗ rispetto
a |f (x k ) − f (x ∗ )| se e solo se converge nello stesso modo rispetto a kx k − x ∗ k.
Infatti, vicino a x ∗
f (x) ≈ f (x ∗ ) +
e ∃ intorno N(x ∗ ) tale che
′
1
(x − x ∗ )t H(x ∗ )(x − x ∗ )
2
′
λ1 kx − x ∗ k2 ≤ |f (x) − f (x ∗ )| ≤ λn kx − x ∗ k2
′
∀x ∈ N(x ∗ )
′
con λ1 = λ1 − ε > 0 e λn = λn + ε, dove ε > 0 e 0 < λ1 ≤ . . . ≤ λn sono gli autovalori
di H(x ∗ ).
N.B.: In generale non esiste un’equivalenza (e.g. funzioni non ovunque C 1 ) ma vale per
funzioni quadratiche strettamente convesse.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
4 / 12
Funzioni quadratiche strettamente convesse:
Sia f (x) = 21 x t Qx − b t x e la norma pesata kxk2Q := x t Qx.
Poich´e Qx ∗ = b,
1
kx − x ∗ k2Q = 21 (x − x ∗ )t Q(x − x ∗ ) = 21 x t Qx + 12 x ∗t Qx ∗ − x ∗t Qx = f (x) − f (x ∗ )
2
Teorema: Se il metodo del gradiente con ottimizzazione 1-D esatta viene applicato ad
f ∈ C 2 quadratica strettamente convessa, {x k } → x ∗ per qualsiasi x 0 e
λn − λ1 2
) kx k − x ∗ k2Q
λn + λ1
dove 0 < λ1 ≤ . . . ≤ λn sono gli autovalori di Q.
kx k+1 − x ∗ k2Q ≤ (
Dim.: Risultato di convergenza globale (Zoutendijk) +
Si applica la disuguaglianza di Kantorovich: Se Q definita positiva (con λ1 e λn minimo
e massimo autovalore), per ogni x 6= 0 si ha
(x t x)2
(x t Qx)(x t Q −1 x)
≥
4λn λ1
.
(λn + λ1 )2
Se λ1 = λn (Q = γI e curve di livello = cerchi), metodo “converge” in una iterazione.
Aikake ha mostrato che questo limite superiore `e raggiunto per certe scelte di x 0 .
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
5 / 12
Il tasso di convergenza dipende dal numero di condizionamento κ =
λn
λ1
di Q:
λn − λ1
κ−1
)=(
)
λn + λ1
κ+1
r `e tanto pi`
u piccolo quanto κ `e vicino ad 1; se lo spettro di Q `e molto ampio allora
κ ≫ 1 e r ≈ 1.
r =(
Funzioni non lineari generiche:
Teorema: Se f ∈ C 2 e metodo del gradiente con ricerca 1-D esatta converge a x ∗ con
H(x ∗ ) definita positiva, allora
f (x k+1 ) − f (x ∗ ) ≤ (
λn − λ1 2
) [f (x k ) − f (x ∗ )]
λn + λ1
dove 0 < λ1 ≤ . . . ≤ λn sono gli autovalori di H(x ∗ ).
In genere non ci si pu`
o aspettare convergenza migliore con ricerca 1-D inesatta.
Determinare αk che minimizza φ(α) pu`
o non essere la scelta migliore, bisognerebbe
cercare di “estrarre” informazioni del 2o ordine su f (x).
Esempio: per f quadratica strettamente convessa, αk = 1/λk+1 ”porta” a x ∗ in al pi`
un
passi!
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
6 / 12
4.6 Metodo di Newton
Siano f ∈ C 2 e H(x) = ∇2 f (x).
Consideriamo l’approssimazione quadratica intorno a x k :
1
(x − x k )t H(x k )(x − x k )
2
un suo punto stazionario (∇x qk (x) = 0), ovvero tale che
qk (x) := f (x k ) + ∇t f (x k )(x − x k ) +
e scegliamo come x k+1
∇f (x k ) + H(x k )(x k+1 − x k ) = 0.
Se H(x k ) non singolare, H −1 (x k ) esiste e
x k+1 := x k − H −1 (x k )∇f (x k ).
Se H(x k ) `e definita positiva, allora f ∈ C 2 implica H −1 (x) definita positiva su N(x k ) e
l’iterazione `e ben-definita in N(x k ), altrimenti direzione potrebbe non essere di discesa.
Nel metodo di Newton “puro” αk = 1 per ogni k.
Se f `e una funzione quadratica strettamente convessa, il minimo globale si trova in
un’unica iterazione.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
7 / 12
Propriet`
a: Metodo invariante rispetto a cambio di coordinate affine non singolare
(esercizio 6.5)
Osservazione: Per funzioni generiche convergenza locale molto rapida, ma non globale!
3
3
Esempio: minx∈R f (x) = − exp(−x 2 ) con minimo globale x ∗ = 0 e f ′ (x) = 2x exp(−x 2 )
1
2
f’(x)
x0 x2
0
0
1
2
f(x)
x
x1
x0
2
x1 x2
...
x
−1
−2
−2
−1
2
−3
−2
−1
0
1
2
3
−3
−2
−1
0
1
2
3
Se −0.2 ≤ x0 ≤ 0.2, {xk }k∈N converge a x ∗ = 0. Se x0 > 1, {xk }k∈N diverge.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
8 / 12
Interpretazione alternativa del metodo di Newton (caso 1-D):
f (x) ∈ C 2 e si cerca x ∗ tale che f ′ (x) = 0.
Metodo delle tangenti (Newton-Raphson) per determinare gli zeri di una funzione:
All’iterazione k, f ′ (x) approssimata con la tangente in xk
z = f ′ (xk ) + f ′′ (xk )(x − xk )
xk+1 corrisponde all’intersezione con asse di x:
xk+1 = xk −
f ′ (xk )
.
f ′′ (xk )
Caso n-D: Si determina un punto stazionario di f risolvendo il sistema non lineare
∇f (x) = 0 mediante il metodo di Newton-Raphson.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
9 / 12
Teorema:
Supponiamo f ∈ C 2 e x ∗ tale che ∇f (x ∗ ) = 0 e H(x ∗ ) definita positiva e
kH(x) − H(y )k ≤ Lkx − y k
∀x, y ∈ N(x ∗ )
allora, per x 0 sufficientemente vicino al minimo locale x ∗ ,
i) {x k } → x ∗ con rapidit`
a di convergenza quadratica,
ii) {k∇f (x k )k} → 0 quando k → ∞ quadraticamente.
Svantaggi:
Se H(x k ) `e singolare il passo non `e ben-definito.
Se H −1 (x k ) non `e definita positiva, la direzione di Newton pu`
o non essere di
discesa per f .
Anche se la direzione `e di discesa il passo αk = 1 potrebbe aumentare il valore di f .
a O(n3 ) ).
Calcolo di H −1 (x k ) ad ogni iterazione ( complessit`
Convergenza solo locale: se x 0 non `e abbastanza vicino al minimo locale la
o non convergere.
successione {x k } pu`
Poich´e il metodo converge a partire da un intorno di un qualsiasi punto stazionario
o convergere verso massimi locali.
in cui ∇2 f (x k ) non `e singolare, pu`
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
10 / 12
Modifiche del metodo di Newton
1) Se il passo αk = 1 non soddisfa le condizione di Wolfe (o alternative), si effettua una
ricerca unidimensionale approssimata.
2) Per garantire la convergenza globale, si pu`
o modificare la direzione di Newton
considerando
d k = −Dk ∇f (x k )
con una matrice Dk diversa da [∇2 f (x k )]−1 .
Se Dk `e simmetrica e definita positiva, d k `e una direzione di discesa.
“Compromesso” tra direzioni di massima discesa e di Newton:
Dk := (εk I + ∇2 f (x k ))−1
dove εk > 0 sono i pi`
u piccoli valori tali che gli autovalori di (εk I + ∇2 f (x k )) siano
≥ δ > 0. Esiste sempre un εk che rende Dk definita positiva.
Coincide con metodo “puro” di Newton quando ci si avvicina ad un minimo locale.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
11 / 12
3) Metodi a passi ristretti (”trust region methods”)
Idea: La direzione d k e il passo αk vengono determinati contemporaneamente
minimizzando l’approssimazione quadratica qk (x) intorno a x k corrente su una regione di
confidenza (“trust region”) in cui qk (x) fornisce una buona approssimazione di f (x).
Esempio di regione di confidenza: palla di raggio ∆k > 0.
Illustrazione:
o essere risolto in forma chiusa o
In genere il sottoproblema (per determinare d k e αk ) pu`
richiede un onere computazionale ridotto.
La dimensione della regione di confidenza (e.g., ∆k se palla) viene variata in modo
adattativo in base ad una stima della qualit`
a dell’approssimazione quadratica sulla
regione corrente.
Edoardo Amaldi (PoliMI)
Ottimizzazione
A.A. 2013-14
12 / 12
© Copyright 2024 ExpyDoc
