CURS 8: METODE DE OPTIMIZARE PARAMETRIC

Problemele de optimizare vizeaz extremizarea (maximizarea sau minimizarea) unui criteriu de performan. Acesta din urm poate fi o funcie caz n care este vorba despre optimizarea parametric sau o funcional (o funcie de funcii), cnd este vorba despre optimizarea dinamic. Acest paragraf este dedicat ilustrrii comparative a principalilor algoritmi de optimizare parametric.

1.1 Formularea problemei. Definiii Criteriul de performan care trebuie extremizat se mai numete funcie scop, funcie

obiectiv sau funcie criteriu fr impuneri de legturi sau/i restricii. Aceasta este o funcie de n argumente reale, 1 2( , ,... )nf x x x , a crei extremizare nseamn gsirea unui vector

* * * *1 2 ...

Tn

nx x x x

=

, corespunztor unui punct din spaiul n-dimensional, pentru

care funcia este optim (maxim sau minim). Maximizarea i minimizarea unei funcii nu se deosebesc formal, ntruct maximul lui f se obine pentru minimul lui f.

Pentru n2, funcia obiectiv admite o reprezentare geometric, i anume: bidimensional: 1( )y f x= este ecuaia unei curbe n planul 1( , )x y ; tridimensional: 1 2( , )y f x x= este ecuaia unei suprafee n sistemul de coordonate

1 2( , , )x x y (suprafaa de rspuns). Generalizarea acestor reprezentri pentru o funcie obiectiv de n variabile independente

necesit un sistem de n+1 axe independente, perpendiculare dou cte dou ntr-un sistem cartezian. Pentru n3 aceasta este evident imposibil de realizat n spaiul tridimensional i de aceea dezvoltrile teoretice cu introducerea noiunilor de hiperplan, hipersuprafa, hiperspaiu sunt uneori mai dificil de urmrit.

Este util reluarea a dou definiii cunoscute din matematic. Def in i ia 1: Fie funcia scalar continu i derivabil de variabil vectorial ( )f x ,

nx . Se numete gradientul funciei f funcia vectorial de variabil vectorial notat cu ( )f x , care conine derivatele pariale de ordinul nti ale lui f n raport cu fiecare dintre componentele lui x :

(1) 1 2

( ) ( ) ( )'( ) ( ) ...

T

n

f x f x f xf x f xx x x

=

Funcia ( )f x se numete antigradientul funciei f. Punctele de extrem, *x , ale unei funcii de variabil vectorial sunt caracterizate de anularea gradientului: *( ) 0f x = . Direcia vectorului gradient indic spre maximul unei funcii concave, iar a antigradientului indic spre minimul unei funcii convexe.

2

Def in i ia 2: Se numete (matricea) hessian a funciei de variabil vectorial ( )f x funcia matricial de variabil vectorial notat cu ( )H x , obinut printr-o nou derivare a gradientului n raport cu componentele vectorului x :

(2)

2 2 2

2 1 2 112 2 2

22 1 22

2 2 2

21 2

( ) ( ) ( )...

( ) ( ) ( )...

"( ) ( )... ... ... ...

( ) ( ) ( )...

n

n

n n n

f x f x f xx x x xx

f x f x f xf x H x x x x xx

f x f x f xx x x x x

=

1.2 Clasificarea metodelor de optimizare parametric Principalele metode de optimizare parametric sunt sintetizate n tabelul 2.9; ele sunt

detaliate n paragrafele urmtoare. Cele dou mari clase de metode indirecte i directe se deosebesc att principial, ct i din punctul de vedere al performanelor (viteza de convergen, timpul de calcul i memoria necesar algoritmilor rezultai). Astfel, metodele directe sunt n general mai lent convergente dect metodele indirecte, dar necesit un volum de memorie mai mic. Nivelul admisibil al compromisului acceptat n ce privete performanele este un factor n alegerea uneia sau alteia dintre metode.

A.1 metode de gradient (Cauchy) A.2 metode Newton (de gradient de ordinul al II-lea)

A. indirecte (folosesc valorile funciei

( )f x i pe cele ale derivatelor ei) A.3 metode ale direciilor conjugate

B.1 metoda explorrii exhaustive unidimensional B.2 metode de eliminare multidimensional

