Algoritmus Broyden – Fletcher – Goldfarb – Shanno - Broyden–Fletcher–Goldfarb–Shanno algorithm

v numerické optimalizace, Broyden – Fletcher – Goldfarb – Shanno (BFGS) algoritmus je iterační metoda pro neomezené řešení nelineární optimalizace problémy.^[1]

Metoda BFGS patří kvazi-Newtonovy metody, třída optimalizace horolezectví techniky, které hledají a stacionární bod funkce (nejlépe dvakrát spojitě diferencovatelné). Pro takové problémy, a nezbytná podmínka pro optimálnost je to spád být nula. Newtonova metoda a není zaručeno, že konvergují metody BFGS, pokud funkce nemá kvadratický Taylorova expanze poblíž optimální. BFGS však může mít přijatelný výkon i pro instance plynulé optimalizace.^[2]

v Kvazi-Newtonovy metody, Hesenská matice sekundy deriváty není vypočítán. Namísto toho je pytlovina matice aproximována pomocí aktualizací určených pomocí vyhodnocení gradientu (nebo přibližného vyhodnocení gradientu). Kvazi-Newtonovy metody jsou zobecnění sekansová metoda najít kořen první derivace pro vícerozměrné problémy. Ve vícerozměrných problémech sečanská rovnice neurčuje jedinečné řešení a kvazi-Newtonovy metody se liší v tom, jak omezují řešení. Metoda BFGS je jedním z nejpopulárnějších členů této třídy.^[3] Také se běžně používá L-BFGS, což je verze BFGS s omezenou pamětí, která je zvláště vhodná pro problémy s velmi velkým počtem proměnných (např.> 1000). Varianta BFGS-B zpracovává jednoduchá omezení polí.^[4]

Algoritmus je pojmenován po Charles George Broyden, Roger Fletcher, Donald Goldfarb a David Shanno.^[5]^[6]^[7]^[8]

Odůvodnění

Problém optimalizace je minimalizovat ${ displaystyle f ( mathbf {x})}$ , kde ${ displaystyle mathbf {x}}$ je vektor v ${ displaystyle mathbb {R} ^ {n}}$ , a ${ displaystyle f}$ je diferencovatelná skalární funkce. Na hodnoty, které existují, neexistují žádná omezení ${ displaystyle mathbf {x}}$ můžu vzít.

Algoritmus začíná počátečním odhadem optimální hodnoty ${ displaystyle mathbf {x} _ {0}}$ a postupuje iterativně, aby získal lepší odhad v každé fázi.

Směr hledání p_k ve fázi k je dáno řešením analogu Newtonovy rovnice:

{ displaystyle B_ {k} mathbf {p} _ {k} = - nabla f ( mathbf {x} _ {k}),}

kde ${ displaystyle B_ {k}}$ je přiblížení k Hesenská matice, který je iterativně aktualizován v každé fázi, a ${ displaystyle nabla f ( mathbf {x} _ {k})}$ je gradient funkce vyhodnocené na X_k. A vyhledávání linek ve směru p_k se poté použije k nalezení dalšího bodu X_k+1 minimalizací ${ displaystyle f ( mathbf {x} _ {k} + gamma mathbf {p} _ {k})}$ přes skalární ${ displaystyle gamma> 0.}$

Kvazi-Newtonova podmínka uložená na aktualizaci ${ displaystyle B_ {k}}$ je

{ displaystyle B_ {k + 1} ( mathbf {x} _ {k + 1} - mathbf {x} _ {k}) = nabla f ( mathbf {x} _ {k + 1}) - nabla f ( mathbf {x} _ {k}).}

