Metodi di Ottimizzazione - · MetodiIterativi Metodi di Ottimizzazione StefanoGualandi...

Metodi Iterativi

Metodi di Ottimizzazione

Stefano GualandiUniversità di Pavia, Dipartimento di Matematica

email: [email protected]: @famo2spaghi, @famo2contiblog: http://stegua.github.com

Metodi Iterativi

Metodi di Ottimizzazione

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)||∞ >toll) (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.

Metodi Iterativi

Demo web

DEMO WEB:http://www.benfrederickson.com/numerical-optimization/

http://www.benfrederickson.com/numerical-optimization/

http://www.benfrederickson.com/numerical-optimization/

Metodi Iterativi

Calcolo della radice quadrata di un numero

Sia data la funzione f : R→ R seguente:

f (x) = x3

3 − rx

di cui si deve trovare un punto stazionario utilizzando un metodoiterativo, ovvero un punto che realizza

∇f (x) = 0 ⇒ ∇f (x) = x2 − r = 0

OsservazioneIn pratica, stiamo cercando un metodo iterativo che permetta diapprossimare al computer la radice quadrata di un numero. Ser = 2, stiamo cercando un’approssimazione di

√2.

Metodi Iterativi

Calcolo della radice quadrata di un numeroChiamiamo ora g(x) = x2 − r e vediamo come possiamo trovarecon un metodo iterativo un punto tale per cui g(x) = 0.

(DEMO: https://en.wikipedia.org/wiki/File:NewtonIteration_Ani.gif)

In pratica, approssimiamo la funzione g(x) in un punto xk con iprimi due termini del polinomio di Taylor

g(xk) + g ′(xk)(x − xk) = 0Il punto x che soddisfa l’equazione precedente, viene usato comenuovo punto xk , che meglio approssima

√r . In pratica risolviamo

g(xk) + g ′(xk)(xk+1 − xk) = 0da cui

xk+1 = xk −g(xk)g ′(xk)

https://en.wikipedia.org/wiki/File:NewtonIteration_Ani.gif


Metodi Iterativi

Calcolo della radice quadrata di un numeroChiamiamo ora g(x) = x2 − r e vediamo come possiamo trovarecon un metodo iterativo un punto tale per cui g(x) = 0.(DEMO: https://en.wikipedia.org/wiki/File:NewtonIteration_Ani.gif)








Metodi Iterativi



g(xk) + g ′(xk)(x − xk) = 0

Il punto x che soddisfa l’equazione precedente, viene usato comenuovo punto xk , che meglio approssima






Metodi Iterativi





g(xk) + g ′(xk)(xk+1 − xk) = 0

da cuixk+1 = xk −

g(xk)g ′(xk)



Metodi Iterativi









Metodi Iterativi

Metodo Iterativo per il calcolo di√

k

Abbiamo ora il nostro primo metodo iterativo:


DomandePossiamo garantire che il metodo converge ad un punto x∗?Possiamo garantire che il metodo converge proprio a

√r?

Esercizio 1Implementare uno script Matlab che calcola la radice quadrata di 2.(Prima di implementare, provare i conti a mano per trovare

√36)

Metodi Iterativi

Esempio numerico

Nel nostro caso, il metodo iterativo consiste nel calcolare


= xk −x2

k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)

Esempio numerico per calcolare√2, ovvero con r = 2

Iterata corrente xk Quoziente rxk

Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico


xk+1 = xk −g(xk)g ′(xk) = xk −

x2k − r2xk

=

2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

=

12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1

21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5

21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.4167

1.4167 21.4167 = 1.4118 (1.4118+1.4167)

2 = 1.41421.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167

21.4167 = 1.4118 (1.4118+1.4167)

2 = 1.41421.4142 ... ...

Metodi Iterativi

Esempio numerico



x2k − r2xk

= 2x2k − x2

k + r2xk

= 12(xk + r

xk)



Media tra xk e rxk

1 21

(1+2)2 = 1.5

1.5 21.5 = 1.3333 (1.3333+1.5)

2 = 1.41671.4167 2

1.4167 = 1.4118 (1.4118+1.4167)2 = 1.4142

1.4142 ... ...

Metodi Iterativi

Stima dell’erroreStudiamo l’errore del nostro metodo iterativo (senza conoscere ilvalore esatto di

√r). Sia Ek l’errore di approssimazione

Ek = xk −√r

da cui

xk =√r + Ek

L’errore alla prossima iterazione sarà

Ek+1 = xk+1 −√r =

xk + rxk

2 −√r

=xk + r

xk− 2√r

2 = x2k − 2

√rxk + r

2xk

= (xk −√r)2

2xk= E 2

k2xk

Metodi Iterativi



Ek = xk −√r

da cui

xk =√r + Ek


Ek+1 = xk+1 −√r =

xk + rxk

2 −√r

=

xk + rxk− 2√r

2 = x2k − 2

√rxk + r

2xk

= (xk −√r)2

2xk= E 2

k2xk

Metodi Iterativi



Ek = xk −√r

da cui

xk =√r + Ek


Ek+1 = xk+1 −√r =

xk + rxk

2 −√r

=xk + r

xk− 2√r

2 =

x2k − 2

√rxk + r

2xk

= (xk −√r)2

2xk= E 2

k2xk

Metodi Iterativi



Ek = xk −√r

da cui

xk =√r + Ek


Ek+1 = xk+1 −√r =

xk + rxk

2 −√r

=xk + r

xk− 2√r

2 = x2k − 2

√rxk + r

2xk

=

(xk −√r)2

2xk= E 2

k2xk

Metodi Iterativi



Ek = xk −√r

da cui

xk =√r + Ek


Ek+1 = xk+1 −√r =

xk + rxk

2 −√r

=xk + r

xk− 2√r

2 = x2k − 2

√rxk + r

2xk

= (xk −√r)2

2xk=

E 2k

2xk

Metodi Iterativi



Ek = xk −√r

da cui

xk =√r + Ek


Ek+1 = xk+1 −√r =

xk + rxk

2 −√r

=xk + r

xk− 2√r

2 = x2k − 2

√rxk + r

2xk

= (xk −√r)2

2xk= E 2

k2xk

Metodi Iterativi

Stima dell’erroreDopo la prima iterata x0, tutti gli errori successivi saranno semprepositivi. Inoltre l’errore ad ogni iterazione diventa sempre piùpiccolo, in quanto

Ek = xk −√r < xk e quindi 0 < Ek

xk< 1

da cui

Ek+1 = E 2k

2xk= Ek

xk× Ek

2 <Ek2

Riassumendo..... abbiamo dimostrato che l’errore del metodo iterativo diventasempre più piccolo ad ogni iterazione in quanto

0 < Ek+1 <Ek2 < Ek

Metodi Iterativi

Criterio d’arresto basato sulla stima dell’erroreDalle relazioni precedenti abbiamo che

0 < xk+1 −√r < xk −

√r

⇒√r < xk+1 < xk

Riprendendo la definizione di errore al passo kEk = xk −

√r = xk − xk+1 + xk+1 −

√r

= (xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1

In pratica, se si vuole una soluzione con un errore minore di ε > 0,basterà verificare la condizione:

xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r = xk − xk+1 + xk+1 −

√r

= (xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1


xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r =

xk − xk+1 + xk+1 −√r

= (xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1


xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r = xk − xk+1 + xk+1 −

√r

=

(xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1


xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r = xk − xk+1 + xk+1 −

√r

= (xk − xk+1) + Ek+1

< (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1


xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r = xk − xk+1 + xk+1 −

√r

= (xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1


xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r = xk − xk+1 + xk+1 −

√r

= (xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2

< xk − xk+1


xk − xk+1 < ε

Metodi Iterativi


0 < xk+1 −√r < xk −

√r ⇒

√r < xk+1 < xk


√r = xk − xk+1 + xk+1 −

√r

= (xk − xk+1) + Ek+1 < (xk − xk+1) + Ek2

ovvero

Ek+1 <Ek2 < xk − xk+1


xk − xk+1 < ε

Metodi Iterativi

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?

Metodi Iterativi

Convergenza

Definition 1 (Convergenza locale)Un algoritmo di ottimizzazione converge localmente ad un punto diminimo x∗ se per scelte di x0 sufficientemente vicine a x∗ la successionegenerata a partire da x0, ovvero la successione {xk(x0)}, converge a x∗,ovvero se ∃ρ > 0 tale che

∀x0 ∈ B(x∗, ρ) = {x : ||x − x∗|| < ρ} ⇒ {xk(x0)} → x∗ per k →∞

Definition 2 (Convergenza globale)Un algoritmo di ottimizzazione converge globalmente ad un punto diminimo x∗ se per ogni scelta di x0 la successione generata a partire dax0, {xk(x0)}, converge a x∗ ovvero:

∀x0 ∈ Rn ⇒ {xk(x0)} → x∗ per k →∞

Metodi Iterativi

Rapidità di Convergenza

Definition 3 (Convergenza Q-lineare)Sia {xk} una sequenza di punti in Rn che converge a x∗. Diciamoche la convergenza è Q-lineare se esiste una costante r ∈ (0, 1) taleper cui

||xk+1 − x∗||||xk − x∗|| ≤ r , per ogni k sufficientemente grande. (1)

Fattore di riduzioneQuesto significa che la distanza dalla soluzione ottima x∗diminuisce ad ogni iterazione di almeno un fattore costante.

Metodi Iterativi


Definition 4 (Convergenza Q-superlineare)La rapidità di convergenza viene detta Q-superlineare se

limk→∞

||xk+1 − x∗||||xk − x∗|| = 0.

Definition 5 (Convergenza Q-quadratica)Si parla di convergenza Q-quadratica quando

||xk+1 − x∗||||xk − x∗||2

≤ M, per ogni k sufficientemente grande,

in cui M è una costante positiva, non necessariamente minore di 1.

Metodi Iterativi


Definition 6 (Convergenza di ordine p)Una sequenza converge con ordine p (con p > 1) se esiste unacostante M tale che

||xk+1 − x∗||||xk − x∗||p ≤ M, per ogni k sufficientemente grande.

Metodi Iterativi

Esercizio 1

Esercizio 1Dimostrare che

1 La successione {1 + 12

k} converge a 1 con rapidità Q-lineare.

2 La successione {1 + k−k} converge a 1 con rapidità Q-superlineare.

3 La successione {1 + 0.52k} converge a 1 con rapidità Q-quadratica.

Dopo aver dimostrato la velocità di convergenza indicata per ciascunasuccessione, usare Matlab per rappresentare graficamente la velocità diconvergenza delle tre successioni.

Metodi di Ottimizzazione - · MetodiIterativi Metodi di Ottimizzazione StefanoGualandi...

Documents

Transcript of Metodi di Ottimizzazione - · MetodiIterativi Metodi di Ottimizzazione StefanoGualandi...