Metodi di Ricerca Lineare · CondizioniNecessarie CondizioniNecessarie MetodidiRicercaLineare...

Condizioni Necessarie Condizioni Necessarie Metodi di Ricerca Lineare Passo di spostamento

Metodi di Ricerca Lineare

Stefano GualandiUniversità di Pavia, Dipartimento di Matematica

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


Metodi di Ottimizzazione

1 Iteration: conta il valore k per xk+1 = xk + αkdk . Parte dak = 0.

2 Func-Count: numero di valutazioni di f (x̄), per diversi valori di x̄.

3 f(x): il valore di f (xk)

4 Step-size: il valore di αk

5 First-Order optimality: il valore di ||∇f (xk)||∞



NOTA: per la stessa funzione, usata con gli stessi parametri, mapartendo da un punto iniziale diverso, possiamo ottenere un diversonumero di iterazioni, e, potenzialmente, anche un diverso puntostazionario (o non avere proprio convergenza...)



Metodi di OttimizzazioneI metodi numerici per il calcolo di minimi di una funzione obiettivosono di tipo iterativo: a partire da un dato punto iniziale x0 ∈ Rn

generano una successione di punti xk convergente ad un puntostazionario.

SCHEMA GENERICO DI ALGORITMO ITERATIVO1 Sia dato x0 e un valore di tolleranza numerica toll2 while(||∇f (xk)||∞ > 10−13) (Verifica C.N. I ordine)3 il metodo genera un vettore hk

4 xk+1 = xk + hk (aggiornamento dell’iterata)5 end

La scelta fatta del vettore hk differenzia il metodo usato.


Proprietà

Affidabilità e convergenzaSiamo interessati ad algoritmi affidabili e efficienti:

L’affidabilità è associata al concetto di convergenza: ilmetodo converge ad un punto stazionario? È anche un puntodi minimo?L’efficienza si misura in termini di velocità di convergenza ecosto computazionale: con che velocità il metodo converge adun punto stazionario? Quante risorse di calcolo consuma ilmetodo?


Theorem 1 (Teorema di Taylor)Sia f ∈ C1 nell’intorno di un segmento che unisce i punti x ex + p, e quindi con x , p ∈ Rn, allora si ha che

f (x + p) = f (x) +∇f (x + tp)Tp (1)

per un qualche t ∈ (0, 1). Se f ∈ C2, abbiamo anche che

∇f (x + p) = ∇f (x) +∫ 1

0∇2f (x + tp)p dt, (2)

ef (x + p) = f (x) +∇f (x)Tp + 1

2pT∇2f (x + tp)p, (3)

per un qualche t ∈ (0, 1).


Theorem 2 (Teorema di Taylor)Sia f ∈ C2 nell’intorno di un punto x̄ ∈ Rn. Allora per p ∈ Rn e||p|| sufficientemente piccola:

f (x̄ + p) = f (x̄) +∇f (x̄)Tp + 12p

T∇2f (x̄)p + o(||p||2). (4)

AttenzioneIntuitivamente, stiamo approssimando una funzione non linearef (x), in un intorno piccolo di x̄ , con un suo modello quadratico.L’errore commesso sarà dell’ordine di o(||p||).

Iperpiano tangenteSe ci limitiamo ad usare il gradiente ignorando l’Hessiano, è comese stessimo approssimando la funzione f (x) con l’iperpianotangente nel punto x̄ (pensare alla retta tangente ad una curva).


Theorem 3 (Condizione necessaria del 1o ordine)Se f (x) ∈ C1(Rn) e x∗ è un minimo relativo, allora x∗ è un puntostazionario di f (x) e vale:

∇f (x∗) = 0 (5)

Theorem 4 (Condizione necessaria del 2o ordine)Se f (x) ∈ C2(Rn) e x∗ è un minimo relativo, allora ∇f (x∗) = 0 e∇2f (x∗) è semidefinita positiva.

Theorem 5 (Condizione sufficiente)Sia f ∈ C2 in un intorno di x∗. Si assuma che ∇f (x∗) = 0 e che∇2f (x∗) sia definito positivo. Allora x∗ è un punto di minimolocale per f .


Proof: Condizione necessaria del 1o e 2o ordine

Proof.Sia u ∈ Rn. Per il teorema di Taylor abbiamo che per ogni t ∈ Rsufficientemente piccolo:

f (x∗ + tu) = f (x∗) + t∇f (x∗)T u + t2

2 uT∇2f (x∗)u + o(t2).

Poiché x∗ è un punto di minimo locale (vedi definizione) dobbiamo avere cheper t sufficientemente piccolo

f (x∗) ≤ f (x∗ + tu) ⇒ f (x∗ + tu)− f (x∗) ≥ 0

e quindi:∇f (x∗)T u + t

2uT∇2f (x∗)u + o(t) ≥ 0

per tutti i t sufficientemente piccoli e per tutti i vettori u ∈ Rn.


Proof: Condizione necessaria del 1o e 2o ordine

Proof.

∇f (x∗)T u + t2uT∇2f (x∗)u + o(t) ≥ 0

per tutti i t sufficientemente piccoli e per tutti i vettori u ∈ Rn. Quindi seponiamo t = 0 e u = −∇f (x∗) otteniamo:

−∇f (x∗)T∇f (x∗) ≥ 0 ⇒ ||∇f (x∗)||2 = 0 ⇒ ∇f (x∗) = 0

Ponendo ∇f (x∗) = 0, dividendo per t sopra, si ottiene:

12uT∇2f (x∗)u ≥ 0

per ogni u ∈ Rn, ovvero, la matrice Hessiana in x∗ è semidefinita positiva.



Data il problema di ottimizzazione

min f (x), x ∈ R

I metodi numerici che studiamo, partendo da un punto inizialex0 ∈ R, cercano una successione di nuovi punti xk usando la regoladi aggiornamento

xk+1 = xk + hk

cercando di garantire che la successione {xk}k>0 converge ad unpunto x∗ tale per cui

∇x∗ = 0

I Metodi di Ricerca Lineare scelgono il vettore hk = αkdk ,ovvero

xk+1 = xk + αkdk



I Metodi di Ricerca Lineare scelgono il vettore hk come

xk+1 = xk + αkdk

in cui lo scalare αk ∈ R viene chiamato passo di spostamento(Step-size) e il vettore dk ∈ Rn è la direzione di spostamento.

DOMANDA: Quale condizione su xk+1 vogliamo verificare adogni iterazione?

La condizione minima che vorremo verificare è che

f (xk+1) < f (xk) ⇒ f (xk + αkdk) < f (xk)


Definition 6 (Direzione di discesa)Sia f ∈ C2(Rn). Se dT

k ∇f (xk) < 0, allora dk è una direzione didiscesa, pur di prendere αk sufficientemente piccolo.

La proprietà dTk ∇f (xk) < 0 garantisce che la funzione f può

diminuire lungo la direzione dk .


Significato geometrico della direzione di discesa

∇f (xk)T dk = ||∇f (xk)||2 ||dk ||2 cos(θk)dove ||||2 indica la norma euclidea e θk è l’angolo compreso tra ∇f (xk) e dk . Ledirezioni di discesa sono quelle che formano un angolo ottuso con il gradiente.


Scelta della direzione di discesa

NOTA: Ricordarsi che (AB)T = BTAT e che se A è una matricesimmetrica allora A = AT .

La direzione di ricerca può essere scritta in modo generale nellaforma

dk = −B−1k ∇f (xk), (6)

in cui Bk è una matrice simmetrica non singolare. Quando dk èdefinita dalla (6) e Bk è definita positiva (definizione?), abbiamo

dTk ∇f (xk) = −(B−1

k ∇f (xk))T∇f (xk) = −∇f (xk)TB−1k ∇f (xk)< 0,

e quindi dk è una direzione di discesa.


Metodi di Ricerca Lineare in funzione di Bk

Diverse scelte della matrice Bk portano a diversi metodi di ricercalineare:

1 Bk = I: se Bk è la matrice identità, otteniamo il metodo dimassima discesa, chiamato anche metodo del (anti)gradiente(opzione matlab: ’HessUpdate’,’steepdesc’)

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(opzione: ’HessUpdate’,’dfp’ oppure’HessUpdate’,’bfgs’)