Nechat ${ displaystyle mathbf {y} _ {k} = nabla f ( mathbf {x} _ {k + 1}) - nabla f ( mathbf {x} _ {k})}$ a ${ displaystyle mathbf {s} _ {k} = mathbf {x} _ {k + 1} - mathbf {x} _ {k}}$ , pak ${ displaystyle B_ {k + 1}}$ splňuje ${ displaystyle B_ {k + 1} mathbf {s} _ {k} = mathbf {y} _ {k}}$ , což je sekánová rovnice. Stav zakřivení ${ displaystyle mathbf {s} _ {k} ^ { top} mathbf {y} _ {k}> 0}$ by měl být spokojen ${ displaystyle B_ {k + 1}}$ být kladně definitivní, což lze ověřit předběžným vynásobením secanské rovnice ${ displaystyle mathbf {s} _ {k} ^ {T}}$ . Pokud funkce není silně konvexní, musí být podmínka vynucena explicitně.

Místo toho, abychom v tomto bodě vyžadovali úplnou hesenskou matici ${ displaystyle mathbf {x} _ {k + 1}}$ být vypočítán jako ${ displaystyle B_ {k + 1}}$ , přibližný Hessian ve fázi k je aktualizován přidáním dvou matic:

{ displaystyle B_ {k + 1} = B_ {k} + U_ {k} + V_ {k}.}

Oba ${ displaystyle U_ {k}}$ a ${ displaystyle V_ {k}}$ jsou symetrické matice první řady, ale jejich součet je aktualizační matice druhé řady. BFGS a DFP aktualizační matice se od svého předchůdce liší maticí druhé úrovně. Další jednodušší metoda pořadí je známá jako symetrická hodnost jedna metoda, která nezaručuje pozitivní definitivnost. Aby byla zachována symetrie a pozitivní definitivita ${ displaystyle B_ {k + 1}}$ , lze zvolit aktualizační formulář jako ${ displaystyle B_ {k + 1} = B_ {k} + alpha mathbf {u} mathbf {u} ^ { top} + beta mathbf {v} mathbf {v} ^ { top} }$ . Ukládání sekančního stavu, ${ displaystyle B_ {k + 1} mathbf {s} _ {k} = mathbf {y} _ {k}}$ . Výběr ${ displaystyle mathbf {u} = mathbf {y} _ {k}}$ a ${ displaystyle mathbf {v} = B_ {k} mathbf {s} _ {k}}$ , můžeme získat:^[9]

{ displaystyle alpha = { frac {1} { mathbf {y} _ {k} ^ {T} mathbf {s} _ {k}}},}

{ displaystyle beta = - { frac {1} { mathbf {s} _ {k} ^ {T} B_ {k} mathbf {s} _ {k}}}.}

Nakonec dosadíme ${ displaystyle alpha}$ a ${ displaystyle beta}$ do ${ displaystyle B_ {k + 1} = B_ {k} + alpha mathbf {u} mathbf {u} ^ { top} + beta mathbf {v} mathbf {v} ^ { top} }$ a získejte rovnici aktualizace ${ displaystyle B_ {k + 1}}$ :

{ displaystyle B_ {k + 1} = B_ {k} + { frac { mathbf {y} _ {k} mathbf {y} _ {k} ^ { mathrm {T}}} { mathbf { y} _ {k} ^ { mathrm {T}} mathbf {s} _ {k}}} - { frac {B_ {k} mathbf {s} _ {k} mathbf {s} _ { k} ^ { mathrm {T}} B_ {k} ^ { mathrm {T}}} { mathbf {s} _ {k} ^ { mathrm {T}} B_ {k} mathbf {s} _ {k}}}.}

Algoritmus

Z počátečního odhadu ${ displaystyle mathbf {x} _ {0}}$ a přibližná hesenská matice ${ displaystyle B_ {0}}$ následující kroky se opakují jako ${ displaystyle mathbf {x} _ {k}}$ konverguje k řešení:

