En optimització numèrica, l'algorisme Broyden-Fletcher-Goldfarb-Shanno (BFGS) és un mètode iteratiu per resoldre problemes d'optimització no lineal sense restriccions. Igual que el mètode relacionat de Davidon-Fletcher-Powell, BFGS determina la direcció de descens precondicionant el gradient amb informació de curvatura. Ho fa millorant gradualment una aproximació a la matriu hessiana de la funció de pèrdues, obtinguda només a partir d'avaluacions de gradient (o avaluacions de gradient aproximades) mitjançant un mètode secant generalitzat.

Com que les actualitzacions de la matriu de curvatura BFGS no requereixen inversió matricial, la seva complexitat computacional només és , en comparació amb en el mètode de Newton. També s'utilitza habitualment L-BFGS, que és una versió de memòria limitada de BFGS que s'adapta especialment a problemes amb un nombre molt gran de variables (per exemple, >1000). La variant BFGS-B gestiona restriccions de caixa simples. La matriu BFGS també admet una representació compacta, cosa que la fa més adequada per a problemes amb grans restriccions.

L'algorisme rep el nom de Charles George Broyden, Roger Fletcher, Donald Goldfarb i David Shanno.

Raonament El problema d'optimització és minimitzar , on és un vector en , i és una funció escalar diferenciable. No hi ha restriccions sobre els valors que pot prendre.

L'algoritme comença amb una estimació inicial per obtenir el valor òptim i procedeix iterativament per obtenir una millor estimació en cada etapa.

La direcció de cerca pk a l'etapa k ve donada per la solució de l'anàleg de l'equació de Newton:

on és una aproximació a la matriu hessiana a , que s'actualitza iterativament a cada etapa, i és el gradient de la funció avaluada a x k. Aleshores s'utilitza una cerca lineal en la direcció pk per trobar el següent punt xk +1 minimitzant sobre l'escalar

La condició de quasi-Newton imposada a l'actualització de és

Deixa i , aleshores satisfà

,

que és l'equació de la secant.

La condició de curvatura s'hauria de satisfer per per ser definit positiva, cosa que es pot verificar premultiplicant l'equació secant per . Si la funció no és fortament convexa, aleshores la condició s'ha d'aplicar explícitament, per exemple, trobant un punt x k +1 que satisfaci les condicions de Wolfe, que impliquen la condició de curvatura, utilitzant la cerca lineal.

En lloc de requerir la matriu hessiana completa en el punt a calcular com , l'aproximat hessià a l'etapa k s'actualitza mitjançant l'addició de dues matrius:

Tots dos i són matrius simètriques de rang u, però la seva suma és una matriu d'actualització de rang dos. Les matrius d'actualització de BFGS i DFP difereixen de les seves predecessores en una matriu de dos rangs. Un altre mètode de rang u més senzill es coneix com a mètode simètric de rang u, que no garanteix la definició positiva. Per tal de mantenir la simetria i la definició positiva de , el formulari d'actualització es pot triar com a . Imposant la condició secant, . Escollir i

, podem obtenir:

Finalment, substituïm i en i obtenir l'equació d'actualització de :

Algorisme Considereu el següent problema d'optimització sense restriccions on és una funció objectiva no lineal.

Des d'una conjectura inicial i una conjectura inicial de la matriu hessiana els passos següents es repeteixen com a convergeix a la solució:

Obtenir una direcció resolent . Realitzar una optimització unidimensional (cerca lineal) per trobar una mida de pas acceptable en la direcció trobada al primer pas. Si es realitza una cerca lineal exacta, aleshores . A la pràctica, una cerca lineal inexacta normalment és suficient, amb un resultat acceptable satisfent les condicions de Wolfe. Conjunt i actualitzar . . .

La convergència es pot determinar observant la norma del gradient; donat algun , es pot aturar l'algoritme quan Si s'inicialitza amb , el primer pas serà equivalent a un descens de gradient, però els passos posteriors es refinen cada cop més mitjançant , l'aproximació a l'hessià.

El primer pas de l'algoritme es duu a terme utilitzant la inversa de la matriu , que es pot obtenir de manera eficient aplicant la fórmula de Sherman-Morrison al pas 5 de l'algoritme, donant

Això es pot calcular de manera eficient sense matrius temporals, reconeixent que és simètric, i que i són escalars, utilitzant una expansió com ara

Per tant, per evitar qualsevol inversió matricial, es pot aproximar la inversa de l'hessiana en lloc de la mateixa hessiana:

Des d'una conjectura inicial i una matriu hessiana invertida aproximada els passos següents es repeteixen com a convergeix a la solució:

Obtenir una direcció resolent . Realitzar una optimització unidimensional (cerca lineal) per trobar una mida de pas acceptable en la direcció trobada al primer pas. Si es realitza una cerca lineal exacta, aleshores . A la pràctica, una cerca lineal inexacta normalment és suficient, amb un resultat acceptable satisfent les condicions de Wolfe. Conjunt i actualitzar . .

En problemes d'estimació estadística (com ara la màxima versemblança o la inferència bayesiana), els intervals de credibilitat o intervals de confiança per a la solució es poden estimar a partir de la inversa de la matriu hessiana final.. Tanmateix, aquestes quantitats estan tècnicament definides per la veritable matriu hessiana, i l'aproximació BFGS pot no convergir a la veritable matriu hessiana.

Implementacions notables Les implementacions de codi obert més destacades són:

ALGLIB implementa BFGS i la seva versió de memòria limitada en C++ i C# GNU Octave utilitza una forma de BFGS a la seva funció fsolve, amb extensions de regió de confiança. El GSL implementa BFGS com a gsl_multimin_fdfminimizer_vector_bfgs2. A R, l'algoritme BFGS (i la versió L-BFGS-B que permet restriccions de caixa) s'implementa com una opció de la funció base optim(). A SciPy, la funció scipy.optimize.fmin_bfgs implementa BFGS. També és possible executar BFGS utilitzant qualsevol dels algorismes L-BFGS establint el paràmetre L a un nombre molt gran. També és un dels mètodes per defecte que s'utilitzen quan s'executa scipy.optimize.minimize sense restriccions. A Julia, el paquet Optim.jl implementa BFGS i L-BFGS com a opció de solucionador per a la funció optimize() (entre altres opcions).

Referències

Categoria:Algorismes Categoria:Optimització