Metoda quasi-Newtona - Quasi-Newton method

Metody quasi-Newtona to metody używane do znajdowania zer lub lokalnych maksimów i minimów funkcji, jako alternatywa dla metody Newtona. Można ich użyć, jeśli jakobian lub hes jest niedostępny lub jest zbyt drogi do obliczenia w każdej iteracji. Metoda „pełnego” Newtona wymaga jakobianu do wyszukiwania zer lub heskiego do znajdowania ekstremów.

Szukaj zer: znajdowanie korzeni

Metoda Newtona znaleźć zerowych funkcji wielu zmiennych określał , gdzie jest lewa odwrotny od Jacobiego matrycy z oceniano . ${\displaystyle g}$${\ Displaystyle x_ {n + 1} = x_ {n} - [J_ {g} (x_ {n})] ^ {-1} g (x_ {n})}$${\ Displaystyle [J_ {g} (x_ {n})] ^ {-1}}$ ${\ Displaystyle J_ {g} (x_ {n})}$${\displaystyle g}$${\displaystyle x_{n}}$

Ściśle mówiąc, każda metoda, która zastępuje dokładny jakobian przybliżeniem, jest metodą quasi-Newtona. Na przykład, prostym przykładem jest metoda akordów (gdzie jest zastępowana przez dla wszystkich iteracji). Podane poniżej metody optymalizacji odnoszą się do ważnej podklasy metod quasi-Newtonowych, czyli metod siecznych. ${\ Displaystyle J_ {g} (x_ {n})}$${\ Displaystyle J_ {g} (x_ {n})}$${\ Displaystyle J_ {g} (x_ {0})}$

Korzystanie z metod opracowanych do znajdowania ekstremów w celu znalezienia zer nie zawsze jest dobrym pomysłem, ponieważ większość metod używanych do znajdowania ekstremów wymaga, aby użyta macierz była symetryczna. Chociaż obowiązuje to w kontekście wyszukiwania ekstremów, rzadko sprawdza się podczas wyszukiwania zer. „Dobra” i „zła” metoda Broydena to dwie metody powszechnie używane do znajdowania ekstremów, które można również zastosować do znalezienia zer. Inne metody, które mogą być stosowane są metody kolumny aktualizacji The odwrotny sposób kolumny aktualizacji The quasi-Newtona metodą najmniejszych kwadratów , a pseudo-Newtona odwrotną metodą najmniejszych kwadratów .

Ostatnio metody quasi-Newtona zostały zastosowane do znalezienia rozwiązania wielu sprzężonych układów równań (np. problemy interakcji płyn-struktura lub problemy interakcji w fizyce). Pozwalają one na znalezienie rozwiązania, rozwiązując każdy system składowy oddzielnie (co jest prostsze niż system globalny) w sposób cykliczny, iteracyjny, aż do znalezienia rozwiązania systemu globalnego.

Szukaj ekstremów: optymalizacja

Poszukiwanie minimum lub maksimum funkcji o wartościach skalarnych to nic innego jak poszukiwanie zer gradientu tej funkcji. Dlatego metody quasi-Newtona można łatwo zastosować do znalezienia ekstremów funkcji. Innymi słowy, jeśli jest gradientem , to poszukiwanie zer funkcji o wartościach wektorowych odpowiada poszukiwaniu ekstremów funkcji o wartościach skalarnych ; jakobian z teraźniejszości staje się Heskim z . Główna różnica polega na tym, że macierz Hesja jest macierzą symetryczną , w przeciwieństwie do jakobianu przy wyszukiwaniu zer . Większość metod quasi-Newtonowych stosowanych w optymalizacji wykorzystuje tę właściwość. ${\displaystyle g}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$

W optymalizacji , metody quasi-Newtona (szczególny przypadek metody zmiennej metryki ) są algorytmy dla znalezienia lokalnego minimum i maksimum z funkcji . Metody quasi-Newtona opierają się na metodzie Newtona w celu znalezienia punktu stacjonarnego funkcji, gdzie gradient wynosi 0. Metoda Newtona zakłada, że ​​funkcja może być lokalnie aproksymowana jako kwadratowa w obszarze wokół optimum i wykorzystuje pierwszą i drugą pochodne, aby znaleźć punkt stacjonarny. W wyższych wymiarach metoda Newtona wykorzystuje gradient i macierz Hessian drugich pochodnych funkcji do zminimalizowania.