Získejte směr ${ displaystyle mathbf {p} _ {k}}$ řešením ${ displaystyle B_ {k} mathbf {p} _ {k} = - nabla f ( mathbf {x} _ {k})}$ .
Proveďte jednorozměrnou optimalizaci (vyhledávání linek ) najít přijatelnou velikost kroku ${ displaystyle alpha _ {k}}$ ve směru nalezeném v prvním kroku. Pokud je provedeno přesné vyhledávání řádků, pak ${ displaystyle alpha _ {k} = arg min f ( mathbf {x} _ {k} + alpha mathbf {p} _ {k})}$ . V praxi obvykle postačuje nepřesné vyhledávání řádků, které je přijatelné ${ displaystyle alpha _ {k}}$ uspokojující Wolfe podmínky.
Soubor ${ displaystyle mathbf {s} _ {k} = alpha _ {k} mathbf {p} _ {k}}$ a aktualizovat ${ displaystyle mathbf {x} _ {k + 1} = mathbf {x} _ {k} + mathbf {s} _ {k}}$ .
${ displaystyle mathbf {y} _ {k} = { nabla f ( mathbf {x} _ {k + 1}) - nabla f ( mathbf {x} _ {k})}}$ .
${ displaystyle B_ {k + 1} = B_ {k} + { frac { mathbf {y} _ {k} mathbf {y} _ {k} ^ { mathrm {T}}} { mathbf { y} _ {k} ^ { mathrm {T}} mathbf {s} _ {k}}} - { frac {B_ {k} mathbf {s} _ {k} mathbf {s} _ { k} ^ { mathrm {T}} B_ {k} ^ { mathrm {T}}} { mathbf {s} _ {k} ^ { mathrm {T}} B_ {k} mathbf {s} _ {k}}}}$ .

${ displaystyle f ( mathbf {x})}$ označuje objektivní funkci, která má být minimalizována. Konvergenci lze zkontrolovat pozorováním normy gradientu, ${ displaystyle || nabla f ( mathbf {x} _ {k}) ||}$ . Li ${ displaystyle B_ {0}}$ je inicializováno pomocí ${ displaystyle B_ {0} = I}$ , první krok bude ekvivalentní a klesání, ale další kroky jsou čím dál rafinovanější ${ displaystyle B_ {k}}$ , aproximace pytloviny.

První krok algoritmu se provádí pomocí inverze matice ${ displaystyle B_ {k}}$ , které lze efektivně získat použitím Sherman – Morrisonův vzorec do kroku 5 algoritmu, dávat

{ displaystyle B_ {k + 1} ^ {- 1} = left (I - { frac { mathbf {s} _ {k} mathbf {y} _ {k} ^ {T}} { mathbf {y} _ {k} ^ {T} mathbf {s} _ {k}}} vpravo) B_ {k} ^ {- 1} vlevo (I - { frac { mathbf {y} _ { k} mathbf {s} _ {k} ^ {T}} { mathbf {y} _ {k} ^ {T} mathbf {s} _ {k}}} vpravo) + { frac { mathbf {s} _ {k} mathbf {s} _ {k} ^ {T}} { mathbf {y} _ {k} ^ {T} mathbf {s} _ {k}}}.}

To lze vypočítat efektivně bez dočasných matic, což si uvědomujeme ${ displaystyle B_ {k} ^ {- 1}}$ je symetrický, a to ${ displaystyle mathbf {y} _ {k} ^ { mathrm {T}} B_ {k} ^ {- 1} mathbf {y} _ {k}}$ a ${ displaystyle mathbf {s} _ {k} ^ { mathrm {T}} mathbf {y} _ {k}}$ jsou skaláry, používající expanzi jako

{ displaystyle B_ {k + 1} ^ {- 1} = B_ {k} ^ {- 1} + { frac {( mathbf {s} _ {k} ^ { mathrm {T}} mathbf { y} _ {k} + mathbf {y} _ {k} ^ { mathrm {T}} B_ {k} ^ {- 1} mathbf {y} _ {k}) ( mathbf {s} _ {k} mathbf {s} _ {k} ^ { mathrm {T}})}} {( mathbf {s} _ {k} ^ { mathrm {T}} mathbf {y} _ {k} ) ^ {2}}} - { frac {B_ {k} ^ {- 1} mathbf {y} _ {k} mathbf {s} _ {k} ^ { mathrm {T}} + mathbf {s} _ {k} mathbf {y} _ {k} ^ { mathrm {T}} B_ {k} ^ {- 1}} { mathbf {s} _ {k} ^ { mathrm {T }} mathbf {y} _ {k}}}.}

