Kvazi-Newtonova metoda - Quasi-Newton method

Kvazi-Newtonovy metody jsou metody používané buď k vyhledání nul, nebo lokálních maxim a minim funkcí, jako alternativa k Newtonově metodě. Mohou být použity, pokud Jacobian nebo Hesián není k dispozici nebo je příliš nákladné na výpočet při každé iteraci. Plný" Newtonova metoda vyžaduje jakobiána, aby hledal nuly, nebo pytlovinu pro hledání extrémů.

Hledat nuly: nález root

Newtonova metoda najít nuly funkce ${displaystyle g}$ více proměnných je dáno vztahem ${displaystyle x_ {n + 1} = x_ {n} - [J_ {g} (x_ {n})] ^ {- 1} g (x_ {n})}$ , kde ${displaystyle [J_ {g} (x_ {n})] ^ {- 1}}$ je vlevo inverzní z Jacobian matrix ${displaystyle J_ {g} (x_ {n})}$ z ${displaystyle g}$ hodnoceno pro ${displaystyle x_ {n}}$ .

Přesně řečeno, jakákoli metoda, která nahradí přesnou Jacobian ${displaystyle J_ {g} (x_ {n})}$ s aproximací je kvazi-Newtonova metoda.^[1] Například metoda akordů (kde ${displaystyle J_ {g} (x_ {n})}$ je nahrazen ${displaystyle J_ {g} (x_ {0})}$ pro všechny iterace) je jednoduchý příklad. Níže uvedené metody pro optimalizace odkazují na důležitou podtřídu kvazi-Newtonových metod, secantových metod.^[2]

Použití metod vyvinutých k nalezení extrémů za účelem nalezení nul není vždy dobrý nápad, protože většina metod používaných k hledání extrémů vyžaduje, aby použitá matice byla symetrická. I když to platí v kontextu hledání extrémů, zřídka to platí při hledání nul. Broydenovy „dobré“ a „špatné“ metody jsou dvě metody běžně používané k nalezení extrémů, které lze také použít k nalezení nul. Další metody, které lze použít, jsou metoda aktualizace sloupců, inverzní metoda aktualizace sloupce, kvazi-Newtonova metoda nejmenších čtverců a metoda kvazi-Newtonových inverzních metod nejmenších čtverců.

Nověji byly k nalezení řešení více spojených systémů rovnic (např. Problémy interakce tekutina-struktura nebo interakční problémy ve fyzice) použity kvazi-Newtonovy metody. Umožňují najít řešení cyklickým a iterativním řešením každého jednotlivého systému samostatně (což je jednodušší než globální systém), dokud není nalezeno řešení globálního systému.^[2]^[3]

Hledat extrémy: optimalizace

Všimněte si, že hledání minima nebo maxima funkce se skalární hodnotou není nic jiného než hledání nul spád této funkce lze snadno použít kvazi-Newtonovy metody k nalezení extrémů funkce. Jinými slovy, pokud ${displaystyle g}$ je gradient ${displaystyle f}$ , poté vyhledejte nuly funkce s vektorovou hodnotou ${displaystyle g}$ odpovídá hledání extrémů funkce skalární hodnoty ${displaystyle f}$ ; jakobián z ${displaystyle g}$ se nyní stává hesiánem z ${displaystyle f}$ . Hlavní rozdíl je v tom hesenská matice je symetrická matice, na rozdíl od Jacobian kdy hledání nul. Většina kvazi-Newtonových metod používaných při optimalizaci využívá tuto vlastnost.

v optimalizace, kvazi-Newtonovy metody (zvláštní případ proměnné-metrické metody) jsou algoritmy pro hledání místních maxima a minima z funkce. Kvazi-Newtonovy metody jsou založeny na Newtonova metoda najít stacionární bod funkce, kde gradient je 0. Newtonova metoda předpokládá, že funkci lze lokálně aproximovat jako a kvadratický v oblasti kolem optima a použije první a druhou derivaci k nalezení stacionárního bodu. Ve vyšších dimenzích Newtonova metoda používá gradient a Hesenská matice sekundy deriváty funkce, která má být minimalizována.

V kvazi-Newtonových metodách nemusí být vypočítána hesenská matice. Hesensko je místo toho aktualizováno analýzou postupných vektorů gradientů. Kvazi-Newtonovy metody jsou zobecněním sekansová metoda najít kořen první derivace pro vícerozměrné problémy. Ve více dimenzích je sekanční rovnice nedostatečně stanoveno a kvazi-Newtonovy metody se liší v tom, jak omezují řešení, typicky přidáním jednoduché aktualizace s nízkým hodnocením k současnému odhadu Hessian.

První kvazi-Newtonův algoritmus navrhl William C. Davidon, fyzik pracující v Argonne National Laboratory. V roce 1959 vyvinul první kvazi-Newtonův algoritmus: Vzorec pro aktualizaci DFP, který byl později popularizován Fletcherem a Powellem v roce 1963, ale dnes se používá jen zřídka. Nejběžnější kvazi-Newtonovy algoritmy jsou v současné době Vzorec SR1 (pro „symetrický první stupeň“), BHHH metoda, rozšířená Metoda BFGS (nezávisle navrhli Broyden, Fletcher, Goldfarb a Shanno v roce 1970) a jeho rozšíření s nízkou pamětí L-BFGS. Broydenova třída je lineární kombinací metod DFP a BFGS.

Vzorec SR1 nezaručuje zachování aktualizační matice pozitivní jednoznačnost a lze jej použít pro neurčité problémy. The Broydenova metoda nevyžaduje, aby byla aktualizační matice symetrická a používá se k nalezení kořene obecného systému rovnic (spíše než přechodu) aktualizací Jacobian (spíše než pytloviny).

Jednou z hlavních výhod kvazi-Newtonových metod Newtonova metoda je to Hesenská matice (nebo v případě kvazi-Newtonových metod jeho aproximace) ${displaystyle B}$ není nutné převracet. Newtonova metoda a její deriváty jako např vnitřní bodové metody, vyžadují, aby byla pytlovina obrácena, což se obvykle provádí řešením a soustava lineárních rovnic a je často docela nákladný. Naproti tomu kvazi-Newtonovy metody obvykle generují odhad ${displaystyle B ^ {- 1}}$ přímo.

Jako v Newtonova metoda, jeden používá aproximaci druhého řádu k nalezení minima funkce ${displaystyle f (x)}$ . The Taylor série z ${displaystyle f (x)}$ kolem iterace je

{displaystyle f (x_ {k} + Delta x) přibližně f (x_ {k}) + abla f (x_ {k}) ^ {mathrm {T}}, Delta x + {frac {1} {2}} Delta x ^ {mathrm {T}} B, Delta x,}

kde ( ${displaystyle abla f}$ ) je spád, a ${displaystyle B}$ přiblížení k Hesenská matice^[4]. Gradient této aproximace (s ohledem na ${displaystyle Delta x}$ ) je

{displaystyle abla f (x_ {k} + Delta x) přibližně abla f (x_ {k}) + B, Delta x,}

a nastavení tohoto přechodu na nulu (což je cílem optimalizace) poskytuje Newtonův krok:

{displaystyle Delta x = -B ^ {- 1} abla f (x_ {k}).}

Hesenská aproximace ${displaystyle B}$ je vybrán k uspokojení

{displaystyle abla f (x_ {k} + Delta x) = abla f (x_ {k}) + B, Delta x,}

který se nazývá sekansová rovnice (Taylorova řada samotného gradientu). Ve více než jedné dimenzi ${displaystyle B}$ je podurčeno. V jedné dimenzi řešení pro ${displaystyle B}$ a použití Newtonova kroku s aktualizovanou hodnotou je ekvivalentní s sekansová metoda. Různé kvazi-Newtonovy metody se liší výběrem řešení sečancové rovnice (v jedné dimenzi jsou všechny varianty ekvivalentní). Většina metod (ale s výjimkami, jako je Broydenova metoda ) hledat symetrické řešení ( ${displaystyle B ^ {T} = B}$ ); dále uvedené varianty lze motivovat vyhledáním aktualizace ${displaystyle B_ {k + 1}}$ to je co nejblíže ${displaystyle B_ {k}}$ v některých norma; to je ${displaystyle B_ {k + 1} = operatorname {argmin} _ {B} | B-B_ {k} | _ {V}}$ , kde ${displaystyle V}$ je nějaký pozitivně definitivní matice který definuje normu. Přibližná počáteční hodnota ${displaystyle B_ {0} = eta I}$ k dosažení rychlé konvergence je často dostačující, ačkoli neexistuje žádná obecná strategie, kterou lze zvolit ${displaystyle eta}$ ^[5]. Všimněte si, že ${displaystyle B_ {0}}$ by měl být kladný-definitivní. Neznámý ${displaystyle x_ {k}}$ je aktualizován použitím Newtonova kroku vypočítaného pomocí aktuální přibližné hesenské matice ${displaystyle B_ {k}}$ :

${displaystyle Delta x_ {k} = - alpha _ {k} B_ {k} ^ {- 1} abla f (x_ {k})}$ , s ${displaystyle alpha}$ vybrán, aby uspokojil Wolfe podmínky;
${displaystyle x_ {k + 1} = x_ {k} + Delta x_ {k}}$ ;
Gradient vypočítaný v novém bodě ${displaystyle abla f (x_ {k + 1})}$ , a

{displaystyle y_ {k} = abla f (x_ {k + 1}) - abla f (x_ {k})}

se používá k aktualizaci přibližné hesenské hodnoty ${displaystyle B_ {k + 1}}$ , nebo přímo jeho inverzní ${displaystyle H_ {k + 1} = B_ {k + 1} ^ {- 1}}$ za použití Sherman – Morrisonův vzorec.

Klíčovou vlastností aktualizací BFGS a DFP je, že pokud ${displaystyle B_ {k}}$ je kladně definitivní a ${displaystyle alpha _ {k}}$ je tedy vybrán tak, aby splňoval podmínky Wolfe ${displaystyle B_ {k + 1}}$ je také kladně definitivní.

Nejpopulárnější vzorce pro aktualizaci jsou:

Metoda	${displaystyle displaystyle B_ {k + 1} =}$	${displaystyle H_ {k + 1} = B_ {k + 1} ^ {- 1} =}$
BFGS	${displaystyle B_ {k} + {frac {y_ {k} y_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}} Delta x_ {k}}} - {frac {B_ {k} Delta x_ {k} (B_ {k} Delta x_ {k}) ^ {mathrm {T}}} {Delta x_ {k} ^ {mathrm {T}} B_ {k}, Delta x_ {k} }}}$	${displaystyle left (I- {frac {Delta x_ {k} y_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}} Delta x_ {k}}} ight) H_ {k } vlevo (I- {frac {y_ {k} Delta x_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}} Delta x_ {k}}} vpravo) + {frac { Delta x_ {k} Delta x_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}}, Delta x_ {k}}}}$
Broyden	${displaystyle B_ {k} + {frac {y_ {k} -B_ {k} Delta x_ {k}} {Delta x_ {k} ^ {mathrm {T}}, Delta x_ {k}}}, Delta x_ { k} ^ {mathrm {T}}}$	${displaystyle H_ {k} + {frac {(Delta x_ {k} -H_ {k} y_ {k}) Delta x_ {k} ^ {mathrm {T}} H_ {k}} {Delta x_ {k} ^ {mathrm {T}} H_ {k}, y_ {k}}}}$
Broydenova rodina	${displaystyle (1-varphi _ {k}) B_ {k + 1} ^ {ext {BFGS}} + varphi _ {k} B_ {k + 1} ^ {ext {DFP}}, quad varphi in [0, 1]}$
DFP	${displaystyle left (I- {frac {y_ {k}, Delta x_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}}, Delta x_ {k}}} ight) B_ {k} vlevo (I- {frac {Delta x_ {k} y_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}}, Delta x_ {k}}} v noci) + {frac {y_ {k} y_ {k} ^ {mathrm {T}}} {y_ {k} ^ {mathrm {T}}, Delta x_ {k}}}}$	${displaystyle H_ {k} + {frac {Delta x_ {k} Delta x_ {k} ^ {mathrm {T}}} {Delta x_ {k} ^ {mathrm {T}}, y_ {k}}} - { frac {H_ {k} y_ {k} y_ {k} ^ {mathrm {T}} H_ {k}} {y_ {k} ^ {mathrm {T}} H_ {k} y_ {k}}}}$
SR1	${displaystyle B_ {k} + {frac {(y_ {k} -B_ {k}, Delta x_ {k}) (y_ {k} -B_ {k}, Delta x_ {k}) ^ {mathrm {T} }} {(y_ {k} -B_ {k}, Delta x_ {k}) ^ {mathrm {T}}, Delta x_ {k}}}}$	${displaystyle H_ {k} + {frac {(Delta x_ {k} -H_ {k} y_ {k}) (Delta x_ {k} -H_ {k} y_ {k}) ^ {mathrm {T}}} {(Delta x_ {k} -H_ {k} y_ {k}) ^ {mathrm {T}} y_ {k}}}}$

