Michele Antonelli · 2012. 9. 12. · Ottimizzazione numerica I metodi di ottimizzazione consentono...

Funzioni univariateFunzioni multivariate

Ottimizzazione numerica

Michele Antonelli

28 Ottobre 2010

Michele Antonelli Ottimizzazione numerica


Outline

1 Funzioni univariateGolden section searchIntroduzione ai metodi di discesaGradiente discendenteNewton-Raphson

2 Funzioni multivariateNewton-Raphsonoptim



Ottimizzazione numerica

I metodi di ottimizzazione consentono di trovare i punti estremanti(massimi, minimi) di una funzione obiettivo f : R

n → R.

Poiche max f (x) = −min (−f (x)), e sufficiente concentrarsi suimetodi per la ricerca del minimo

minx∈Ω⊆Rn

f (x)

dove Ω e l’insieme definito dai vincoli, se presenti.

Per semplicita, nel seguito supporremo l’esistenza e l’unicita delpunto di minimo x∗ (locale e globale), e tratteremol’ottimizzazione in assenza di vincoli.



Metodi numerici per l’ottimizzazione

Ecco i metodi numerici che vedremo e implementeremo in R:

per funzioni univariate:

golden section searchgradiente discendenteNewton-Raphson

per funzioni multivariate:

Newton-Raphsonoptim (built-in R function)



Golden section searchIntroduzione ai metodi di discesaGradiente discendenteNewton-Raphson

Golden section search

Algoritmo piuttosto semplice e intuitivo per la ricerca del minimodi una funzione all’interno di un intervallo [a, b] con a < b ex∗ ∈ [a, b].

Richiede che la funzione f sia unimodale.

Definizione

Funzione f : R → R e unimodale se esiste m ∈ R tale che f edecrescente per x ≤ m e crescente per x ≥ m.m e quindi il punto di minimo (globale).





Ecco come funziona il metodo golden section search:

1 Si parte considerando l’intervallo [a0, b0] := [a, b] e si fissauna tolleranza ǫ

2 Si restringe iterativamente l’intervallo a [ak+1, bk+1] ⊂ [ak , bk ]in modo che il punto di minimo x∗ continui a cadere al suointerno

3 Ci si arresta quando |bk − ak | < ǫ, e si accetta bk−ak

2come

una buona approssimazione del punto di minimo x∗

Al passo 2, si determinano x1, x2 ∈ [ak , bk ] tali che x1 < x2.Poiche la funzione obiettivo e unimodale e abbiamo suppostoesserci un unico punto di minimo x∗ ∈ [a, b],se succede f (x1) > f (x2) allora significa x∗ ∈ [x1, bk ],altrimenti se f (x1) < f (x2) allora x∗ ∈ [ak , x2].Selezionato l’intervallo corretto, si prosegue in modo iterativo.





Nota

Il nome del metodo e dovuto alla proporzione aurea esistente tra ledistanze dei punti scelti dagli estremi dell’intervallo: x2−x1

x1−a= x1−a

b−x1

Osservazione

pro: non richiede la conoscenza delle derivate

contro: convergenza lenta




Implementazione in R

golden.R function che implementa il metodo golden sectionsearch

valutazione delle funzioni obiettivo

main per testare gli esempi




Esempi

Esempio 1

f (x) = |x − 3.5| + (x − 2)2

Determinare il punto di minimo x∗ ∈ [0, 5].(x∗ = 2.5, f (x∗) = 1.25)

1 2 3 4 5

4

6

8

10

Figure: f (x) = |x − 3.5| + (x − 2)2




Esempi

Esempio 2

f (x) = |x − 3| + sin x − |x − 2|Determinare minimi/massimi e osservare il comportamento delmetodo golden section search al variare dell’intervallo di ricerca.

-2 2 4 6 8

-2

-1

1

2

Figure: f (x) = |x − 3| + sin x − |x − 2|




Esempi

La funzione dell’esempio 2 ha due minimi e due massiminell’intervallo [−3, 9].

