Optimization Toolbox

Università degli studi di Salerno
Facoltà di Scienze Matematiche Fisiche e Naturali
Optimization Toolbox di
MATLAB
Tesina di Ottimizzazione
Studente:
Prof. Giancarlo Raiconi
Gianluca Carbone
0522500116
Anno Accademico 2011/2012
1
INTRODUZIONE…
Il presente lavoro riguarda lo studio delle più
importanti funzioni che il tool mette a
disposizione, degli algoritmi utilizzati e
applicazione del software a problemi di
test reperibili in rete.
Optimization Toolbox di MATLAB
2
…INTRODUZIONE
Nello specifico ho lavorato su :
• Comprensione generale del tool Optimization Toolbox;
• Utilizzo del tool su problemi di nonlineare nonvincolata e
di minimizzazione unidimensionale;
• Utilizzo del tool su problemi riguardo i minimi quadrati
lineari e nonlineari.
Optimization Toolbox di MATLAB
3
Il tool nel complesso…
Una collezione di funzioni che estendono la capacità
dell'ambiente di calcolo numerico di Matlab. La toolbox
include procedure per molti tipi di ottimizzazione tra
cui:
•
•
•
•
•
•
•
Minimizzazione non lineare non vincolata;
Minimizzazione non lineare vincolata, tra cui problemi goal attainment,
problemi minimax e problemi di minimizzazione semi- infinita;
Programmazione quadratica e lineare;
Minimi quadrati e curve-fitting non lineari;
Risoluzione di sistemi di equazioni non lineari;
Minimi quadrati lineari vincolati;
Problemi su larga scala sparsi e strutturati.
Optimization Toolbox di MATLAB
4
ALGORITMI…
Due classi di algoritmi:
1. Medium – Scale ( or Standard) algorithm :
- Minimizzazione non vincolata : metodi di ricerca del simplesso Nelder - Mead e il
metodo Quasi-Newton di BFGS( Broyden-Fletcher-Goldfarb-Shanno );
- Minimizzazione vincolata (minimax, goal attainment e ottimizzazione semi – infinita )
: sono usate variazioni della programmazione quadratica sequenziale (SQP);
- Minimi quadrati non lineari : metodi di Gauss – Newton e Levemberg – Marquardt;
- Equazioni non lineari : risoluzione anche attraverso l’algoritmo Trust – Region
Dogleg;
Optimization Toolbox di MATLAB
5
…ALGORITMI
2. Large Scale algorithm :
- Tutti gli algoritmi su larga scala, eccetto la programmazione lineare, sono metodi
Trust – Region.
- I problemi vincolati sono risolti usando metodi di Newton Riflessivo.
- I problemi con vincoli di eguaglianza sono risolti con i metodi del Gradiente
Coniugato Precondizionato;
- Per individuare il passo corrente per risolvere sistemi lineari , si possono
utilizzare risolutori sparsi o risolutori sparsi diretti.
- Il metodo di programmazione lineare è una variante dell’algoritmo predictorcorrector di Mehrotra , un metodo primale duale interior-point.
L’idea di base dei metodi di “ trust - region” è di determinare la direzione e l’ampiezza
dello spostamento da effettuare a partire dal punto corrente x , in modo da
minimizzare un modello quadratico della funzione obiettivo in una regione sferica di
centro x.
Optimization Toolbox di MATLAB
6
FUNZIONI…
Il tool mette a disposizione tre categorie di funzioni :
1. Minimization : minimizzazione scalare(fminbnd),
minimizzazione non vincolata (fminunc, fminsearch), linear
programming (linprog), programmazione quadratica (quadprog),
minimizzazione vincolata (fmincon), goal attainment( fgoalattain),
minimax (fminimax), minimizzazione semi – infinita (fseminf);
2. Rioluzione di equazioni : equazioni lineari ( \ (slash)),
equazioni non lineari di una variabile (fzero), equazioni non lineari
(fsolve);
Optimization Toolbox di MATLAB
7
…FUNZIONI
3. Minimi quadrati (curve fitting) : minimi quadrati lineari
( \(slash)), minimi quadrati lineari non negativi (lsqnonneg), minimi
quadrati lineari vincolati (lsqlin), minimi quadrati non lineari
(lsqnonlin), curve fitting (lsqcurvefit).
Il curve fitting è il processo di costruzione di una curva o di una funzione
matematica, che abbia la migliore corrispondenza ad una serie di punti
assegnati, possibilmente soggetti a limitazioni. Il curve fitting può implicare
sia l'interpolazione, dove è richiesta un'esatta corrispondenza con i punti
dati, o lo spianamento, dove viene costruita una funzione piana che
combaci approssimativamente con i dati.
Optimization Toolbox di MATLAB
8
Tornando agli algoritmi
Qualche algoritmo standard :
Gradient methods : i metodi del gradiente usano informazioni circa la
pendenza della funzione per dettare una direzione di ricerca dove si ritiene
che sia il minimo. Il più semplice di questi è il metodo di steepest
descent(gradiente) in cui viene eseguita una ricerca in una direzione, -f(x),
dove f(x) è il gradiente della funzione obbiettivo. Questo metodo è
inefficiente quando la funzione da minimizzare ha lunghe curvature strette.
Quasi – Newton methods : utilizza le informazioni del gradiente,
costruisce le informazioni della curvatura ad ogni iterazione per formulare il
problema del modello quadratico della forma:
H matrice Hessiana, c vettore costante, b costante
Implementazione consiste di due fasi:
-
Determinazione di una direzione di ricerca( aggiornamento Hessiano);
Procedure di Line Search.
Optimization Toolbox di MATLAB
9
Tornando agli algoritmi
…Qualche algoritmo Standard
Quasi – Newton : Il metodo di tipo-Newton (come opposto ai metodi Quasi
-Newton) calcola H direttamente e procede in una direzione di discesa per
localizzare il minimo dopo un numero di iterazioni. Calcolare H numericamente
comporta un grande numero di computazioni. I metodi Quasi -Newton evitano
questo usando il comportamento osservato di f(x) e ∆f(x) per costruire le
informazioni di curvatore per fare un approssimazione di H usando un’
appropriata tecnica di aggiornamento.
Tra le tecniche di aggiornamento dell’Hessiano vi è BFGS:
dove
Optimization Toolbox di MATLAB
10
ALGORITMI
… ancora qualche algoritmo Standard
Ottimizzazione con i minimi quadrati
Metodo Gauss – Newton : è ottenuta una direzione di ricerca D di
k ad ogni iterazione k, cioè una soluzione del problema dei minimi
quadrati. La direzione di ricerca D può essere utilizzata come parte
di una strategia di ricerca di linea per garantire che ad ogni
iterazione la funzione f(x) decrementa. Questo metodo ha limiti con
valori molto grandi nell’equazione .
J matrice Jacobiaba, G vettore gradiente, H matrice hessiana
Problemi risolti nel metodo di Levemberg-Marquardt.
Levemberg – Marquardt : trova una soluzione di un insieme
lineare di equazioni, usa una direzione di ricerca che è un incrocio
tra la direzione di Gauss – Newton e Steepest Descent.
Optimization Toolbox di MATLAB
11
ALGORITMI
Algoritmi su Larga scala…
Trust – Region : esempio minimizzare f(x). Supponiamo di essere in un
punto x in uno spazio n e vogliamo migliorare ad un valore di funzione
inferiore. L’idea di base è di approssimare f ad una semplice funzione q, che
riflette adeguatamente il comportamento della funzione f in un vicino N
intorno al punto x. Questo punto è detto trust – region. Il punto viene
aggiornato solo se la soluzione è migliorata.
Preconditioned Conjugate Gradients : risolvere grandi sistemi definiti
positivi simmetrici di equazioni lineari o l’equivalente problema di
programmazione quadratica.
Consiste nel decomporre un problema di minimo quadratico n – dimensionale in n problemi
monodimensionali mediante l’introduzione di direzioni coniugate. Leggermente più
complesso di steepest descent ma molto più veloce nella convergenza.
Optimization Toolbox di MATLAB
12
ALGORITMI
…algoritmi su Larga scala
Minimi quadrati non lineari :
Il metodo di base usato per risolvere questo problema è lo stesso come nel
caso generale descritto per Trust Region. Tuttavia la struttura del
problema dei minimi quadrati non lineari è sfruttata per migliorare
l’efficienza.
Minimi quadrati lineari :
Ogni iterazione implica la soluzione approssimata di un sistema lineare grande (di
ordine n dove n è la lunghezza di x). Il metodo dei gradienti è utilizzato per
risolvere approssimativamente l’equazione normale, ad esempio,
Il metodo Trust-region è utlizzato per individuare una direzione di ricerca
Optimization Toolbox di MATLAB
13
FUNZIONI ANALIZZATE
Le funzioni che sono state analizzate:
fminsearch : trova il minimo di una funzione multi-variabile non lineare non vincolata ;
fminunc : trova il minimo di una funzione multi variabile non lineare non vincolata ;
fmincon : trova il minimo di una funzione multi-variaible non lineare vincolata
lsqlin : risolve il problema dei minimi quadrati lineari ;
lsqnonlin : risolve problemi dei minimi quadrati non lineari (data-fitting non lineari).
Per ognuna delle funzioni vi sono diverse sezioni, in particolare :
scopo
descrizione
note particolari
algoritmi che utilizzano
Optimization Toolbox di MATLAB
14
fminsearch
[x,fval,exitflag,output] = fminsearch(fun,x0,options,P1,P2,…)
Input
fun -> funzione da minimizzare
x0 -> punto di inizio
options -> permette di modificare i parametri di ottimizzazione
P1,P2 -> argomenti addizionali passati a fun.
Output
x -> minimo locale della funzione descritta in fun
fval -> valore della funzione obbiettivo alla soluzione x
exitflag -> descrive la condizione di uscita
output -> contiene informazioni circa l’ottimizzazione (iterazioni, algoritmo, ecc).
Algoritmi
Usa il metodo di ricerca del simplesso; potrebbe solo dare una soluzione locale;
minimizza solo su numeri reali ( ha bisogno di scomporre variabili complesse).
Optimization Toolbox di MATLAB
15
fminunc
[x, fval, exitflag, output, grad, hessian]= fminunc(fun, x0, options, P1,
P2,…);
Input
fun -> funzione da minimizzare
x0 -> punto di inizio
options -> permette di modificare i parametri di ottimizzazione
P1,P2 -> argomenti addizionali passati a fun.
Output
x -> minimo locale della funzione descritta in fun
fval -> valore della funzione obbiettivo alla soluzione x
exitflag -> descrive la condizione di uscita
output -> contiene informazioni circa l’ottimizzazione (iterazioni, algoritmo, ecc)
grad -> è il valore del gradiente di fun alla soluzione x
hessian -> è il valore dell’Hessiano della funzione obbiettivo fun alla soluzione x.
Algoritmi
-
large-scale (on) : metodo Trust- Region,Newton interior- reflective,gradiente(PCG).
large –scale (off) : quasi- Newton , formula BFGS e DFP, steepest descent.
Optimization Toolbox di MATLAB
16
lsqlin
[x, resnorm, residual, exitflag, output, lambda]= lsqlin(C, d, A, b, Aeq,
beq, lb, ub, x0, options, p1, p2,…);
Input
C,A e Aeq sono matrici
d, b, beq, lb(lower bound), e ub(upper bound) sono vettori
P1,P2 -> argomenti addizionali passati a fun
x0 -> punto di inizio
options -> permette di modificare i parametri di ottimizzazione
Output
x -> minimo locale della funzione descritta in fun
residual-> C*x-d;
exitflag -> descrive la condizione di uscita
output -> contiene informazioni circa l’ottimizzazione (iterazioni, algoritmo, ecc)
Lambda -> struttura contenente il moltiplicatore di Lagrange alla soluzione x;
Resnorm -> norm(C*x-d)^2;
Algoritmi
Large Scale (on) -> metodo trust region basato sul metodo di Newton interior-reflective, gradienti:
Large Scale (off) -> programmazione quadratica
Optimization Toolbox di MATLAB
17
lsqnonlin
• [x, resnorm, residual, exitflag, output, lambda, jacobian] = lsqnonlin
(fun,x0,lb,ub,options,P1,P2,…);
Input
Fun -> funzione in input
lb(lower bound), e ub(upper bound) sono vettori
P!,P2 -> argomenti addizionali passati a fun
x0 -> punto di inizio
options -> permette di modificare i parametri di ottimizzazione
Output
x -> minimo locale della funzione descritta in fun
residual-> C*x-d;
exitflag -> descrive la condizione di uscita
output -> contiene informazioni circa l’ottimizzazione (iterazioni, algoritmo, ecc)
Lambda -> struttura contenente il moltiplicatore di Lagrange alla soluzione x;
Resnorm -> norm(C*x-d)^2;
Jacobian -> ritorna lo Jacobiano di fun alla soluzione x
Algoritmi
Larga scala(on) -> trust- region si basa sul metodo di Newton interior-reflective, gradienti preconditioned
Larga scala(off) -> Levemberg – Marquardt con ricerca di linea, Gauss- Newton con ricerca di linea
18
Optimization Toolbox di MATLAB
Esempi
Fminunc -
•
•
•
•
minimizzare la funzione data, trovare x1 e x2.
X0[-1,1];
Options =optimset(‘LargeScale’,’off’);
[x,fval,exitflag,output] =fminunc(@objfun,x0,options);
algoritmo-> medium scale ,’Quasi-Newton line search’
X=0.5000, -1,000
Optimization Toolbox di MATLAB
19
Esempi
Fminsearch - minimizza la funzione unidimensionale per trovare un minimo vicino a 2
Function : sen(x) + 3
• x = fminsearch (@myfun2,2);
• x= 4.7124;
Optimization Toolbox di MATLAB
20
Esempi
Esempio tratto da COPS
Problema - il più grande tra poligoni piccoli, cioè
Se
trovare il poligono di massima area,
tra i poligoni con n lati e diametro d<=1;
sono le coordinate dei vertici dei poligoni, allora dobbiamo massimizzare:
con i vincoli :
Optimization Toolbox di MATLAB
21
GRAZIE PER
L’ATTENZIONE
22

Download Report