Další metody jsou Pearsonova metoda, McCormickova metoda, Powellova symetrická metoda Broyden (PSB) a Greenstadtova metoda.^[2]

Vztah k inverzi matice

Když ${displaystyle f}$ je konvexní kvadratická funkce s pozitivním definitivním hesiánem ${displaystyle B}$ , dalo by se očekávat matice ${displaystyle H_ {k}}$ generované kvazi-Newtonovou metodou ke konvergenci k inverzní pytlovině ${displaystyle H = B ^ {- 1}}$ . To je skutečně případ třídy kvazi-Newtonových metod založených na aktualizacích s nejnižšími změnami.^[6]

Pozoruhodné implementace

Implementace kvazi-Newtonových metod jsou k dispozici v mnoha programovacích jazycích. Pozoruhodné implementace zahrnují:

GNU oktáva používá ve svém formátu BFGS fsolve funkce, s důvěryhodný region rozšíření.
Mathematica zahrnuje kvazi-Newtonovy řešitele.^[7]
The Knihovna NAG obsahuje několik rutin^[8] pro minimalizaci nebo maximalizaci funkce^[9] které používají kvazi-Newtonovy algoritmy.
V MATLABU Optimalizace nástrojů, fminunc funkce používá (mimo jiné metody) BFGS kvazi-Newtonova metoda.^[10] Mnoho z omezených metod, které používá sada nástrojů Optimalizace, používá BFGS a varianta L-BFGS.^[11]
R je optim rutina optimalizátoru pro obecné účely používá BFGS metoda pomocí method = "BFGS".^[12]
Scipy.optimize má fmin_bfgs. V SciPy rozšíření na Krajta, scipy.optimize.minimize funkce mimo jiné zahrnuje a BFGS implementace.^[13]

Viz také

Reference

