Broyden-Fletcher-Goldfarb-Shanno-algoritme

Broyden -Fletcher-Goldfarb-Shanno-algoritmen (BFGS) er en iterativ numerisk optimeringsmetode designet til at finde det lokale maksimum/minimum af en ikke-lineær funktionel uden begrænsninger.

BFGS er en af de mest udbredte kvasi-newtonske metoder . I kvasi-newtonske metoder beregnes funktionens hessian ikke direkte . I stedet estimeres Hessian tilnærmelsesvis baseret på de hidtil taget skridt. Der er også en hukommelsesbegrænset modifikation af denne metode ( L-BFGS ), som er designet til at løse ikke-lineære problemer med et stort antal ukendte, samt en hukommelsesbegrænset modifikation i en multidimensionel terning ( L-BFGS-B ) .

Denne metode finder minimum af enhver to gange kontinuerligt differentierbar konveks funktion. På trods af disse teoretiske begrænsninger har erfaring vist, at BFGS også håndterer ikke-konvekse funktioner godt.

Beskrivelse

Lad opgaven med at optimere det funktionelle løses:

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

Andenordensmetoder løser dette problem iterativt ved at udvide funktionen til et polynomium af anden grad:

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

hvor er hessian for det funktionelle ved punktet . Ofte er beregningen af hessian besværlig, så BFGS-algoritmen i stedet for den reelle værdi beregner den omtrentlige værdi af , hvorefter den finder minimum af det opnåede kvadratiske problem: $H$ $f$ $x$ $H(x)$ $B_{k}$

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

Herefter søges der som regel i en given retning efter et punkt, hvor Wolfe-betingelserne er opfyldt .

Enhver ikke-degenereret, velkonditioneret matrix kan tages som den indledende tilnærmelse af Hessian. Ofte tages identitetsmatrixen . Den omtrentlige værdi af hessian i det næste trin beregnes med formlen:

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}}},

hvor er identitetsmatrixen, er algoritmens trin pr. iteration, er ændringen i gradienten pr. iteration. $jeg$ $s_{k}=x_{{k+1}}-x_{k}$ $y_{k}=\nabla f_{{k+1}}-\nabla f_{{k}}$

Da det er beregningsmæssigt vanskeligt at beregne den inverse matrix, bliver den inverse matrix opdateret i stedet for at beregne : ${\displaystyle 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},

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

Algoritme

givet initialize mens find direction compute , opfylder Wolfes betingelser udpege og beregne slut $\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$

Litteratur

Nocedal, George; Wright, Stephen J. Numerisk optimering. — 2. udgave. — USA: Springer, 2006. — ISBN 978-0-387-30303-1 .
Avriel, Mordokaj. Ikke-lineær programmering: Analyse og metoder. - Dover Publishing, 2003. - ISBN 0-486-43227-0 .

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering