Broyden-Fletcher-Goldfarb-Shanno-algoritm

Broyden -Fletcher-Goldfarb-Shanno-algoritmen (BFGS) är en iterativ numerisk optimeringsmetod utformad för att hitta det lokala max/minimum för en icke-linjär funktion utan begränsningar.

BFGS är en av de mest använda kvasi-newtonska metoderna . I kvasi-newtonska metoder beräknas inte funktionens hessian direkt . Istället uppskattas hessian ungefär, baserat på de steg som hittills tagits. Det finns också en minnesbegränsad modifiering av denna metod ( L-BFGS ), som är utformad för att lösa icke-linjära problem med ett stort antal okända, samt en minnesbegränsad modifiering i en flerdimensionell kub ( L-BFGS-B ) .

Denna metod finner minimum av en två gånger kontinuerligt differentierbar konvex funktion. Trots dessa teoretiska begränsningar har erfarenheten visat att BFGS även hanterar icke-konvexa funktioner väl.

Beskrivning

Låt uppgiften att optimera det funktionella lösas:

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

Andra ordningens metoder löser detta problem iterativt genom att expandera funktionen till ett polynom av andra graden:

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

var är hessian för det funktionella vid punkten . Ofta är beräkningen av hessian mödosam, så BFGS-algoritmen i stället för det verkliga värdet beräknar det ungefärliga värdet av , varefter den hittar minimum av det resulterande kvadratiska problemet: $H$ $f$ $x$ $H(x)$ $B_{k}$

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

Som regel, efter detta, utförs en sökning längs en given riktning efter en punkt för vilken Wolfe-villkoren är uppfyllda .

Vilken icke degenererad, välkonditionerad matris som helst kan tas som den initiala approximationen av Hessian. Ofta tas identitetsmatrisen . Det ungefärliga värdet av hessian i nästa steg beräknas med formeln:

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

var är identitetsmatrisen, är steget för algoritmen per iteration, är förändringen i gradienten per iteration. $jag$ $s_{k}=x_{{k+1}}-x_{k}$ $y_{k}=\nabla f_{{k+1}}-\nabla f_{{k}}$

Eftersom det är beräkningsmässigt svårt att beräkna den inversa matrisen , uppdateras den inversa matrisen istället för att beräkna : ${\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},

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

Algoritm

givet initialisera medan find direction compute , uppfyller Wolfes villkor designate och beräkna 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}$ $\alfa _{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:a upplagan. — USA: Springer, 2006. — ISBN 978-0-387-30303-1 .
Avriel, Mordokai. Icke-linjär programmering: Analys och metoder. - Dover Publishing, 2003. - ISBN 0-486-43227-0 .

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powells metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering