Broyden-Fletcher-Goldfarb-Shanno-algoritmi

Broyden -Fletcher-Goldfarb-Shanno-algoritmi (BFGS) on iteratiivinen numeerinen optimointimenetelmä , joka on suunniteltu etsimään epälineaarisen funktion paikallinen maksimi/minimi ilman rajoituksia.

BFGS on yksi yleisimmin käytetyistä kvasi-newtonilaisista menetelmistä . Kvasinewtonilaisissa menetelmissä funktion Hessenistä ei lasketa suoraan . Hessenin sen sijaan on arvioitu likimääräisesti tähän mennessä tehtyjen askelten perusteella. Tästä menetelmästä on myös muistirajoitettu muunnos ( L-BFGS ), joka on suunniteltu ratkaisemaan epälineaarisia ongelmia, joissa on suuri määrä tuntemattomia, sekä muistirajoitettu modifikaatio moniulotteisessa kuutiossa ( L-BFGS-B ) . .

Tämä menetelmä löytää minkä tahansa kahdesti jatkuvasti differentioituvan konveksin funktion minimin. Näistä teoreettisista rajoituksista huolimatta kokemus on osoittanut, että BFGS käsittelee myös ei-kuperat funktiot hyvin.

Kuvaus

Ratkaistaan toiminnallisuuden optimointi:

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

Toisen asteen menetelmät ratkaisevat tämän ongelman iteratiivisesti laajentamalla funktion toisen asteen polynomiksi:

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

missä on funktion Hessianinen pisteessä . Usein Hessenin laskenta on työlästä, joten BFGS-algoritmi laskee todellisen arvon sijaan likimääräisen arvon , jonka jälkeen se löytää tuloksena olevan neliötehtävän minimin: $H$ $f$ $x$ $H(x)$ $B_{k}$

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

Pääsääntöisesti tämän jälkeen etsitään tiettyä suuntaa pitkin pistettä, jolle Wolfen ehdot täyttyvät .

Mitä tahansa rappeutumatonta, hyvin ehdoiteltua matriisia voidaan pitää Hessenin alkuperäisenä approksimaationa. Usein otetaan identiteettimatriisi . Hessenin likimääräinen arvo seuraavassa vaiheessa lasketaan kaavalla:

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

missä on identiteettimatriisi, on algoritmin askel iteraatiota kohti, on gradientin muutos iteraatiota kohti. $minä$ $s_{k}=x_{{k+1}}-x_{k}$ $y_{k}=\nabla f_{{k+1}}-\nabla f_{{k}}$

Koska käänteimatriisin laskeminen on laskennallisesti vaikeaa, laskennan sijaan käänteimatriisi päivitetään : ${\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},

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

Algoritmi

annettu alustus , kun etsi suunta laske , täyttää Wolfen ehdot nimetä ja laske loppu $\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$

Kirjallisuus

Nocedal, George; Wright, Stephen J. Numeerinen optimointi. – 2. painos. — USA: Springer, 2006. — ISBN 978-0-387-30303-1 .
Avriel, Mordokai. Epälineaarinen ohjelmointi: analyysi ja menetelmät. - Dover Publishing, 2003. - ISBN 0-486-43227-0 .

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijk menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi