Introduzione alleFunzioni di Ottimizzazione

di MatlabMetodi Numerici

1. Toolbox di Ottimizzazione

Matlab ha tre principali funzioni per resolvere problem di ottimizzazione:

1. fminunc: trova il minimo di un problema non vincolato(“unc-onstrained”), usando metodi che usano o stimano ilgradiente

2. fminsearch: trova il minimo un problema non vincolato, senza usare nessuna informazione sul gradiente (“derivate free methods”)

3. fmincon: risolve un problema di ottimizzazione vincolata

4. fzero: trovi gli zeri di una funzione non lineare (può essereusata per trovare i punti stazionari…)

2. Usare la funzione fminunc

Sintassi:

[xmin, f_xmin] = fminunc(f, x0, options)

Input:

1. f: è la funzione obiettivo

2. x0: è il punto di iniziale da cui iniziare la ricerca

3. options: opzioni definite dall’utente che determinano iltipo di algoritmo usato e diversi parametri numerici

Output minimale:

1. xmin: punto di minimo relativo trovato

2. fval: funzione obiettivo valutata in xmin

2. Funzione F2.mfunction [z,g,h] = F2(X)

x = X(1);

y = X(2);

z = x^2 + y^2;

if nargout > 1

g(1) = 2*x; % Gradiente

g(2) = 2*y;

if nargout > 2

h(1,1) = 2; % Hessiano

h(2,2) = 2;

h(1,2) = 0;

h(2,1) = h(1,2);

end

end

end

2. Usare la funzione fminunc

Sintassi:

[xmin, f_xmin] = fminunc(f, x0, options)

Esempio: Usando la funzione F2.m vista la volta scorsa, provare:

>> [xbar, f_xbar] = fminunc(@F2, [-2,0])

xbar =

1.0e-07 *

0 0.1490

f_xbar =

-2.2204e-16

2. Usare la funzione fminuncSintassi:

[xmin,fval,exitflag,output,grad,hessian] =

fminunc(f, x0, options)

Esempio: Usando la funzione F2.m sul sito del corso provare:

>> [x,fval,exitflag,output,grad,hessian]=fminunc(@F2,[2,0])

PROVARE!

NOTA: Leggere sempre la documentazione online:

https://it.mathworks.com/help/optim/ug/fminunc.html

ATTENZIONE A MATLAB !

In una certa versione di Matlab, successiva a quellainstallato nelle aule B2 e C2/C3, è stato cambiato ilmodo di passare le “options” al toolbox diottimizzazione.

Nella documentazione online di Matlab trovate ilnuovo modo, ma abituatevi ad usare il vecchio, inquanto l’esame sarà sui computer delle aule B2 eC2/C3.

3.1 Opzioni per fminunc

• Opzioni per vedere il processo di ottimizzazione:

>> options = optimset('Display','iter’)

Esempio: Usando la funzione F3.m utilizzata per l’esercizio del Matlab Grader:

>> x0 = [0,0]; # Dopo provare con x0=[1,2]

>> [x,fval,exitflag,output,Gk,Hk] = fminunc(@F3,x0,options)

Iteration,Func-count,f(x),Step-size,1st order optimality

PROVARE!

3.2 Opzioni per fminunc

• Opzioni per vedere il critero di arresto:

>> opts = optimset(‘MaxFunEvals’,200,’MaxIter’,200’);

>> opts = optimset(opts,’TolFun’,1e-7,’TolX’,1e-7);

3.3 Opzioni per fminunc

Opzioni per selezionare il metodo iterativo di ottimizzazione:

1. Steepest Descent (metodo del gradiente, massima discesa), senza uso delgradiente calcolato nella funzione obiettivo implementata da voi:

options=optimset(’LargeScale’,’off’,’GradObj’,’off’,

’HessUpdate’,’steepdesc’);

Se volete fare usare il gradiente che avete implementato nella funzione obiettivo:

options=optimset(’LargeScale’,’off’,’GradObj’,’on’,

’HessUpdate’,’steepdesc’);

3.4 Opzioni per fminunc

Opzioni per vedere la scelta del metodo di soluzione:

2. BFGS: Algoritmo di Broyden–Fletcher–Goldfarb–Shanno

options=optimset(’LargeScale’,’off’,’GradObj’,’on’,

’HessUpdate’,’bfgs’);

3. DFP: Algoritmo di Davidon–Fletcher–Powell

options= optimset(’LargeScale’,’off’,’GradObj’,’on’,

’HessUpdate’,’dfp’);

4. Trust-Region

options = optimset(’LargeScale’,’on’,’GradObj’,’on’,

’Hessian’,’on’); (oppure ‘off’)

Esercizi Preliminari su fminunc

• Utilizzando la funzione F2.m definite la volta scorsa, provare ad utilizzare la funzione fminunc con le diverse opzioni appena vista.

• Controllare i valori del gradiente e dell’hessiana, e commentare il tipo di punti stazionari trovati

• Ripetere i passi sopra con la funzione F3.m, quelladefinita nell’esercizio sul Matlab Grader della voltascorsa.

Esercizio 4: Da svolgere in aula Si consideri la funzione seguente (funzione di Rosenbrock):

f(x,y) = 100(y-x2)2 + (x-1)2

1. Scrivere il gradiente e l’Hessiana della funzione data

2. Scrivere una funzione Matlab che calcoli in un dato punto:a) Il valore di f(x,y)b) Il gradiente di f(x,y)c) La matrice Hessiana di f(x,y)

3. Tracciare il grafico della superficie di f(x,y).

4. Visualizzare le curve di livello.

5. A partire dal punto x0=[-1,2]T, trovare eventuali punti stazionari con la funzione fminunc funzione, utilizzando i quattro metodi visti in precedenza (gradiente, DFP, BFGS, e Trust Region). Cosa si osserva sullavelocità di convergenza?

6. Classificare l’eventuale punto stazionario (minimo, massimo o sella?)

Esercizio 5: Da svolgere in aula Si consideri la funzione seguente (appello del 27/02/2017):

f(x,y) = a x2 + b y2 - c log(x+y)

1. Scrivere il gradiente e l’Hessiana della funzione data

2. Scrivere una funzione Matlab che, usando a = 1, b = 2, c = 2, calcoli in un dato punto:a) Il valore di f(x,y)b) Il gradiente di f(x,y)c) La matrice Hessiana di f(x,y)

3. Tracciare il grafico della superficie di f(x,y).

4. Visualizzare le curve di livello

5. A partire dal punto x0=[0.8,0.8]T, utilizzando il metodo del gradiente, trovare eventuali punti stazionari con la funzione fminunc. Si usino le seguenti tolleranze: TolFun=1.e-12 e TolX=1.e-12

6. Classificare gli eventuali punti stazionari (minimo, massimo o sella?)

Esercizio 6: Facoltativo

1. Scrivere il gradiente e l’Hessiana della funzione data

2. Scrivere una funzione Matlab che calcoli in un datopunto:a) Il valore di f(x,y)b) Il gradiente di f(x,y)c) La matrice Hessiana di f(x,y)

3. Tracciare il grafico della superficie di f(x,y).

4. Visualizzare le curve di livello

5. A partire dal punto x0 trovare eventuali puntistazionari con la funzione fminunc.

6. Classificare gli eventuali punti stazionari (minimo, massimo o sella?)

Si consideri la funzione seguente (demo online delle slides):

f(x,y) = (x2+y−11)2 + (x+y2−7)2