Metoda quasi-Newtona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metody quasi-Newtonowskie (nazywane również metodami zmiennej metryki) są dobrze znanymi algorytmami 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[edytuj]

Jak w metodzie Newtona, stosujemy aproksymacje drugiego stopnia w celu znalezienia minimym 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ż[edytuj]

Bibliografia[edytuj]

  • 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. ISBN 0-387-98793-2.
  • Edwin K.P.Chong and Stanislaw H.Zak, An Introduction to Optimization 2ed, John Wiley & Sons Pte. Ltd. August 2001.