Ottimizzazione numerica
Michele Antonelli
28 Ottobre 2010
Outline
1 Funzioni univariate Golden section search
Introduzione ai metodi di discesa Gradiente discendente
Newton-Raphson
2 Funzioni multivariate Newton-Raphson optim
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.
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)
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).
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.
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
Implementazione in R
golden.Rfunction che implementa il metodo golden section search
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 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|
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
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.
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.
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 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
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
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).
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)
Implementazione in R
gradiente.Rfunction che implementa il metodo del gradiente discendente
valutazione delle funzioni obiettivo main per testare gli esempi
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 una funzione, applicato a f′, in quanto determinare il punto di minimo della funzione f equivale a determinare la radice della derivata prima f′.
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.
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.
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
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.
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-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)).
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
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)
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
Esempi
Esempio 5 f(x, y ) = sin
x2 2 −y42
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)
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).