Universitatea Valahia Targoviste

Facultatea de Inginerie Electrica

PROIECT

STUDENT: Covaci Alexandra Gabriela

Specializare: Automatica IV

1

CuprinsMetoda celei mai rapide coborari...............................................................................................................3

Algoritmul metodei celei mai rapide coborari.........................................................................................5

Exemplu de program in Matlab...............................................................................................................7

Example si concluzii.....................................................................................................................................8

2

Metodaceleimairapidecoborari.

Algoritmulmetodeiceleimairapidecoborari

MetodaceleimairapidecoborariMetodaceleimairapidecoborarieste o particularitate a metodeigradientului in care lungimea pasului de cautare se face pe baza relatiei:

, (1)

Stabilirea lui pe baza relatiei de mai sus nu este intotdeauna posibila. Mai mult,

esteposibilcalimitainferioarapentrurelatia (1) sa nu fie accesibilapentru diverse valori ale

indicelui k. in practica, se determinaca o valoare care aproximeaza sufficient de bine conditia

(1). In acestsens, esteposibilcavaloarea sa se determine cu conditia:

, , (2)

sau :

, 0< (3)

Marimile , din (2) si (3) caracterizeaza eroarea fata de conditia (1); astfel incat, cu cat se

apropie mai mult de zero, iar de unitate, cu atat eroarea de evaluare in raport cu (1) estemai

mica.

Trebuieremarcatcadirectia de antigradientasigura o foartebunaevolutiedoar in vecinatateapunctului de lansare a procedurii de cautare. In acesteconditii, dacavireza de variatie a

functieieste mare, atunci in punctual , directiaantigradient ( poate diferi foarte

mult de directia precedent ( .

3

Din acestmotiv, stabilireaparametrului nu impuneasigurarearelatiei (1) cu o mare fidelitate.

In practica, de multeori ne limitam in alegereapasului astfelincatsaasigurammonotonia

fara a cauta optimizarea pasului de cautare. Astfel, pentruiteratiak :

(4)

In cadrul fiecarei iteratii, se evalueaza modul in care evolueaza crieteriul si in functie de aceasta evolutie se modifica pasul astfel:

Daca , evolutiaestecorespunzatoaresi se incearcamodificarea in

senscrescator in ideeaaccelerariiconvergentei.

Daca inseamna ca lungimea pasului de cautareesteprea mica

incatdiferentele nu suntsesizabile sic a si in cazul precedent, marimlungimeapasului de cautare.

In sfarsit, daca , lungimeapasului de cautareesteprea mare,

aproximarealiniara care sta la bazatehnicilor de gradient nu estecorespunzatoare sic a

atare, lungimeapasuluitrebuiediminuatasirejectandvaloareaobtinuta , reluam iteratia

din .

Daca functia obiectiv este de clasa si daca satisfice conditia Lipschitz:

, (5)

In care constanta L estecunoscuta, atuncilungimeapasului de cautare in tehnica de gradient poate fi aleasa de forma:

, in care , reprezinta doi parametric de metoda, daca alegem

si , obtinem metoda de gradient cu o lungime a pasului de cautare .

Daca constanta L este mare, lungimea pasului va fi mica si convergenta este extreme de lenta.

4

Abordareateoretica a problemeiconvergenteialgoritmilor de tip gradient se porneste de la premizaoptimizariiprocedurii iterative in forma:

, (6)

Proceduranelimitatasi care conduce la un sir . inrealitate, cum vomvedea ulterior, algoritmul

se opreste in conditia de STOP: , cu apriori impus. Considerand ca succesiunea de

valori formeaza un sir , problema care se pune este daca acest sir este convergent catre

Solutia de minim a problemei initiale, decidaca se asiguraconvergentacatremultimeapunctelor de minim:

(7)

saualtfelspus, dacasuntindepliniteconditiile:

, (8)

Asigurareaconvergenteiimpunepelangaconditiileimpuseprinformulareaproblemei oserie de restrictiisuplimentaredestul de duresifoartegreu de evaluat.

Fie , de clasa si pentru care gradientul functiei satisface

conditia Lipschitz:

, (9)

In acesteconditii, sirul construit iterative in forma:

(10)

pentru care lungimeapasilor respecta:

, , (11)

5

unde pentru orice initializare , asigura

.

In plus, daca este convexa si daca reprezinta valoarea de minim atunci pentru

:

, . (12)

Dacaconsideramcaacesterestrictiisuntsatisfacute, conditia de oprire a

algoritmuluisivalidareasolutieivafi .

Algoritmulmetodeiceleimairapidecoborari

Etapa de initializare: Fie – conditia de STOP. Alegem coditia de initializare, k=1

si trecem la etapa de baza.

Etapa de baza: Daca , algoritmul se oprestesi reprezintasolutia de minim. Daca

nu, si se determina .

Construim si se reia etapa de baza.

Interpretareageometrica.

Putem da o interpretaregeometrica intuitive legata de constructa iterative a solutiei,

utilizandalgoritmulceleimairapidecoborari.Astfel, punctul determinat in conditiile:

si se aflapedreapta

inpunctul de tangent a acesteidrepte cu conturul de izonivel

6

sidreapta este perpendicular pe conturul de izonivel

Vomconsidera o parametrizare a curbei de izonivel de forma pentru si deci

pentru , iar . in aceste conditii:

.

In particular, pentru obtinem:

si in felulacestarezultacadirectia de gradient (sauantigradient) este perpendicular pe in punctul

.

Reamintimca se determina cu conditia:

Prinurmare, directia de gradient si sunt perpendicular si cum este

perpendicular pe , rezulta ca este tangent curbei .

Considerentelegeometriceprezentatesuntaplicatepecurbele de izonivel din figura 1.a si1.b :

7

Figura 1: interpretareageometrica a constructiei iterative

Este evidenta o comportaremaibunapentrucazul a.)in care curbele de izonivelsuntapropiateunorcontururicirculare. Pentrusituatiaprezentata in cazul b.), in care aparcontururialungitecesemnificafaptulca o serie de variabilemodificamaiputerniccriteriuldecatcelelalte, comportareaimplica un zig-zagprelungit in care eficientacautariiesteelativ mica.