W metodach quasi-Newtonowych nie ma potrzeby obliczania macierzy Hessów. Hessian jest aktualizowany poprzez analizę kolejnych wektorów gradientu. Metody quasi-Newtona są uogólnieniem metody siecznych w celu znalezienia pierwiastka pierwszej pochodnej dla problemów wielowymiarowych. W wielu wymiarach równanie siecznych jest niedostatecznie określone , a metody quasi-Newtona różnią się sposobem, w jaki ograniczają rozwiązanie, zazwyczaj przez dodanie prostej aktualizacji niskiego rzędu do bieżącego oszacowania hessu.

Pierwszy algorytm quasi-Newtona został zaproponowany przez Williama C. Davidona , fizyka pracującego w Argonne National Laboratory . W 1959 r. opracował pierwszy algorytm quasi-Newtona: formułę aktualizacji DFP , która została później spopularyzowana przez Fletchera i Powella w 1963 r., ale jest obecnie rzadko używana. Najpopularniejszymi algorytmami quasi-Newtona są obecnie formuła SR1 (dla „symetrycznej rangi jeden”), metoda BHHH , rozpowszechniona metoda BFGS (sugerowana niezależnie przez Broydena, Fletchera, Goldfarba i Shanno w 1970 r.) oraz jej niski -rozszerzenie pamięci L-BFGS . Klasa Broydena jest liniową kombinacją metod DFP i BFGS.

Formuła SR1 nie gwarantuje, że macierz aktualizacji zachowa dodatnią jednoznaczność i może być używana do rozwiązywania nieokreślonych problemów. Metoda Broydena nie wymaga, aby macierz aktualizacji była symetryczna i służy do znalezienia pierwiastka ogólnego układu równań (zamiast gradientu) poprzez aktualizację jakobianu (zamiast heskiego).

Jedną z głównych zalet metod quasi-Newtona nad metodą Newtona jest to, że macierz Hess (lub w przypadku metod quasi-Newtona jej aproksymacja) nie musi być odwracana. Metoda Newtona i jej pochodne, takie jak metody punktów wewnętrznych , wymagają odwrócenia hesjanu, co jest zwykle realizowane przez rozwiązywanie układu równań liniowych i często jest dość kosztowne. W przeciwieństwie do tego, metody quasi-Newtona zwykle generują oszacowanie bezpośrednio. ${\ Displaystyle B}$${\ Displaystyle B ^ {-1}}$

Podobnie jak w metodzie Newtona , do znalezienia minimum funkcji używa się przybliżenia drugiego rzędu . Szereg Taylora z wokół iterate jest ${\displaystyle f(x)}$${\displaystyle f(x)}$