^ Broyden, C. G. (1972). „Kvazi-Newtonovy metody“. V Murray, W. (ed.). Numerické metody pro neomezenou optimalizaci. London: Academic Press. str. 87–106. ISBN 0-12-512250-0.
^ ^A ^b ^C Haelterman, Rob (2009). „Analytická studie kvazi-Newtonovy metody nejmenších čtverců pro problémy interakce“. Disertační práce, Ghent University. Citováno 2014-08-14.
^ Rob Haelterman, Dirk Van Eester, Daan Verleyen (2015). „Urychlení řešení fyzikálního modelu uvnitř tokamaku pomocí metody (inverzní) aktualizace sloupce“. Journal of Computational and Applied Mathematics. 279: 133–144. doi:10.1016 / j.cam.2014.11.005.CS1 maint: používá parametr autoři (odkaz)
^ https://mathinsight.org/taylors_theorem_multivariable_introduction
^ Nocedal, Jorge; Wright, Stephen J. (2006). Numerická optimalizace. New York: Springer. str.142. ISBN 0-387-98793-2.
^ Robert Mansel Gower; Peter Richtarik (2015). „Randomizované kvazi-newtonské aktualizace jsou lineárně konvergentní maticové inverzní algoritmy“. arXiv:1602.01768 [matematika.NA ].
^ http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html
^ Skupina numerických algoritmů. „Index klíčových slov: Kvazi-Newton“. Manuál knihovny NAG, Mark 23. Citováno 2012-02-09.
^ Skupina numerických algoritmů. „E04 - minimalizace nebo maximalizace funkce“ (PDF). Manuál knihovny NAG, Mark 23. Citováno 2012-02-09.
^ http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html
^ http://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html
^ [1]
^ http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

Další čtení

Bonnans, J. F .; Gilbert, J. Ch .; Lemaréchal, C.; Sagastizábal, C. A. (2006). Numerická optimalizace: teoretické a numerické aspekty (Druhé vydání.). Springer. ISBN 3-540-35445-X.
Fletcher, Roger (1987), Praktické metody optimalizace (2. vyd.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8.
Nocedal, Jorge; Wright, Stephen J. (1999). „Kvazi-Newtonovy metody“. Numerická optimalizace. New York: Springer. str. 192–221. ISBN 0-387-98793-2.
Press, W. H .; Teukolsky, S. A .; Vetterling, W. T .; Flannery, B. P. (2007). „Oddíl 10.9. Kvazi-Newtonské nebo variabilní metrické metody ve vícerozměrech“. Numerické recepty: Umění vědecké práce na počítači (3. vyd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Scales, L. E. (1985). Úvod do nelineární optimalizace. New York: MacMillan. str. 84–106. ISBN 0-333-32552-4.

[1] Broyden, C. G. (1972). „Kvazi-Newtonovy metody“. V Murray, W. (ed.). Numerické metody pro neomezenou optimalizaci. London: Academic Press. str. 87–106. ISBN 0-12-512250-0.

[Haelterman-2] A ^b ^C Haelterman, Rob (2009). „Analytická studie kvazi-Newtonovy metody nejmenších čtverců pro problémy interakce“. Disertační práce, Ghent University. Citováno 2014-08-14.

[3] Rob Haelterman, Dirk Van Eester, Daan Verleyen (2015). „Urychlení řešení fyzikálního modelu uvnitř tokamaku pomocí metody (inverzní) aktualizace sloupce“. Journal of Computational and Applied Mathematics. 279: 133–144. doi:10.1016 / j.cam.2014.11.005.CS1 maint: používá parametr autoři (odkaz)

[4] ttps://mathinsight.org/taylors_theorem_multivariable_introduction

[5] Nocedal, Jorge; Wright, Stephen J. (2006). Numerická optimalizace. New York: Springer. str.142. ISBN 0-387-98793-2.

[Gower_and_Richtarik-6] Robert Mansel Gower; Peter Richtarik (2015). „Randomizované kvazi-newtonské aktualizace jsou lineárně konvergentní maticové inverzní algoritmy“. arXiv:1602.01768 [matematika.NA ].

[7] ttp://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html

[8] Skupina numerických algoritmů. „Index klíčových slov: Kvazi-Newton“. Manuál knihovny NAG, Mark 23. Citováno 2012-02-09.

[9] Skupina numerických algoritmů. „E04 - minimalizace nebo maximalizace funkce“ (PDF). Manuál knihovny NAG, Mark 23. Citováno 2012-02-09.

[10] ttp://www.mathworks.com/help/toolbox/optim/ug/fminunc.html

[11] ttp://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html

[12] [1]

[13] ttp://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]