Il Toolbox di ottimizzazione di Matlab
• I Toolbox di Matlab sono pacchetti software utili per risolvere problemi specifici. Questi pacchetti non fanno parte del kernel vero e proprio di Matlab.
• Si tratta di codice scritto appositamente per risolvere problemi in moltissimi
campi dell’ingegneria, della matematica, della fisica, dell’economia, della
finanza, e altro ancora.
• In questa presentazione vedremo in dettaglio alcune funzioni dell’Optimization
Problema di ottimizzazione libera
• Consideriamo un esempio di minimizzazione libera di una funzione di pi`u variabili. • Dato il vettore x = [x1, x2, x3] T e la funzione f(x) = x21 + x 2 2x3, vogliamo
risolvere il seguente problema di ottimizzazione: min x∈R3 {f (x)} = min x∈R3 x2 1 + x 2 2x3 .
• E’ possibile specificare anche il gradiente della funzione da minimizzare al fine di ottenere prestazioni migliori. In assenza di alcuna specificazione, il gradiente `e calcolato automaticamente in modo numerico.
• Qui di seguito `e riportato il codice Matlab necessario per risolvere il problema di minimizzazione considerato mediante la funzione fminunc.
• Occorre anzitutto indicare la funzione da minimizzare in un file ffree.m:
1 function retval = ffree ( x ) 2 % Funzione da m i n i m i z z a r e
Problema di ottimizzazione vincolata
• Successivamente occorre scrivere il codice necessario per la minimizzazione:
1 % Esempio di m i n i m i z z a z i o n e libera di una funzione di piu ’ variabili
2
3 % Punto iniziale dell ’ algoritm o di o t t i m i z z a z i o n e
4 x0 = [10; 10; 10];
5 % Opzioni di m i n i m i z z a z i o n e
6 options = optimset (’ L a r g e S c a l e ’, ’ off ’, ... % Non sono u t i l i z z a t i algoritmi ’ Large Scale ’
7 ’ M a x F u n E v a l s ’, 1000 , ... % Numero massimo v a l u t a z i o n i della funzione
8 ’ GradObj ’, ’ off ’, ... % Gradiente calcolat o n u m e r i c a m e n t e
9 ’ TolFun ’, 1e -9 , ... % T o l l e r a n z a sul valore della funzione
10 ’ TolX ’, 1e -9 , ... % T o l l e r a n z a sul valore di x
11 ’ Display ’,’ iter ’ ... % V i s u a l i z z a z i o n e risultati a ogni i t e r a z i o n e
12 );
13 % M i n i m i z z a z i o n e vera e propria
• Al prompt dei comandi viene visualizzato il testo seguente:
1 >> e s e m p i o F r e e
2 First - order
3 Iteration Func - count f ( x ) Step - size o p t i m a l i t y
4 0 4 1100 200 5 1 8 867.51 0.005 171 6 2 12 143.046 1 44.6 7 3 16 64.7454 1 15.6 8 4 20 47.3196 1 13.6 9 5 24 37.0588 1 11.6 10 6 28 15.7725 1 14.4 11 7 32 4.23781 1 9.94 12 8 36 0.508438 1 3.42 13 9 40 0.0114608 1 0.326 14 10 44 0 . 0 0 0 1 0 4 1 9 8 1 0.02 15 11 48 5.95782 e -07 1 0.00285 16 12 52 3.00695 e -10 1 8.52 e -05 17 13 56 8.15836 e -14 1 1.03 e -06 18 14 60 3.85541 e -16 1 1.85 e -07 19
22 O p t i m i z a t i o n completed because the size of the gradient is less than 23 the selected value of the function tolerance .
24
25 < stopping criteria details > 26 27 xopt = 28 -0.0000 29 -0.0000 30 6.1721 31 32 fval = 33 3.8554 e -16 34 35 exitFlag = 36 1
• Alle varie iterazioni del processo di ottimizzazione vengono mostrate diverse
informazioni, tra cui il valore della funzione da minimizzare, il valore del
gradiente della funzione da minimizzare, e il numero di volte in cui la funzione da minimizzare viene valutata.
• La procedura di minimizzazione ha fornito come ottimo x∗ = 0 0 6.17 , f(x ∗ ) = 0
• La procedura `e terminata con exitFlag pari a 1, ossia a causa del raggiunto limite di tolleranza sulla norma del gradiente della funzione obiettivo.
• Esistono altri valori che exitFlag pu`o assumere, corrispondenti ad altre condizioni che hanno interrotto la procedura di ricerca del minimo.
Problema di ottimizzazione vincolata
• Consideriamo un esempio di minimizzazione vincolata di una funzione di pi`u variabili.
• Dato il vettore x = [x1, x2, x3] T
e la funzione f(x) = −x1x2x3, vogliamo
risolvere il seguente problema di ottimizzazione: min
x
{f (x)} = min
x
{−x1x2x3}
con vincoli 0 ≤ x1 + 2x2 + 2x3 ≤ 72 e x21x2 ≥ 0. Si tratta di due vincoli
lineari di disuguaglianza e di un vincolo non lineare di disuguaglianza.
• E’ possibile specificare anche il gradiente della funzione da minimizzare al fine di ottenere prestazioni migliori. In assenza di alcuna specificazione, il gradiente
• Qui di seguito `e riportato il codice Matlab necessario per risolvere il problema di minimizzazione considerato mediante la funzione fmincon.
• Occorre anzitutto indicare la funzione da minimizzare in un file fconstr.m:
1 function retval = fconstr ( x ) 2 % Funzione da m i n i m i z z a r e
3 retval = -x (1)* x (2)* x (3);
• Occorre poi indicare la funzione dei vincoli non lineari di uguaglianza e disuguaglianza in un file nonlinconstr.m:
1 function [c , ceq ] = n o n l i n c o n s t r ( x )
2 % Funzione dei vincoli non lineari di d i s u g u a g l i a n z a e di u g u a g l i a n z a
3 % Vincoli di d i s u g u a g l i a n z a non lineari ( visti come c <=0)
4 c = -x (1)^2* x (2);
5 % Vincoli di u g u a g l i a n z a non lineari ( visti come ceq ==0)
Problema di ottimizzazione vincolata
• Successivamente occorre scrivere il codice necessario per la minimizzazione:
1 % Esempio di m i n i m i z z a z i o n e vincolata di una funzione di piu ’ variabili
2
3 % Matrici per indicare i vincoli lineari di d i s u g u a g l i a n z a Ax <= b
4 A = [ -1 -2 -2; 1 2 2]; 5 b = [0; 72];
6 % Punto iniziale dell ’ algoritm o di o t t i m i z z a z i o n e
7 x0 = [10; 10; 10];
8 % Opzioni di m i n i m i z z a z i o n e
9 options = optimset (’ L a r g e S c a l e ’, ’ off ’, ... % Non sono u t i l i z z a t i algoritmi ’ Large Scale ’
10 ’ M a x F u n E v a l s ’, 1000 , ... % Numero massimo v a l u t a z i o n i della funzione
11 ’ GradObj ’, ’ off ’, ... % Gradiente calcolat o n u m e r i c a m e n t e
12 ’ TolFun ’, 1e -9 , ... % T o l l e r a n z a sul valore della funzione
13 ’ TolX ’, 1e -9 , ... % T o l l e r a n z a sul valore di x
14 ’ TolCon ’, 1e -6 , ... % T o l l e r a n z a sulla v i o l a z i o n e dei vincoli
15 ’ Display ’,’ iter ’ ... % V i s u a l i z z a z i o n e risultati a ogni i t e r a z i o n e
16 );
17 % M i n i m i z z a z i o n e vera e propria
• Al prompt dei comandi viene visualizzato il testo seguente:
1 >> e s e m p i o C o n s t r a i n e d 2
3 Max Line search D i r e c t i o n a l First - order
4 Iter F - count f ( x ) c o n s t r a i n t s t e p l e n g t h d e r i v a t i v e o p t i m a l i t y Procedure 5 0 4 -1000 -22 6 1 9 -1587.17 -11 0.5 642 584 7 2 13 -3323.25 0 1 -1.9 e +003 161 8 3 21 -3325.4 0 0.0625 108 57.5 Hessian modified 9 4 25 -3337.65 -1.421 e -014 1 -10.7 56.7 10 5 29 -3393.66 0 1 -34.4 43.8 11 6 33 -3436.73 0 1 -22.2 37 12 7 37 -3452.42 0 1 -5.47 20.4 13 8 41 -3455.64 0 1 -1.37 7.1 14 9 45 -3456 0 1 -0.0136 0.556 15 10 49 -3456 0 1 -3.22 e -005 0.0229 16 11 53 -3456 0 1 -4.06 e -008 0.000684 Hessian modified 17 12 57 -3456 0 1 -8.15 e -012 9.94 e -006 Hessian modified 18 O p t i m i z a t i o n t e r m i n a t e d : magnitude of d i r e c t i o n a l d e r i v a t i v e in search
19 direction less than 2* options . TolFun and maximum c o n s t r a i n t violation 20 is less than options . TolCon .
22 Active i n e q u a l i t i e s ( to within options . TolCon = 1 e -006): 23 lower upper ineqlin i n e q n o n l i n
24 2 25 xopt = 26 24.0000 27 12.0000 28 12.0000 29 30 fval = 31 -3.4560 e +003 32 33 exitFlag = 34 5
• Alle varie iterazioni del processo di ottimizzazione vengono mostrate diverse
informazioni, tra cui il valore della funzione da minimizzare, il valore del
gradiente della funzione da minimizzare, e il numero di volte in cui la funzione da minimizzare viene valutata.
• La procedura di minimizzazione ha fornito come ottimo x∗ = 24 12 12 , f(x ∗ ) = −3.45 · 103
• La procedura `e terminata con exitFlag pari a 5, ossia a causa del raggiunto limite di tolleranza sulla derivata direzionale e sulla violazione dei vincoli.
• Esistono altri valori che exitFlag pu`o assumere, corrispondenti ad altre condizioni che hanno interrotto la procedura di ricerca del minimo.