• Non ci sono risultati.

Golden section search

N/A
N/A
Protected

Academic year: 2022

Condividi "Golden section search"

Copied!
32
0
0

Testo completo

(1)

Ottimizzazione numerica

Michele Antonelli

28 Ottobre 2010

(2)

Outline

1 Funzioni univariate Golden section search

Introduzione ai metodi di discesa Gradiente discendente

Newton-Raphson

2 Funzioni multivariate Newton-Raphson optim

(3)

Ottimizzazione numerica

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

Poich´e max f (x) = − min (−f (x)), `e sufficiente concentrarsi sui metodi per la ricerca del minimo

x ∈Ω⊆Rmin nf(x)

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

Per semplicit`a, nel seguito supporremo l’esistenza e l’unicit`a del punto di minimo x (locale e globale), e tratteremo

l’ottimizzazione in assenza di vincoli.

(4)

Metodi numerici per l’ottimizzazione

Ecco i metodi numerici che vedremo e implementeremo in R:

per funzioni univariate:

golden section search gradiente discendente Newton-Raphson per funzioni multivariate:

Newton-Raphson

optim(built-in R function)

(5)

Golden section search

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

Richiede che la funzione f sia unimodale.

Definizione

Funzione f : R → R `e unimodale se esiste m ∈ R tale che f `e decrescente per x ≤ m e crescente per x ≥ m.

m `e quindi il punto di minimo (globale).

(6)

Golden section search

Ecco come funziona il metodo golden section search:

1 Si parte considerando l’intervallo [a0, b0] := [a, b] e si fissa una 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 suo interno

3 Ci si arresta quando |bk − ak| < ǫ, e si accetta bk−a2 k come una buona approssimazione del punto di minimo x

Al passo 2, si determinano x1, x2 ∈ [ak, bk] tali che x1 < x2. Poich´e la funzione obiettivo `e unimodale e abbiamo supposto esserci 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.

(7)

Golden section search

Nota

Il nome del metodo `e dovuto alla proporzione aurea esistente tra le distanze dei punti scelti dagli estremi dell’intervallo: xx2−x1

1−a = xb−x1−a

1

Osservazione

pro: non richiede la conoscenza delle derivate contro: convergenza lenta

(8)

Implementazione in R

golden.Rfunction che implementa il metodo golden section search

valutazione delle funzioni obiettivo main per testare gli esempi

(9)

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

(10)

Esempi

Esempio 2

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

Determinare minimi/massimi e osservare il comportamento del metodo 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|

(11)

Esempi

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

A seconda dell’intervallo di ricerca scelto, il metodo converge a uno 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

(12)

Introduzione ai metodi di discesa

I metodi di discesa sono metodi iterativi che, a partire da un iterato iniziale x0∈ Rn, generano una successione di punti {xk}k∈N

definiti dall’iterazione

xk+1= xk + αkpk

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

(13)

Introduzione ai metodi di discesa

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

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

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

(14)

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

(15)

Scelta della lunghezza del passo

Esistono diverse tecniche per la scelta di αk in modo tale da garantire la convergenza del metodo verso punti stazionari di f . Step length:

troppo piccola: pu`o tradursi in una convergenza lenta troppo grande: rischio di “superare” il punto di minimo

(16)

Scelta della lunghezza del passo

Sceglierne una step length costante, o che verifica semplicemente la condizione di decrescita f (xk+1) < f (xk), non sempre garantisce convergenza.

Si pu`o determinare con:

ricerca in linea esatta

condizioni di Wolfe (condizione di Armijo + condizione della curvatura)

sola condizione di Armijo + backtracking

(17)

Gradiente discendente

Metodo del gradiente discendente:

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

Richiede f ∈ C1 (derivabile con continuit`a), e conoscenza dell’espressione analitica della derivata prima.

Osservazione

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

(18)

Gradiente discendente

Costo computazionale

1 valutazione della derivata prima per iterazione.

Osservazione pro:

converge a punti di minimo (e non genericamente a punti stazionari)

non richiede il calcolo della derivata seconda (matrice Hessiana nel caso multivariato)

contro:

alto numero di iterazioni

sensibilit`a rispetto all’iterato iniziale (se x0`e preso troppo lontano dal minimo x, e δ `e scelta piccola, il metodo pu`o non arrivare alla soluzione in tempi ragionevoli)

(19)

Implementazione in R

gradiente.Rfunction che implementa il metodo del gradiente discendente

valutazione delle funzioni obiettivo main per testare gli esempi

(20)

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

(21)

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 una funzione, applicato a f, in quanto determinare il punto di minimo della funzione f equivale a determinare la radice della derivata prima f.

(22)

Newton-Raphson

Il metodo Newton-Raphson `e solitamente preferito rispetto al gradiente discendente, per la sua velocit`a, nonostante richieda f ∈ C2, f′′6= 0, conoscenza dell’espressione analitica delle derivate prima e seconda, e converga indistintamente a minimi e massimi.

Nota

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

(23)

Newton-Raphson

Costo computazionale

A ogni iterazione: valutazione di derivata prima e seconda.

Osservazione pro:

convergenza veloce (quadratica) contro:

convergenza locale alto costo per iterazione

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

(24)

Implementazione in R

newton optim.R function che implementano il metodo di Newton-Raphson per l’ottimizzazione (uni- e bi-variata) valutazione delle funzioni obiettivo

main per testare gli esempi

(25)

Esempi

Esempio 3 f(x) = e−x+ x4

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

(26)

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.

(27)

Newton-Raphson

Il metodo di Newton-Raphson multivariato richiede f ∈ C2, e conoscenza dell’espressione analitica del gradiente e della matrice Hessiana.

Nota

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

Costo computazionale

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

Hf(xk) pk = −∇f (xk) per la determinazione di pk (costo O(n3)).

(28)

Implementazione in R

newton optim.R function che implementano il metodo di Newton-Raphson per l’ottimizzazione (uni- e bi-variata) valutazione delle funzioni obiettivo

main per testare gli esempi

(29)

optim

optim `e una R-function per l’ottimizzazione di funzioni anche di pi`u variabili.

L’utente pu`o scegliere quale metodo usare, tra:

Nelder-Mead (default): robusto ma relativamente lento BFGS (quasi-Newton)

CG (gradiente coniugato)

(30)

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 ) = 1 0.001(x − 1)2+ (x2− y )2

(31)

Esempi

Esempio 5 f(x, y ) = sin

x2 2y42

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 y2

cos (2x − ey)

(32)

Esempi

La funzione dell’esempio 5 presenta molti punti di minimo e di massimo, pertanto scegliendo iterati iniziali diversi (e metodi diversi), si pu`o arrivare a soluzioni diverse (a seconda della grandezza dei bacini di attrazione dei punti stazionari).

Riferimenti

Documenti correlati

Sia f (x) funzione derivabile con derivata continua e positiva in un intervallo aperto I, convessa in I. Ne segue quindi che la funzione `e strettamente crescente e ammette un

se, inoltre, un marinaio si muove verso oriente, sulla nave, con una velocità pari ad una parte: allora il marinaio si muoverà di moto vero e assoluto nello spazio immobile,

Solo a questo punto – si noti il richiamo alla coppia prove- spiegazioni, che trovavamo già nel Discours cartesiano, può essere avviata la fase di “sintesi”, nella quale –

Fondare l’Analisi in questo modo sulle quantit` a finite, e investigare le ragioni prime e ultime di quantit` a finite nascenti o evanescenti ` e in sintonia con la Geometria

Amid all the turmoil, Newton, now 23, returned to the family farm where he develop three laws of motion, a theory of coloured light, his theory of fluxions (calculus), and a

Whewell, però, era un grande ammiratore di Newton: il suo obiettivo era di giustificare Newton, non solo perché credeva che la teoria di Newton fosse vera, ma anche perché

Era stato quindi lo stesso Halley a spingere Newton a sottomettere il suo lavoro alla Royal Society e gli aveva fatto anche una presentazione di supporto... Il primo libro si apre

Fu in quell'occasione che Newton scrisse una monografia sotto forma di lettera indirizzata a Oldenburg (il segretario della Royal Society) in cui descrisse tutti gli esperimenti