B.3 metode de cutare pe baz de hiperpoliedre (simplexuri) exploratoare B.4 metode de cutare aleatoare (Monte Carlo)

B. directe (folosesc numai valorile funciei ( )f x , fr a le utiliza pe cele ale derivatelor ei) B.5 metode de cutare unidirecional (unidimensional)

metode de relaxare (Gauss) Tabel 1 Clasificarea metodelor de optimizare parametric

1.3 Metode indirecte Metodele indirecte se mai numesc i metode de urcare (coborre); pentru simplificare,

pintr-un lejer abuz de limbaj, termenul de metode de gradient denot n mod generic ntreaga clas a metodelor indirecte. Esena lor const n gsirea punctului de anulare a gradientului (acesta fiind punctul de extrem cutat), pornind dintr-un punct iniial dat. n calculul aproximativ, termenul de anulare nseamn, de fapt, situarea valorii absolute sub o anume limit (toleran) dat, considerat ca suficient.

Metodele de gradient (Cauchy) i cele de gradient de ordinul al II-lea (Newton) se

3

bazeaz pe aproximri de ordinul I, respectiv de ordinul al II-lea, ale dezvoltrii n serie Taylor a funciei obiectiv ( )f x n jurul punctului de optim, *x :

(3) ( ) ( ) ( ) ( )* * *' Tf x f x f x x x + (4) ( ) ( ) ( ) ( ) ( ) ( ) ( )* * * * * *1' "2T T Tf x f x f x x x x x f x x x + + Metodele Newton au o convergen mai bun dect cele de gradient simplu, dar prezint

inconvenientul unui timp de calcul i al unui volum de memorie mai mari, pentru c necesit calculul matricei hessian la fiecare iteraie de cutare.

n formula (23) gradientul arat direcia ratei maxime de cretere a funciei f. Pe aceast formul se bazeaz metoda celei mai mari pante (dac optimul este un maxim) sau metoda celei mai abrupte coborri (dac optimul este un minim). Mai jos se prezint descrierea n meta-limbaj a celui mai simplu algoritm de gradient (notaia |||| semnific norma vectorial).

Date de intrare: (tolerana suficient), x(0) (punctul iniial) i 0 Repet

#1. Se determin direcia de cutare la pasul i (dat de versorul asociat gradientului):

(5) ( )( )( )

( )( )

ii

i

f xd

f x

=

, unde +/ corespund maximizrii/minimizrii

#3. Se alege arbitrar p(i), pasul de deplasare pe direcia d(i). #2. Se calculeaz noul punct de evaluare a gradientului:

(6) ( 1) ( ) ( )( )i i iix x p d+ = + i i+1

Pn cnd ( )( )if x . Se observ c algoritmul de mai sus necesit cunoaterea a priori a tipului de extrem

cutat (maxim sau minim). Implementarea n Matlab se poate face sub forma unei funcii care primete punctul de start al cutrii, x0 (la cazul general acesta este un vector) i tolerana dorit, epsilon, i returneaz valoarea de extrem a unei funcii (la cazul general, vectoriale) cunoscute, x, i numrul de iteraii n care s-a obinut aceasta, nr_it. S-a utilizat o variabil local, itermax, pentru a fora ieirea din ciclare dac extremul nu poate fi gsit.

function [x,nr_it]=opt_grad(x0,epsilon) nr_it=1;x_curent=x0;itermax=1500;%numr maxim de iteraii h=0.001; %variaie utilizat n calculul gradientului p=0.001;%se alege un pas constant de deplasare for k=1:n, v=zeros(1,n);v(k)=1; grad_curent(k)=(f1(x0+h/2*v)-f1(x0-h/2*v))/h; end;

4