A seconda dell’intervallo di ricerca scelto, il metodo converge auno dei minimi:

[−3, 9]: due massimi, due minimi; converge a uno dei minimi

[0, 9]: un massimo, un minimo; converge al minimo

[3, 6]: un minimo; converge a quello




Introduzione ai metodi di discesa

I metodi di discesa sono metodi iterativi che, a partire da uniterato iniziale x0 ∈ R

n, generano una successione di punti xkk∈N

definiti dall’iterazione

xk+1 = xk + αkpk

dove il vettore pk e una direzione di ricerca e lo scalare αk e unparametro positivo chiamato lunghezza del passo (step length) cheindica la distanza di cui ci si muove lungo la direzione pk .




Introduzione ai metodi di discesa

In un metodo di discesa, il vettore pk e il parametro αk sono sceltiin modo da garantire la decrescita della funzione obiettivo f a ogniiterazione:

f (xk+1) < f (xk) ∀k ≥ 0

In particolare, come vettore pk si prende una direzione di discesa,cioe tale che la retta x = xk + αkpk forma un angolo ottuso con ilvettore gradiente ∇f (xk). In questo modo e possibile garantire ladecrescita di f , purche αk sia sufficientemente piccolo.




Scelta della direzione di discesa

A seconda della scelta di pk si hanno diversi metodi di discesa.

Noi vedremo:

metodo del gradiente discendente

metodo di Newton-Raphson




Scelta della lunghezza del passo

Esistono diverse tecniche per la scelta di αk in modo tale dagarantire la convergenza del metodo verso punti stazionari di f .

Step length:

troppo piccola: puo tradursi in una convergenza lenta

troppo grande: rischio di “superare” il punto di minimo




Scelta della lunghezza del passo

Sceglierne una step length costante, o che verifica semplicementela condizione di decrescita f (xk+1) < f (xk), non sempre garantisceconvergenza.

Si puo determinare con:

ricerca in linea esatta

condizioni di Wolfe (condizione di Armijo + condizione dellacurvatura)

sola condizione di Armijo + backtracking




Gradiente discendente

Metodo del gradiente discendente:

xk+1 = xk − δf ′(xk)

direzione di ricerca (gradiente): pk = −f ′(xk)step length: αk = δ costante

Richiede f ∈ C 1 (derivabile con continuita), e conoscenzadell’espressione analitica della derivata prima.

Osservazione

Nome dovuto al fatto che si sceglie come direzione di ricerca quellaopposta al gradiente (derivata prima, nel caso univariato).




Gradiente discendente

Costo computazionale

1 valutazione della derivata prima per iterazione.

Osservazionepro:

converge a punti di minimo (e non genericamente a puntistazionari)non richiede il calcolo della derivata seconda (matrice Hessiananel caso multivariato)

contro:

alto numero di iterazionisensibilita rispetto all’iterato iniziale (se x0 e preso troppolontano dal minimo x∗, e δ e scelta piccola, il metodo puo nonarrivare alla soluzione in tempi ragionevoli)





gradiente.R function che implementa il metodo delgradiente discendente






Esempi

Esempio 3

f (x) = e−x + x4

Determinare il punto di minimo.(x∗ ≈ 0.528252, f (x∗) ≈ 0.667504)

-1.0 -0.5 0.5 1.0

1.5

2.0

2.5

3.0

3.5

Figure: f (x) = e−x + x4




Newton-Raphson

Metodo di Newton-Raphson:

xk+1 = xk −f ′(xk)

f ′′(xk)

direzione di ricerca (Newton): pk = −f ′(xk)/f ′′(xk)step length: αk = 1

Ha la forma del metodo di Newton per la ricerca degli zeri di unafunzione, applicato a f ′, in quanto determinare il punto di minimodella funzione f equivale a determinare la radice della derivataprima f ′.




Newton-Raphson

