Algoritmul Broyden-Fletcher-Goldfarb-Shanno

Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS) este o metodă de optimizare numerică iterativă concepută pentru a găsi maximul/minimul local al unei funcționale neliniare fără restricții.

BFGS este una dintre cele mai utilizate metode cvasi-newtoniene . În metodele cvasi-newtoniene, Hessianul funcției nu este calculat direct . În schimb, Hessianul este estimat aproximativ, pe baza demersurilor întreprinse până acum. Există, de asemenea, o modificare limitată de memorie a acestei metode ( L-BFGS ), care este concepută pentru a rezolva probleme neliniare cu un număr mare de necunoscute, precum și o modificare limitată de memorie într-un cub multidimensional ( L-BFGS-B ) .

Această metodă găsește minimul oricărei funcții convexe diferențiabile de două ori continuu. În ciuda acestor limitări teoretice, experiența a arătat că BFGS gestionează bine și funcțiile neconvexe.

Descriere

Să fie rezolvată sarcina de optimizare a funcționalului:

\arg \min _{x}f(x).

Metodele de ordinul doi rezolvă această problemă în mod iterativ, prin extinderea funcției într-un polinom de gradul doi:

f(x_{k}+p)=f(x_{k})+\nabla f^{T}(x_{k})p+{\frac {1}{2}}p^{T}H(x_ {k})p,

unde este Hessianul funcționalului în punctul . Adesea, calculul Hessianului este laborios, astfel încât algoritmul BFGS în loc de valoarea reală calculează valoarea aproximativă a lui , după care găsește minimul problemei pătratice obținute: $H$ $f$ $X$ $H(x)$ $B_{k}$

p_{k}=-B_{k}^{{-1}}\nabla f(x_{k}).

De regulă, după aceasta, se efectuează o căutare pe o direcție dată pentru un punct pentru care sunt îndeplinite condițiile Wolfe .

Orice matrice nedegenerată, bine condiționată poate fi luată ca aproximare inițială a Hessianului. Adesea este luată matricea de identitate . Valoarea aproximativă a Hessianului în pasul următor este calculată prin formula:

B_{k+1}=B_{k}-{\frac {B_{k}s_{k}s_{k}^{T}B_{k}^{T}}{s_{k}^ {T}B_{k}s_{k}}}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}},

unde este matricea de identitate, este pasul algoritmului pe iterație, este modificarea gradientului pe iterație. $eu$ $s_{k}=x_{{k+1}}-x_{k}$ $y_{k}=\nabla f_{{k+1}}-\nabla f_{{k}}$

Deoarece calcularea matricei inverse este dificilă din punct de vedere computațional, în loc să se calculeze , matricea inversă este actualizată : $B_{k}^{-1)$ $B_{k}$ $C_{k}=B_{k}^{{-1}}$

C_{k+1}=(I-\rho _{k}s_{k}y_{k}^{T})C_{k}(I-\rho _{k}y_{k}s_ {k}^{T})+\rho _{k}s_{k}s_{k}^{T},

unde . $\rho _{k}={\frac {1}{y_{k}^{T}s_{k)))$

Algoritm

dat initialize while find direction compute , satisface conditiile lui Wolfe designate si compute end $\varepsilon ,\;x_{0}$
$C_{0}$
$k = 0$
$||\nabla f_{k}||>\varepsilon$
$p_{k}=-C_{k}\nabla f_{k}$
$x_{{k+1}}=x_{k}+\alpha _{k}p_{k}$ $\alpha _{k}$
$s_{k}=x_{{k+1}}-x_{{k}}$ $y_{k}=\nabla f_{{k+1}}-\nabla f_{k}$
$C_{{k+1}}$
$k=k+1$

Literatură

Nocedal, George; Wright, Stephen J. Optimizare numerică. — ediția a II-a. — SUA: Springer, 2006. — ISBN 978-0-387-30303-1 .
Avriel, Mardoheu. Programare neliniară: analiză și metode. - Editura Dover, 2003. - ISBN 0-486-43227-0 .

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock Metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică