BFGSalgoritmen

BFGS-algoritmen är en metod för obestämda optimeringsproblem och tillhör familjen quasi-Newton-metoder. Den uppdaterar en approximation av Hessianen, eller dess inverse, vid varje iteration för att kunna beräkna en effektiv Newton-sökväg mot ett minimum utan att behöva räkna ut Hessianen exakt. Algoritmen är känd för sin robusthet och goda konvergens i många praktiska problem.

Vid varje iteration används s_k = x_{k+1} − x_k och y_k = ∇f(x_{k+1}) − ∇f(x_k). Om man arbetar med den inverse Hessian-approximationen H_k uppdateras den enligt H_{k+1} = H_k + (y_k y_k^T)/(y_k^T s_k) − (H_k s_k s_k^T H_k)/(s_k^T H_k s_k), under villkoret y_k^T s_k > 0. Om man istället arbetar med en Hessianuppskattning B_k uppdateras den enligt B_{k+1} = B_k − (B_k s_k s_k^T B_k)/(s_k^T B_k s_k) + (y_k y_k^T)/(y_k^T s_k). Första approximationen sätts ofta till identitetsmatrisen.

Egenskaper: BFGS bevarar symmetri och positiv definithet i H_k (så länge y_k^T s_k > 0 och startvärdet är positivt definite). Den kräver endast gradientutvärderingar och använder en rank-two-uppdatering, vilket ger ungefär O(n^2) beräkningskostnad per iteration och O(n^2) minne. Linje- eller Wolfe-kriterier används ofta för att säkra stabilitet i uppdateringen.

Historia och användning: BFGS utvecklades oberoende av Broyden, Fletcher, Goldfarb och Shanno på 1970-talet och är bland de mest använda optimeringsmetoderna i vetenskap och teknik. För mycket stora problem används varianter som L-BFGS, som minskar minnes- och beräkningskrav.