Scelta del passo di spostamento αk

Fissata l’iterata corrente xk e la direzione dk , la scelta idealesarebbe trovare il valore che minimizza la funzione univariata φ(·)definita da

φ(α) = f (xk + αdk), con α > 0, (7)

ovvero si vuole trovare il αk che risolve il problemamonodimensionale:

αk = arg min{φ(α) | α > 0}. (8)

OSSERVAZIONE: Si noti che per come è definita φ(α) abbiamo

φ′(α) = ∇f (xk + αdk)T dk

φ(0) = f (xk), e φ′(0) = ∇f (xk)T dk


Scelta del passo di spostamento αk

Fissata la direzione dk si vuole risolvere il problema 1D:

αk = arg min{φ(α) | α > 0}

Strategia di ricerca:ESATTA: trovare un minimo di φ(α),ma è computazionalmente costosoe richiede troppe valutazioni di f (x) e ∇f (x).EURISTICA: algoritmi di ricerca monodimensionali per identificare unpasso che permetta un’adeguata riduzione di f (x) con il minimo sforzocomputazionale. Esempio:

BacktrackingMetodi di interpolazione

EURISTICA con GARANZIA: Altri algoritmi generano una successionedi αk arrestandosi quando il passo soddisfa opportune condizioni chegarantiscono la convergenza (globale) del metodo di discesa. Esempio:

Condizioni di Armijo e di GoldsteinCondizioni di WolfeCondizione di Armijo e regole di salvaguardia


Backtracking

Il più semplice dei metodi euristici è il metodo di Backtracking,in cui il parametro β viene chiamato fattore di riduzione:

NOTA: Nella versione base del metodi di Backtracking nonabbiamo tuttavia nessuna garanzia che il metodo converga ad unpunto stazionario (!!)


Condizioni di Armijo

Una condizione su αk che viene usata nei metodi di ricerca lineareeuristici impone un vincolo sulla riduzione dif (xk+1) = f (xk + αkdk), che deve essere inferiore rispetto a f (xk)di un valore tale per cui viene verificata la

Condizione di Armijo : f (xk + αkdk) ≤ f (xk) + ραk∇f (xk)Tdk

in cui ρ ∈ (0, 1) è un valore di solito pari a 10−4.

Questa condizione richiede che la riduzione di f sia proporzionalesia al passo αk che alla derivata direzionale ∇f (xk)Tdk .


Condizione di curvatura

La condizione di Armijo non è ancora tuttavia sufficiente pergarantire che l’algoritmo realizzi un miglioramento significativo peril valore di f , in quanto la (20) è soddisfatta da tutti i valorisufficientemente piccoli di αk . Per questo motivo, si introduce unaseconda condizione che richiede che αk soddisfi la

Condizione di curvatura : ∇f (xk + αkdk)Tdk ≥ σ∇f (xk)Tdk ,

in cui σ ∈ (ρ, 1). Si noti che il termine a sinistra non è altro che laderivata φ′(αk), e quindi la condizione di curvatura assicura che lapendenza di φ(αk) sia maggiore di σ volte il gradiente φ′(0).


Andamento grafico di φ(α) 1/4


Le condizioni di Wolfe in senso forte richiedono che αk soddisfi

f (xk + αkdk) ≤ f (xk) + ραk∇f (xk)Tdk , (9)|∇f (xk + αkdk)Tdk | ≤ σ|∇f (xk)Tdk |, (10)

in cui 0 < ρ < σ < 1.

Lemma 7Sia f : Rn → R differenziabile con continuità. Sia dk una direzionedi discesa in xk , e si assuma che f sia inferiormente limitata lungoil raggio {xk + αdk | α > 0}. Allora se 0 < ρ < σ < 1, esiste unintervallo in cui i valori di α soddisfano le condizioni di Wolfe e lecondizioni di Wolfe in senso forte.

Metodi di Ricerca Lineare · CondizioniNecessarie CondizioniNecessarie MetodidiRicercaLineare...

Documents

Transcript of Metodi di Ricerca Lineare · CondizioniNecessarie CondizioniNecessarie MetodidiRicercaLineare...