Studeni: Ghi Maria Mdlina Rdulescu Vlad Grupa : 442 A

Metoda Davidon-Fletcher-Powell

Problema

Metoda DFP a fost obinut iniial de Davidon i mbuntit de Fletcher i Powell.Este o funcie ptratic care are proprietatea c genereaz direciile de gradieni conjugai construind simultan inversa Hessianului.Gsirea unor metode intermediare ntre metoda celei mai abrupte pante i metoda lui NewtonMotive: accelerarea convergenei tipic lent a metodei celei mai abrupte pante evitarea evalurii, memorrii i inversrii Hessianului cerute de metoda lui Newton

Metoda Newton ModificatConsiderm problema min f(x) i propunem o rezolvare bazat pe procesul iterativ general

unde Sk este o matrice nn simetric i k este ales astfel nct s minimizeze f(xk+1). (Pentru Sk = I obinem metoda celei mai abrupte pante iar pentru Sk = F(xk)-1 obinem metoda lui Newton). Filosofia acestei modificri a metodei standard este s alegem Sk aproximativ egal cu F(xk)-1, cu condiia suplimentar c aceast aproximaie s fie uor de construit.

Construcia InverseiIdeile principale ale metodelor qvasiNewton sunt: Constructia unei aproximaii ale inversei Hessianului folosind informaie obinut pe msur ce procesul de cutare evolueaz.

Aproximarea curenta Hk este folosita la fiecare pas pentru a defini noua direcie de cutare punnd Sk = Hk n metoda Newton modificat.

Aproximarea converge la inversa Hessianului n punctul soluie iar metoda per ansamblu se comporta relativ similar metodei lui Newton.

Caracteristici D.F.P.Este o procedur de corecie de rang 2 numit i metod de metrica variabil.

La fiecare pas inversa Hessianului este actualizat printr-o suma de 2 matrici simetrice de rang 1.

Pentru o funcie ptratic genereaz direciile de gradieni conjugai construind simultan inversa Hessianului

AlgoritmSe ncepe cu orice matrice simetric i pozitiv definit H0, orice punct x0, si k = 0.Pasul 1: dk = -HkgkPasul 2: Se minimizeaz f(xk + dk) n raport cu 0 pentru a obine xk+1, pk = kdk, i gk+1Pasul 3: Se seteaz qk = gk+1 - gk si:

Se actualizeaza k i se trece la Pasul 1.

ConcluziiMetode Davidon-Fletcher-Powell evit calculele laborioase fcute cu metoda Newton i pstreaz convergena abrupt a metodei celei mai abrupte pante, n special pentru probleme ptratice.Pentru orice funcie ptratic, algoritmul calculeaz direciile de gradieni conjugai i recalculeaz inversa hessienei.Matricele care aproximeaz Hessiana, notate cu Fk, sunt pozitiv definite.Pentru probleme ptratice, algoritmul converge la soluie n n pai

BibliografieCurs Tehnici de Optimizare in Programare Ovidiu Grigore

www.it-weise.de Global Optimization Algorithms Theory and Application

Curs + Laborator Tehnici de Optimizare - Cristian Oara

Wikipedia