${\ Displaystyle f (x_ {k} + \ Delta x) \ w przybliżeniu f (x_ {k}) + \ nabla f (x_ {k}) ^ {\ operatorname {T}} \ \ Delta x + {\ Frac { 1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,}$

gdzie ( ) jest gradientem i przybliżeniem do macierzy Hess . Gradient tego przybliżenia (w odniesieniu do ) wynosi ${\ Displaystyle \ nabla f}$${\ Displaystyle B}$${\ Displaystyle \ Delta x}$

${\ Displaystyle \ nabla f (x_ {k} + \ delta x) \ w przybliżeniu \ nabla f (x_ {k}) + B \ \ delta x}$

a ustawienie tego gradientu na zero (co jest celem optymalizacji) zapewnia krok Newtona:

${\ Displaystyle \ Delta x = - B ^ {-1} \ nabla f (x_ {k}).}$

Przybliżenie Hess jest wybrane, aby spełnić ${\ Displaystyle B}$

${\ Displaystyle \ nabla f (x_ {k} + \ delta x) = \ nabla f (x_ {k}) + B \ \ delta x}$

które nazywa się siecznym równaniem (seria Taylora samego gradientu). W więcej niż jednym wymiarze jest niedookreślony . W jednym wymiarze rozwiązanie i zastosowanie kroku Newtona ze zaktualizowaną wartością jest równoważne z metodą siecznych . Różne metody quasi-Newtona różnią się doborem rozwiązania równania siecznych (w jednym wymiarze wszystkie warianty są równoważne). Większość metod (ale z wyjątkami, takimi jak metoda Broydena ) poszukuje rozwiązania symetrycznego ( ); ponadto, warianty wymienione poniżej mogą być motywowane znalezieniem aktualizacji, która jest jak najbardziej zbliżona do jakiejś normy ; czyli , gdzie jest pewną dodatnio określoną macierzą, która definiuje normę. Przybliżona wartość początkowa jest często wystarczająca do osiągnięcia szybkiej konwergencji, chociaż nie ma ogólnej strategii do wyboru . Zauważ, że powinno być dodatnio-definitywne. Nieznana jest aktualizowana przy zastosowaniu kroku Newtona obliczonego przy użyciu aktualnej przybliżonej macierzy Hess : ${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle B ^ {T} = B}$${\displaystyle B_{k+1}}$${\ Displaystyle B_ {k}}$${\ Displaystyle B_ {k + 1} = \ operatorname {argmin} _ {B} \ | B-B_ {k} \ | _ {V}}$${\ Displaystyle V}$${\displaystyle B_{0}=\beta ja}$${\ Displaystyle \ beta}$${\displaystyle B_{0}}$${\displaystyle x_{k}}$${\ Displaystyle B_ {k}}$

• ${\ Displaystyle \ Delta x_ {k} = - \ alfa _ {k} B_ {k} ^ {-1} \ nabla f (x_ {k})}$, z wybranymi do spełnienia warunków Wolfe ;${\ Displaystyle \ alfa}$
• ${\ Displaystyle x_ {k + 1} = x_ {k} + \ delta x_ {k}}$;
• Gradient obliczony w nowym punkcie i${\ Displaystyle \ nabla f (x_ {k + 1})}$

${\ Displaystyle y_ {k} = \ nabla f (x_ {k + 1}) - \ nabla f (x_ {k})}$

służy do aktualizacji przybliżonej wartości Hessian lub bezpośrednio jej odwrotności za pomocą wzoru Shermana-Morrisona . ${\displaystyle B_{k+1}}$${\ Displaystyle H_ {k + 1} = B_ {k + 1} ^ {-1}}$

• Kluczową właściwością aktualizacji BFGS i DFP jest to, że jeśli jest określony dodatnio i zostanie wybrany w celu spełnienia warunków Wolfe'a, to również jest określony dodatnio.${\ Displaystyle B_ {k}}$${\ Displaystyle \ alfa _ {k}}$${\displaystyle B_{k+1}}$

Najpopularniejsze formuły aktualizacji to:

metoda	${\displaystyle \displaystyle B_{k+1}=}$	${\ Displaystyle H_ {k + 1} = B_ {k + 1} ^ {-1} =}$
BFG	${\ Displaystyle B_ {k} + {\ Frac {y_ {k} y_ {k} ^ {\ operator {T}}} {y_ {k} ^ {\ operator {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 \ lewo (I-{\ Frac {\ Delta x_ {k} y_ {k} ^ {\ operator {T}}} {y_ {k} ^ {\ operator {T}} \ Delta x_ {k} }}\right)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} } \Delta x_{k}}}\right)+{\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} ^ {\ operator {T}} \ \ Delta x_ {k }}}\,\Delta x_{k}^{\mathrm {T} }}$	${\ Displaystyle H_ {k} + {\ Frac {(\ Delta x_ {k}-H_ {k} y_ {k}) \ Delta x_ {k} ^ {\ operatorname {T}} H_ {k}} {\ Delta x_{k}^{\mathrm {T} }H_{k}\,y_{k}}}}$
Rodzina Broydenów	${\ Displaystyle (1-\ varphi _ {k}) B_ {k + 1} ^ {\ tekst {BFGS}} + \ varphi _ {k} B_ {k + 1} ^ {\ tekst {DFP}} \ quad \varphi \in [0,1]}$
DFP	${\ Displaystyle \ lewo (I-{\ Frac {y_ {k} \, \ Delta x_ {k} ^ {\ operator {T}}} {y_ {k} ^ {\ operator {T}} \ \ Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T } }\,\Delta x_{k}}}}$	${\ Displaystyle H_ {k} + {\ Frac {\ Delta x_ {k} \ Delta x_ {k} ^ {\ operator {T}}} {\ Delta x_ {k} ^ {\ operator {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}) ^ {\ operator {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}}$

Inne metody to metoda Pearsona, metoda McCormicka, symetryczna metoda Broydena (PSB) Powella oraz metoda Greenstadta.

Związek z inwersją macierzy

Gdy jest wypukłą funkcją kwadratową z dodatnio-określoną funkcją Hessian , można by oczekiwać, że macierze wygenerowane metodą quasi-Newtona będą zbieżne do odwrotności Hessian . Tak jest w przypadku klasy metod quasi-Newtonowskich opartych na aktualizacjach o najmniejszej zmianie. ${\displaystyle f}$${\ Displaystyle B}$${\ Displaystyle H_ {k}}$${\ Displaystyle H = B ^ {-1}}$

Wybitne wdrożenia

Implementacje metod quasi-Newtonowych są dostępne w wielu językach programowania. Godne uwagi implementacje obejmują:

• GNU Octave wykorzystuje w swojej fsolvefunkcji formę BFGS z rozszerzeniami regionu zaufania .

• Biblioteka naukowa GNU implementuje algorytm Broyden-Fletcher-Goldfarb-Shanno ( BFGS ).

• Mathematica zawiera solwery quasi-Newtona.
• NAG biblioteka zawiera liczne procedury w celu zminimalizowania lub maksymalizacji funkcji, które wykorzystują algorytmy quasi Newtona.
• W MATLAB za Optimization Toolbox , że fminunczastosowania funkcji (między innymi metodami) Do BFGS Metoda quasi-Newtona. Wiele ograniczonych metod zestawu narzędzi optymalizacji wykorzystuje BFGS i wariant L-BFGS .
• R jest optimuniwersalnym optymalizacji rutynowe wykorzystuje BFGS sposób za pomocą method="BFGS".
• Scipy .optimize ma fmin_bfgs. W scipy rozszerzenie Pythona The scipy.optimize.minimizeFunkcja ta obejmuje, między innymi metodami, a BFGS realizacji.

Zobacz też

• Metoda BFGS
  • L-BFG
  • SOWA-QN
• Metoda Broydena
• Formuła aktualizacji DFP
• Metoda Newtona
• Metoda Newtona w optymalizacji
• Formuła SR1

Bibliografia

Dalsza lektura

• Bonnans, JF; Gilbert, J.Ch.; Lemaréchal, C .; Sagastizábal, CA (2006). Optymalizacja numeryczna: aspekty teoretyczne i numeryczne (druga red.). Skoczek. Numer ISBN 3-540-35445-X.
• Fletcher, Roger (1987), Praktyczne metody optymalizacji (2nd ed.), New York: John Wiley & Sons , ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999). „Metody Quasi-Newtona” . Optymalizacja numeryczna . Nowy Jork: Springer. s. 192-221. Numer ISBN 0-387-98793-2.
• Prasa, WH; Teukolski SA; Vetterling, WT; Flannery, BP (2007). „Punkt 10.9. Quasi-Newtona lub zmienne metody metryczne w wielowymiarowych” . Przepisy numeryczne: The Art of Scientific Computing (3rd ed.). Nowy Jork: Cambridge University Press. Numer ISBN 978-0-521-88068-8.
• Wagi, LE (1985). Wprowadzenie do optymalizacji nieliniowej . Nowy Jork: MacMillan. s. 84-106. Numer ISBN 0-333-32552-4.