Exemplu de program in MatlabMai josvoiprezentadescrierea in meta-limbaj a celuimaisimplualgoritm de gradient.

Date de intrare: (toleranta suficienta), (punct initial)

Repeta

1. Se determinadirectia de cautare la pasuli (data de versorulasociatgradientului):

, unde “+/-“ corespundmaximizarii/minimizarii

2. Se allege arbitrar , pasul de deplasarepedirectia

8

3. Se calculeazanoulpunct de evaluare a gradientului:

Panacand .

Se observacaalgoritmul de maisusnecesitacunoasterea a priori a tipului de extreme cautat (maxim sau minim).Implementarea in Matlab se poate face sub forma uneifunctii care primeste punctual de start al cautarii, x0 (la cazul general acestaeste un vector) sitolerantadorita, epsilon, sireturneazavaloarea de extreme a uneifunctii (la cazul general, vectoriale) cunoscute, x, sinumarul de iteratii in care s-a obtinutaceasta, nr_it. S-autilizat o variabilalocala, itermax, pentru a fortaiesirea din ciclaredacaextremul nu poate fi gasit.

function [x,nr_it]=opt_grad(x0,epsilon)nr_it=1;x_curent=x0;itermax=1500;%numar maxim de itera_ii h=0.001; %varia_ieutilizataîncalcululgradientului p=0.001;%se alege un pas constant de deplasarefor 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; while (norm(grad_curent)>=epsilon)&(nr_it<=itermax),%implementareaformulei (2.29) folosind (2.28); %pentru o func_ie de maximizat „–” se înlocuieste cu „+”x_viitor=x_curent-p*grad_curent/norm(grad_curent);for k=1:n, v=zeros(1,n);v(k)=1;grad_viitor(k)=(f1(x_viitor+h/2*v)-f1(x_viitor-h/2*v))/h;end;x_curent=x_viitor;grad_curent=grad_viitor;nr_it=nr_it+1;end; x=x_curent; Functia de maisus face uz de apellfunctieiMatlabnorm, care calculeazanormavectorialasaumatriciala; earealizeazaminimizareauneifunctii care trebuiesa se afle in fisierulf1.m; in particular eapoate fi o functiescalara:

function y=f1(x) y=5*x^2+2*x+13;

Valoarea in care se atingeminimulacesteifunctiieste –0.2, care se obtinedupa un numar de iteratiimaimicsaumai mare, depinzand de conditiainitialasi de pasul de deplasare ales. Intr-adevar, apelul:

[x,nr_it]=opt_grad(1,1e-3)

9

producerezultatele:

x = -0.2000

nr_it = 1201

iarapelul:

[x,nr_it]=opt_grad(-1,1e-3)

aredreptrezultat:

x = -0.2000

nr_it = 801

Numarul mare de iteratii se datoreazafolosiriiunui pas foartemic (p=0.001); folosireaunuiastfel de pas se justifica in cazulextremelorabrupte, undecomponentelegradientului au variatiimari.

Example siconcluziiPentruailustracomportareaalgoritmuluiceleimairapidecoborarivoiprezenta in continuarecatevaexemple.

Consideramfunctia:

continuasi derivate in . Ne propunemstabilireaminimuluiacesteifunctiiutilizandtehnica de

