Minimizzazione (e massimizzazione) di funzioni
Antonino Polimeno
antonino.polimeno@unipd.it
− Uno dei problemi principali della chimica la minimizzazione dell’energia totale di un sistema molecolare (o
supramolecolare)
− energy optimization
− geometry optimization
− Calcolo della configurazione di equilibrio di molecole e solidi
− Il problema matematica è
− il calcolo del minimo assoluto e/o dei minimi relativi di una funzione (energia totale)
− che dipende dalle coordinate nucleari (nell’approssimazione BO)
− nel modo più efficiente possibile
Direct methods Indirect methods Calculus-based techniques
Genetic algorithms
Evolutionary algorithms Simulated annealing Guided random search techniques
Dynamic programming Enumerative techniques Search techniques
− Metodi di ottimizzazione ‘standard’ diretti
− Sistemi monodimensionali
− metodo di Brent
− golden section search
− Sistemi multidimensionali
− metodo di Powel (valutazione della sola funzione)
− gradiente coniugato
− quasi-Newton
Sezione aurea- 1
a
b
c
Sono dati tre punti a < b < c che individuano un intervallo al cui interno è compreso un minimo, dato che f(b) < f(a), f(c)
Dobbiamo scegliere un nuovo punto per restringere l’intervallo in cui è compreso il minimo; se b è posto ad una frazione w di a e c e il nuovo punto x è ad una frazione z oltre b abbiamo che
, 1 ,
b a c b x b
w w z
c a c a c a
a b x c
w 1-w
z
Il nuovo intervallo sarà quindi lungo w+z oppure 1-w volte quello attuale. Il caso peggiore si ha per w+z=1-w
1 2 z w
Il nuovo punto è quindi il punto ‘simmetrico’ a b nell’intervallo originale, cioè |b-a|/(c-a)=|x-c|/(c-a), e questo implica che cada nell’intervallo più lungo tra [a,b] e [b,c]; nel nostro caso quindi (vedi figura) in [b,c]
x
Sezione aurea- 2
a
b
c
Ma come scegliamo z ? La strategia è che la scelta ottimale, che si sta facendo nell’iterazione attuale, sia stata presumibilmente fatta anche prima, scegliendo w. Quindi si ipotizza che x sia posto alla distanza frazionaria tra b e c uguale a quella di b fra a e c.
1
z w
w
x
Mettendo insieme le due equazioni otteniamo:
2
3 5
0.38197
3 1
2 SEZIONE AU E
0
R A w
w w
α β
γ
: :
Sezione aurea- 3
1. Sia [a, b] un intervallo, con f(a), f(b) già noti 2. Calcoliamo
3. Se f(c) < f (d) allora
4. Se f(d) < f(c) allora
5. Ripeti 2
/ , / , 1 5 / 2 1
c b b a r d a b a r r w
, , , , ,
/
b f b d f d d f d c f c c b b a r
, , , , ,
/
a f a c f c c f c d f d d a b a r
Convergenza lineare
Esempio
% ---GOLDEN SECTION METHOD---
% ---
% Copyright (c) 2009, Katarzyna Zarnowiec, all rights reserved
% mailto: katarzyna.zarnowiec@gmail.com
% --- figure; hold on;
a=0; % start of interval b=2; % end of interval epsilon=0.000001; % accuracy value
iter= 50; % maximum number of iterations
tau=double((sqrt(5)-1)/2); % golden proportion coefficient, around 0.618 k=0; % number of iterations
x1=a+(1-tau)*(b-a); % computing x values x2=a+tau*(b-a);
f_x1=f(x1); % computing values in x points f_x2=f(x2);
plot(x1,f_x1,'rx') % plotting x plot(x2,f_x2,'rx')
while ((abs(b-a)>epsilon) && (k<iter)) k=k+1;
if(f_x1<f_x2) b=x2;
x2=x1;
x1=a+(1-tau)*(b-a);
f_x1=f(x1);
f_x2=f(x2);
plot(x1,f_x1,'rx');
else a=x1;
x1=x2;
x2=a+tau*(b-a);
f_x1=f(x1);
f_x2=f(x2);
plot(x2,f_x2,'rx') end
k=k+1;
end
% chooses minimum point if(f_x1<f_x2)
sprintf('x_min=%f', x1) sprintf('f(x_min)=%f ', f_x1) plot(x1,f_x1,'ro')
else
sprintf('x_min=%f', x2) sprintf('f(x_min)=%f ', f_x2) plot(x2,f_x2,'ro')
end
% ---GOLDEN SECTION METHOD---
% ---
% Copyright (c) 2009, Katarzyna Zarnowiec, all rights reserved
% mailto: katarzyna.zarnowiec@gmail.com
% --- figure; hold on;
a=0; % start of interval b=2; % end of interval epsilon=0.000001; % accuracy value
iter= 50; % maximum number of iterations
tau=double((sqrt(5)-1)/2); % golden proportion coefficient, around 0.618 k=0; % number of iterations
x1=a+(1-tau)*(b-a); % computing x values x2=a+tau*(b-a);
f_x1=f(x1); % computing values in x points f_x2=f(x2);
plot(x1,f_x1,'rx') % plotting x plot(x2,f_x2,'rx')
Molte dimensioni: gradiente coniugato - 1
− Consideriamo una generica funzione; vogliamo individuare il punto (i punti) in cui il gradiente è nullo
− Gradiente coniugato
− metodo iterativo
− usa le derivate (gradiente)
− relativamente semplice da implementare
− convergenza superlineare
( ) funzione delle coordinate
: ˆ ( ) 0 f
f
x x
x x
0 0
2
0 0 0
0
,
( ) 1 ( ) 1
( )
2 2
i i i i j j
i i i j i j
f f
f f x x x x x x c
x
x x
x x x x
x x
x x b x x A x
Molte dimensioni: gradiente coniugato - 2
1
min ˆ
ˆ
k k k
k k k k
f f
f
x x
x x x
Un metodo poco efficiente: steepest descent
Molte dimensioni: gradiente coniugato - 3
− Gradiente coniugato: la direzioni di propagazione ad ogni ogni step cambia minimizzando la forma quadratica
1
1 1
1
lunghezza del 'passo di discesa' proprio
lunghezza del 'passo di discesa ' coniu gat o
k k
k k k
k k
k k k
k k
k
k k
k
k
k k
k
x x p
r b A x
p r
p A r p A p
p
p r
p A r
x = fminunc(fun,x0)
x = fminunc(fun,x0,options) x = fminunc(problem) [x,fval] = fminunc(___)
[x,fval,exitflag,output] = fminunc(___)
[x,fval,exitflag,output,grad,hessian] = fminunc(___)
function [f,g] = rosenbrockwithgrad(x) % Calculate objective f
f = 100*(x(2) - x(1)^2)^2 + (1-x(1))^2; if nargout > 1 % gradient required g = [-400*(x(2)-x(1)^2)*x(1)-2*(1-x(1)); 200*(x(2)-x(1)^2)];
end
options = optimoptions('fminunc','Algorithm','trust- region','SpecifyObjectiveGradient',true);
x0 = [-1,2];
fun = @rosenbrockwithgrad;
x = fminunc(fun,x0,options) x = fminunc(fun,x0)
x = fminunc(fun,x0,options) x = fminunc(problem) [x,fval] = fminunc(___)
[x,fval,exitflag,output] = fminunc(___)
[x,fval,exitflag,output,grad,hessian] = fminunc(___)