Il metodo Newton-Raphson e solitamente preferito rispetto algradiente discendente, per la sua velocita, nonostante richiedaf ∈ C 2, f ′′ 6= 0, conoscenza dell’espressione analitica delle derivateprima e seconda, e converga indistintamente a minimi e massimi.

Nota

Se f ha un’espressione semplice, la function deriv consente dicalcolarne simbolicamente le derivate prima e seconda.




Newton-Raphson


A ogni iterazione: valutazione di derivata prima e seconda.

Osservazionepro:

convergenza veloce (quadratica)

contro:

convergenza localealto costo per iterazione

Esistono varianti che rendono il metodo a convergenza globale eche abbassano il costo computazionale evitando di risolvere conmetodi diretti il sistema per la determinazione di pk .





newton optim.R function che implementano il metodo diNewton-Raphson per l’ottimizzazione (uni- e bi-variata)






Esempi

Esempio 3

f (x) = e−x + x4

Determinare il punto di minimo e confrontare il numero diiterazioni effettuate dal metodo di Newton-Raphson con quellerichieste dal metodo del gradiente discendente, visto in precedenza.



Newton-Raphsonoptim

Newton-Raphson

Dall’espansione di Taylor nel caso multidimensionale, il metodo di

Newton-Raphson multivariato assume la forma:

xk+1 = xk − Hf (xk)−1 ∇f (xk)

dove ora xk ∈ Rn e Hf e la matrice Hessiana (derivate seconde) di

f .

direzione di ricerca (Newton): pk = −Hf (xk)−1 ∇f (xk)step length: αk = 1

Osservazione

La direzione di Newton e di discesa ⇔ Hf e definita positiva.



Newton-Raphsonoptim

Newton-Raphson

Il metodo di Newton-Raphson multivariato richiede f ∈ C 2, econoscenza dell’espressione analitica del gradiente e della matriceHessiana.

Nota

Se f ha un’espressione semplice, la function deriv consente dicalcolarne simbolicamente il gradiente e la matrice Hessiana.


A ogni iterazione: valutazione di gradiente, Hessiana e risoluzionedel sistema n × n

Hf (xk) pk = −∇f (xk)

per la determinazione di pk (costo O(n3)).



Newton-Raphsonoptim


newton optim.R function che implementano il metodo diNewton-Raphson per l’ottimizzazione (uni- e bi-variata)





Newton-Raphsonoptim

optim

optim e una R-function per l’ottimizzazione di funzioni anche dipiu variabili.

L’utente puo scegliere quale metodo usare, tra:

Nelder-Mead (default): robusto ma relativamente lento

BFGS (quasi-Newton)

CG (gradiente coniugato)



Newton-Raphsonoptim

Esempi

Esempio 4

f (x , y) = 12

(

0.001(x − 1)2 + (x2 − y)2)

(funzione di tipo Rosenbrock)Determinare il punto di minimo. (x∗ = (1, 1))

-2

-1

0

1

2

-2

-1

0

1

2

0

5

10

Figure: f (x , y) = 12

(

0.001(x − 1)2 + (x2 − y)2)



Newton-Raphsonoptim

Esempi

Esempio 5

f (x , y) = sin(

x2

2− y2

4

)

cos (2x − ey )

Determinare i punti di minimo e massimo.

-2

-1

0

1

2-2

-1

0

1

2

-1.0

-0.5

0.0

0.5

1.0

Figure: f (x , y) = sin(

x2

2− y2

4

)

cos (2x − ey )Michele Antonelli Ottimizzazione numerica


Newton-Raphsonoptim

Esempi

La funzione dell’esempio 5 presenta molti punti di minimo e dimassimo, pertanto scegliendo iterati iniziali diversi (e metodidiversi), si puo arrivare a soluzioni diverse (a seconda dellagrandezza dei bacini di attrazione dei punti stazionari).


Michele Antonelli · 2012. 9. 12. · Ottimizzazione numerica I metodi di ottimizzazione consentono...

Documents

Transcript of Michele Antonelli · 2012. 9. 12. · Ottimizzazione numerica I metodi di ottimizzazione consentono...