Při problémech se statistickým odhadem (např maximální pravděpodobnost nebo Bayesiánský závěr), důvěryhodné intervaly nebo intervaly spolehlivosti pro řešení lze odhadnout z inverzní konečné hesenské matice. Tyto veličiny jsou však technicky definovány skutečnou hesiánskou maticí a aproximace BFGS nemusí konvergovat ke skutečné hesenské matici.^[10]

Pozoruhodné implementace

Velký nelineární optimalizační software Artelys Knitro implementuje mimo jiné algoritmy BFGS a L-BFGS.
The GSL implementuje BFGS jako gsl_multimin_fdfminimizer_vector_bfgs2.^[11]
V MATLABu Optimalizace nástrojů, funkce fminunc^[12] používá BFGS s kubickým vyhledávání linek když je velikost problému nastavena na „střední měřítko“.^[13]
v R, je algoritmus BFGS (a verze L-BFGS-B, která umožňuje omezení polí) implementován jako možnost základní funkce optim ().^[14]
v SciPy, funkce scipy.optimize.fmin_bfgs implementuje BFGS.^[15] Je také možné spustit BFGS pomocí kteréhokoli z L-BFGS algoritmy nastavením parametru L na velmi velké číslo.

Viz také

Reference

^ Fletcher, Roger (1987), Praktické metody optimalizace (2. vyd.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8
^ Curtis, Frank E .; Que, Xiaocun (2015), „Quasi-Newton Algorithm for Nonconvex, Nonsmooth Optimization with Global Convergence Guarantees“, Výpočet matematického programování, 7 (4): 399–428, doi:10.1007 / s12532-015-0086-2
^ Nocedal & Wright (2006), strana 24
^ Byrd, Richard H .; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), „Algoritmus omezené paměti pro optimalizaci vázaných vazeb“, SIAM Journal on Scientific Computing, 16 (5): 1190–1208, CiteSeerX 10.1.1.645.5814, doi:10.1137/0916069
^ Broyden, C. G. (1970), „Konvergence třídy algoritmů minimalizace dvou řad“, Časopis Ústavu matematiky a jeho aplikací, 6: 76–90, doi:10.1093 / imamat / 6.1.76
^ Fletcher, R. (1970), „Nový přístup k variabilním metrickým algoritmům“, Počítačový deník, 13 (3): 317–322, doi:10.1093 / comjnl / 13.3.317
^ Goldfarb, D. (1970), "Rodina variabilních metrických aktualizací odvozených z variačních prostředků", Matematika výpočtu, 24 (109): 23–26, doi:10.1090 / S0025-5718-1970-0258249-6
^ Shanno, David F. (červenec 1970), „Úprava kvazi-Newtonových metod pro minimalizaci funkcí“, Matematika výpočtu, 24 (111): 647–656, doi:10.1090 / S0025-5718-1970-0274029-X, PAN 0274029
^ Fletcher, Roger (1987), Praktické metody optimalizace (2. vyd.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8
^ Ge, Ren-pu; Powell, M. J. D. (1983). "Konvergence proměnných metrických matic v neomezené optimalizaci". Matematické programování. 27. 123. doi:10.1007 / BF02591941.
^ „Vědecká knihovna GNU - dokumentace GSL 2.6“. www.gnu.org. Citováno 2020-11-22.
^ "Najít minimum neomezené funkce více proměnných - MATLAB fminunc". www.mathworks.com. Citováno 2020-11-22.
^ „Neomezená nelineární optimalizace :: Optimalizační algoritmy a příklady (Optimization Toolbox ™)“. web.archive.org. 2010-10-28. Citováno 2020-11-22.
^ „R: Univerzální optimalizace“. stat.ethz.ch. Citováno 2020-11-22.
^ "scipy.optimize.fmin_bfgs - SciPy v1.5.4 referenční příručka". docs.scipy.org. Citováno 2020-11-22.

Další čtení

Avriel, Mordechaj (2003), Nelineární programování: Analýza a metody, Dover Publishing, ISBN 978-0-486-43227-4
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006), „Newtonovské metody“, Numerická optimalizace: teoretické a praktické aspekty (Second ed.), Berlin: Springer, str. 51–66, ISBN 3-540-35445-X
Dennis, J. E., Jr.; Schnabel, Robert B. (1983), „Secant Methods for Unconstrained Minimization“, Numerické metody pro neomezenou optimalizaci a nelineární rovnice, Englewood Cliffs, NJ: Prentice-Hall, str. 194–215, ISBN 0-13-627216-9
Fletcher, Roger (1987), Praktické metody optimalizace (2. vyd.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8
Luenberger, David G.; Ye, Yinyu (2008), Lineární a nelineární programováníMezinárodní série v oblasti operačního výzkumu a managementu, 116 (Třetí vydání), New York: Springer, str. Xiv + 546, ISBN 978-0-387-74502-2, PAN 2423726
Kelley, C. T. (1999), Iterativní metody pro optimalizaci, Philadelphia: Society for Industrial and Applied Mathematics, str. 71–86, ISBN 0-89871-433-8
Nocedal, Jorge; Wright, Stephen J. (2006), Numerická optimalizace (2. vyd.), Berlín, New York: Springer-Verlag, ISBN 978-0-387-30303-1

[1] Fletcher, Roger (1987), Praktické metody optimalizace (2. vyd.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8

[2] Curtis, Frank E .; Que, Xiaocun (2015), „Quasi-Newton Algorithm for Nonconvex, Nonsmooth Optimization with Global Convergence Guarantees“, Výpočet matematického programování, 7 (4): 399–428, doi:10.1007 / s12532-015-0086-2

[3] Nocedal & Wright (2006), strana 24

[4] Byrd, Richard H .; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), „Algoritmus omezené paměti pro optimalizaci vázaných vazeb“, SIAM Journal on Scientific Computing, 16 (5): 1190–1208, CiteSeerX 10.1.1.645.5814, doi:10.1137/0916069

[5] Broyden, C. G. (1970), „Konvergence třídy algoritmů minimalizace dvou řad“, Časopis Ústavu matematiky a jeho aplikací, 6: 76–90, doi:10.1093 / imamat / 6.1.76

[6] Fletcher, R. (1970), „Nový přístup k variabilním metrickým algoritmům“, Počítačový deník, 13 (3): 317–322, doi:10.1093 / comjnl / 13.3.317

[7] Goldfarb, D. (1970), "Rodina variabilních metrických aktualizací odvozených z variačních prostředků", Matematika výpočtu, 24 (109): 23–26, doi:10.1090 / S0025-5718-1970-0258249-6

[8] Shanno, David F. (červenec 1970), „Úprava kvazi-Newtonových metod pro minimalizaci funkcí“, Matematika výpočtu, 24 (111): 647–656, doi:10.1090 / S0025-5718-1970-0274029-X, PAN 0274029

[9] Fletcher, Roger (1987), Praktické metody optimalizace (2. vyd.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8

[10] Ge, Ren-pu; Powell, M. J. D. (1983). "Konvergence proměnných metrických matic v neomezené optimalizaci". Matematické programování. 27. 123. doi:10.1007 / BF02591941.

[11] „Vědecká knihovna GNU - dokumentace GSL 2.6“. www.gnu.org. Citováno 2020-11-22.

[12] "Najít minimum neomezené funkce více proměnných - MATLAB fminunc". www.mathworks.com. Citováno 2020-11-22.

[13] „Neomezená nelineární optimalizace :: Optimalizační algoritmy a příklady (Optimization Toolbox ™)“. web.archive.org. 2010-10-28. Citováno 2020-11-22.

[14] „R: Univerzální optimalizace“. stat.ethz.ch. Citováno 2020-11-22.

[15] "scipy.optimize.fmin_bfgs - SciPy v1.5.4 referenční příručka". docs.scipy.org. Citováno 2020-11-22.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]