while (norm(grad_curent)>=epsilon)&(nr_it

5

1. Se alege un punct iniial caracterizat de vectorul x(0). 2. Se stabilete direcia iniial drept direcia negativ a gradientului n x(0):

( )( )(0) (0)p f x= 3. La fiecare iteraie i se determin minimul n raport cu parametrul al funciei obiectiv

n direcia p(i), conform relaiei:

(7) ( ) ( )( 1) ( ) ( )i i if x f x p+ = + Se determin astfel punctul x(i+1). 4. Se determin noua direcie de cutare, p(i+1), din punctul x(i+1):

(8) ( ) ( )( )2( 1)

( 1) ( 1) ( )2( )

ii i i

i

f xp f x p

f x

+

+ +

= +

5. Dac ( ) ( )( 1) ( )i if x f x+ , atunci punctul de minim a fost gsit: x* x(i), STOP; altfel se reia de la etapa 3.

n cele ce urmeaz este dat programul Matlab (fletreev.m) care implementeaz algoritmul Fletcher-Reeves; acesta va fi testat pentru aceeai funcie scalar de gradul al II-lea coninut n fiierul f1.m, cu un minim la 0.2.

%iniializri i=1;x(i,:)=x0;n=length(x0);itermax=1000;%numr maxim de iteraii h=0.0001;%variaie utilizat n calculul gradientului for k=1:n, v=zeros(1,n);v(k)=1; %la fiecare pas gradientul este un vector de dimensiune n grad(i,k)=(f1(x0+h/2*v)-f1(x0-h/2*v))/h; end; p(i,:)=-grad(i,:); stop=0;%variabil boolean care arat gsirea minimului local cutat while (~stop)&(i

6

end;%n acest moment noul punct de cutare este x(i+1) if (~stop) for k=1:n, v=zeros(1,n);v(k)=1; grad(i+1,k)=(f1(x(i+1,:)+h/2*v)-f1(x(i+1,:)-h/2*v))/h; end; %noua direcie de cutare se determin cu formula (2.31) p(i+1,:)=-grad(i+1,:)+... norm(grad(i+1,:))^2/norm(grad(i,:))^2*p(i,:); end; i=i+1; end;

[nr_it n]=size(x);nr_it minim=x(nr_it,:) Execuia programului din linie de comand necesit iniializarea variabilei x0, punctul de

start al cutrii. De exemplu, pentru: x0=1;fletreev

rezultatul: nr_it = 2

minim = -0.2000

arat o convergen mai rapid dect cea a metodei de gradient anterioare, implementat prin funcia utilizator opt_grad. Observa ie :

Pentru o funcie de n variabile care nu este ptratic, dup fiecare n iteraii se reiniializeaz direcia de cutare la direcia antigradientului, ca la primul pas. Scopul este eliminarea erorilor datorate faptului c funcia se poate aproxima bine cu o funcie ptratic numai n stricta vecintate a optimului.

1.4 Metode directe. Metode de relaxare Din clasa metodelor directe de cutare a optimului, cea mai simpl, dar i cea mai

costisitoare ca timp, este cea a explorrii exhaustive. Metodele de eliminare se folosesc cnd funcia obiectiv are un singur optim (funcie unimodal); ele se bazeaz pe eliminarea unei regiuni a domeniului de variaie a variabilelor independente care nu conine optimul.

Cutarea aleatoare (metoda Monte Carlo) const n evaluarea funciei obiectiv ntr-un set de puncte generate pseudoaleator la fiecare iteraie a algoritmului. Domeniul de explorare din jurul optimului aflat la fiecare iteraie se restrnge, pn cnd el devine mai mic dect cel impus; astfel, optimul de la ultima iteraie se declar drept optim global.

Spre deosebire de metodele de gradient care efectueaz modificri simultane ce produc deplasri n spaiul n-dimensional metodele de cutare unidimensional (Gauss) se fondeaz pe modificarea succesiv a componentelor vectorului x. Aceste metode se mai numesc i metode de relaxare sau de optimizare ciclic de-a lungul axelor de coordonate (engl. cyclic coordinate search). Cutarea multidimensional este astfel transformat ntr-o

7

succesiune de cutri unidimensionale, fr a prospecta direcia naintrii, ci doar prin relaxarea rnd pe rnd a tuturor direciilor axelor de coordonate. Exist mai muli algoritmi bazai pe metoda relaxrii, care difer dup modul n care se face varierea pasului de cutare.

Metodele de relaxare sunt n general mai lent convergente dect metodele obinuite de gradient, fiindc pot conine mai multe iteraii de cutare unidimensional, n funcie de alegerea punctului de start i a pasului. Ele pot deveni ineficiente sau cel puin foarte lent convergente dac funcia obiectiv prezint o vale (sau o creast) care nu are direcia paralel cu axele de coordonate.

Se prezint mai jos etapele unui algoritm de relaxare [CEAN 84], n care pasul este meninut constant pe durata unui ciclu de explorare a tuturor direciilor, dup care pasul este micorat n progresie geometric de raie r, pn cnd devine mai mic dect un prag dat, .

1. Se alege un punct iniial caracterizat de vectorul (0) (0)(0) (0)1 2 ... nx x x x = ,

valoarea iniial a pasului de cutare, p, i pragul . 2. Se iniializeaz indexul coordonatei de relaxat: k 1. 3. Se iniializeaz contorul de iteraii din optimizarea n raport cu coordonata k: i 0. 4. La o iteraie i se relaxeaz coordonata de index k, obinndu-se vectorul:

( 1)

( ) ( )( 1) ( )1 ... ...

ik

i ii ink

x

x x x p x+

+

= +

Dac ( ) ( )( 1) ( )i if x f x+ , atunci i i+1 i se reia etapa 4; altfel dac i=1 (prima iteraie), atunci se face relaxarea n sens opus:

( ) ( 1)( 1) ( )1 ... 2 ...

i ii inkx x x p x

++ =

p p i i+1 i se reia etapa 4;

altfel dac ( ) ( )( ) ( 1)i if x f x , atunci valoarea de optim a coordonatei k este:

( 1)opt

ik kx x

=

k k+1 i se reia etapa 3 (se relaxeaz urmtoarea coordonat, k+1).

5. Se modific pasul p, nmulindu-l cu raia r

8

%x0 - punctul de start (vector de dimensiunea variabilei funciei de optimizat, n) %pas_init - pasul iniial de cutare %r - raia subunitar de modificare a pasului dup fiecare ciclu de relaxare a tuturor % celor n coordonate %tol - valoarea de prag a pasului, cnd cutarea se oprete

%iniializri i=1;x(i,:)=x0;p=pas_init; n=length(x0);

while (p>tol), p0=p*r;p=p0; k=1;d=zeros(1,n); stop_global=0;inapoi=0; while (~stop_global), d(k)=1;j=0; stop=0; while (~stop) if inapoi, p=p/2; inapoi=0; end; x(i+1,:)=x(i,:)+p*d; j=j+1; if feval(fct_scop,x(i+1,:))>feval(fct_scop,x(i,:)), if j==1, p=-2*p; i=i+1; x(i+1,:)=x(i,:)+p*d; inapoi=1; else stop=1; x(i+1,:)=[]; i=i-1; d(k)=0; k=k+1; p=p0; end; end; i=i+1; end; if k

9

end;

[nr_it n]=size(x); x_opt=x(nr_it,:); Pentru exemplificare, s-a folosit o funcie de dou argumente reale: function y=f(x) y=4+6*x(1)-4*x(2)+x(1)^2+2*x(2)^2-... 6*x(1)*x(2)+x(1)^4+2*x(1)^2*x(2);

care descrie o suprafa (figura 2.9), i care are trei minime locale, calculabile analitic, situate aproximativ n punctele de coordonate (0;1), (0.3117;1.419) i (4.8117;17.794).

Cele dou apeluri de mai jos arat c, din acelai punct de start, (1;3), dar cu alt pas iniial (p=1, respectiv p=0.5), metoda relaxrii poate furniza rezultate semnificativ diferite.

[x_opt,nr_it]=opt_rlx('f',[-1 3],1,0.5,1e-6) x_opt = 0.0000 1.0000 nr_it = 84 [x_opt,nr_it]=opt_rlx('f',[-1 3],0.5,0.5,1e-6) x_opt = 0.3118 1.4191 nr_it = 407

Fig. 1 O suprafa cu trei minime locale: 2 2 4 2

1 2 1 2 1 2 1 2 1 1 2( , ) 4 6 4 2 6 2f x x x x x x x x x x x= + + + + +

Dintr-un alt punct de start se poate obine un alt punct de minim local: [x_opt,nr_it]=opt_rlx('f',[-3 -7],2,0.5,1e-5) x_opt = -4.8158 -17.8200 nr_it = 3577

f(x1,x2)

x2 x1