Metody quasi-newtonowskie (nazywane również metodami zmiennej metryki) – algorytmy znajdowania ekstremów lokalnych funkcji. Metody quasi-newtonowskie bazują na metodzie Newtona znajdowania punktów stacjonarnych funkcji. Metoda Newtona zakłada, że funkcja może być lokalnie aproksymowana funkcją kwadratową w otoczeniu optimum, oraz używają pierwszych i drugich pochodnych (gradient i hesjan) w celu znalezienia punktów stacjonarnych.
W metodzie quasi-Newtona hesjan (macierz drugich pochodnych) minimalizowanej funkcji nie musi być obliczany. Hesjan jest przybliżany przez analizowanie kolejnych wektorów gradientu. Metody Quasi-Newtona są uogólnieniem metody siecznych znajdowania pierwiastków pierwszej pochodnej na problem wielowymiarowy. W przypadku wielowymiarowym równanie siecznej jest wyznaczane w trakcie działania algorytmu. Metody quasi-newtonowskie różnią się między sobą sposobem ograniczeń rozwiązania, zazwyczaj przez dodawanie nieznacznej poprawki do przybliżanego w każdym kroku hesjanu.
Pierwszy algorytm quasi-newtonowski został zaproponowany przez W.C. Davidon, fizyka z Argonne National Laboratory.
Opis metody Jak w metodzie Newtona, stosowane są aproksymacje drugiego stopnia w celu znalezienia minimum funkcji Rozwinięcie w szereg Taylora funkcji wyraża się wzorem:
gdzie jest gradientem , a jej hesjanem.
Szereg Taylora samego gradientu:
rozwiązanie równania daje pierwszy krok:
jednak jest nieznana. W jednowymiarowym problemie znajdowanie i wykonywanie newtonowskiego kroku z zaktualizowaną wartością jest równoważne metodzie siecznych. W problemie wielowymiarowym jest wyznaczana.
Stosuje się wiele metod do wyznaczania rozwiązania równania siecznej, które jest symetryczne i najbliższe aktualnie aproksymowanej wartości zgodnie z pewną metryką Aproksymowana wartość początkowa jest zazwyczaj wystarczająca do osiągnięcia szybkiej zbieżności. nieznany jest aktualizowana przez stosowanie newtonowskiego kroku obliczanego przy użyciu hesjanu z dobraną by spełnić warunek Wolfa;
Gradient obliczany w nowym punkcie i
są używane do poprawienia hesjanu lub bezpośrednio jego odwrotności używająć wzoru Shermana-Morrisona.
Najpopularniejsze metody obliczania przybliżeń:
Metoda DFP BFGS Broyden Broyden Family SR1
Zobacz też metoda gradientu prostego optymalizacja
Bibliografia Eventually W.C. Davidon’s paper published. William C. Davidon, Variable Metric Method for Minimization, SIOPT Volume 1 Issue 1, Pages 1-17, 1991. Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. . Edwin K.P.Chong and Stanislaw H.Zak, An Introduction to Optimization 2ed, John Wiley & Sons Pte. Ltd. August 2001.
Kategoria:Metody numeryczne Kategoria:Metody optymalizacji Kategoria:Isaac Newton