gradient.Evaluareava fi facutautilizandmetodaceleimairapidecoborariimplementata in Matlabprinsubrutinagrad1.m.

Subrutinaspecificata a fostrulatapentru o initializare , pentru treivalori ale

precizieiimpuse , pentru k=1,2,3.

Rezultateleobtinute in urmarulariiprogramelorprecunsidurataprocesariipentrufiecarecaz in parte suntprezentatesintetic in tabelulurmator:

Precizia Solutia de Valoareafuctieiobiecti Timpnecesarp Numar de

10

minim v rocesarii iteratii0.321 sec. 11

0.861 sec. 27

1.883 sec. 81

8.352 sec. 335

Tabel 1: rezultateleutilizariitehnicii de tip gradient

Pentruexemplulconsiderat se observa o bunacomportare in privintacorecteisolutionaripentru o

precizieconvenabila.Astfel, pentruconditia de stop obtinemsolutia ,

fata de solutiareala , . Crestereaexagerata a preciziei conduce la o

imbunatatirenesemnificativa a rezultatelor in daunacresteriisemnificative a timpului de calcul. In acestsens, in figura 2 esteprezentatgraficuldependenteitimpilor de calcul in functie de preciziaimpusa.

Din graphic reieseclarca o precizieexagerata conduce la untimp de calcul extreme de mare.

Figura 2.Dependentatimp de calcul-precizie

In figura 3 esteprezentatadependentadistanteipunctului de lucru in a k-a iteratie in raport cu punctual de minim real. Cum precizamsi in prezentareateoreticaeste evident caproceduraaplicata

11

are o eficientaridicata in fazainitiala a algoritmuluicanddistanta in raport de minimul real este relative mare.

Rafinarearezultatelorpentruasigurareapreciziei se face in pasimici care insaconnsumatimp de calcul.

Figura 3.Dependentapunct de lucru – optim

Deficintaalgoritmului anterior remarcatapoate fi vizualizatasi in graficul care reprezintaevolutiaprocesului de cautare a punctului de minim.

Pentrucazulanalizat, in conditiileuneiprecizii , graficulevolutieiesteprezentat in figura 4.

Se observa cu usurintacadupa circa patruiteratiicautarea se face intr-un zig-zagprelungit extreme de inefficient.

12

Figura 4.Graficulevolutieicatreoptim

Consideram in continuarefunctia de douavariabile:

pentru care gradientul se evalueazaimediat in forma:

Curbele de izonivelpentrufunctia considerate suntprezentate in figura 5. Din

aluraacestorcurberezultacafunctia considerate nu esteunimodalapentru

prezentandmaimultepuncte de extreme. Ne propunemstabilireaunui minim local utilizandtehnica

de tip gradient.

Subrutinagrad1.mimplementeazaalgoritmul de cautarepropus.

13

Figura 5.Curbele de izonivelpentrufunctia considerate

Considerandconditiainitiala , pentru o precizie algoritmul este

convergent in 4 iteratii in punctual de minim local , . initializarea

impusa a fixat punctual de plecare intr-o regiune a spatiului pentru care solutia obtinuta constituie un atractor stabil. O alta solutie de minim local sau sa genereze blocarea algoritmului.

In urmatorulexemplu, consideramdreptfunctieobiectivfucntiaRosenbrock:

pentru care gradientuleste de forma:

Pentru o initializarearbitrara , si o precizie impusa convergenta este

asigurata in 3929 iteratii. Solutia aproximatapentruproblemapropusaeste ,

14

. Valoarea de minim obtinuta pentru functia obiectiv este .

Evolutia in procesul de cautare este prezentata in figura 6.

Figura 6.Evolutia in procesul de cautare

Legat de problemaprezentata, putem face catevaobservatii de ordin general:

Conditia de stop popusa in tehnicile de gradient este cu multmairelevantadecat in cazulmetodelor de cautaredirecta. In cazulproblemeipropuse, pentru o precizie de 1% obtinem o solutiefoarteapropiata de solutiareala.

Pentruobtinereauneisolutiiconvenabilenumarul de iteratiieste in general cu multmaimic in raport cu metodele de cautaredirecta.

In cazulfunctiei considerate evolutia in procesul de cautareurmeazauntraseu curios in cadrulcareiaexistapuncte care apparent sunt situate la o distantamai mare fata de optim in raport cu punctul initial.

Acestlucruaparemai evident dacareluamalgoritmulpropuspentru o initializare ,

. Obtinem o aproximare a solutiei de optim , in 11320

de iteratii la o valoare a functieiobiectiv . Succesiuneapunctelor de

test esteprezentata in figura 7.

15

Figura 7.Succesiuneapunctelor de test

16