Algorytm Levenberga-Marquardta
Algorytm Levenberga-Marquardta – algorytm optymalizacji nieliniowej. Jest to algorytm iteracyjny, łączący w sobie cechy metody największego spadku i metody Gaussa-Newtona.
Sformułowanie problemu
[edytuj | edytuj kod]Mając daną serię danych gdzie szukamy dopasowania gdzie – wektor parametrów. Zakładamy, że najlepszym dopasowaniem jest to minimalizujące funkcjonał:
Algorytm Levenberga-Marquardta w ogólności znajduje rozwiązanie zadania optymalizacji nieliniowej funkcji dającej się zapisać w postaci:
gdzie i zakładamy, że Jak łatwo zauważyć, funkcjonał daje się zapisać w taki sposób. Dla uproszczenia, przedstawmy funkcje jako wektor (zwany wektorem rezydualnym). Wtedy Pochodne funkcji można zapisać przy użyciu Macierzy Jacobiego funkcji zdefiniowanego jako W ogólnym przypadku gradient funkcji można zapisać:
a jej Macierz Hessego:
W przypadku, gdy funkcje można aproksymować funkcjami liniowymi w otoczeniu interesującego nas punktu (wtedy jest bliskie zeru), lub gdy jest małe, hesjan funkcji przyjmuje prostszą postać:
a więc hesjan można otrzymać wprost mając dany jakobian wektora rezydualnego co jest charakterystyczne dla zadania najmniejszych kwadratów.
Opis metody
[edytuj | edytuj kod]Najprostszym podejściem do problemu minimalizacji funkcji jest metoda największego spadku, opisana schematem:
która jest, w ogólnym przypadku, wolno zbieżna. Aby poprawić jej zbieżność, można skorzystać z wiedzy o drugiej pochodnej minimalizowanej funkcji w badanym punkcie. Jednym z możliwych podejść jest rozwinięcie gradientu minimalizowanej funkcji w szereg Taylora:
i przyjęcie przybliżenia kwadratowego funkcji w otoczeniu do rozwiązania równania W ten sposób otrzymujemy metodę Gaussa-Newtona opisaną schematem:
gdzie hesjan funkcji nie musi być znany dokładnie i często wystarczy podane wcześniej przybliżenie. Niestety, szybkość zbieżności tej metody zależy od wyboru punktu początkowego, a konkretnie od liniowości minimalizowanej funkcji w otoczeniu punktu startowego. Kenneth Levenberg zauważył, że opisane metody (największego spadku i Gaussa-Newtona) nawzajem się uzupełniają i zaproponował następującą modyfikację kroku metody:
- (*)
wraz z następującym algorytmem:
- oblicz wartość na podstawie i równania (*),
- oblicz wartość błędu w punkcie
- jeśli błąd wzrósł, wróć do wartości zwiększ wartość -krotnie i wróć do kroku 1 (przybliżenie liniowe minimalizowanej funkcji w otoczeniu okazało się nie dość ścisłe, więc zwiększamy „wpływ” metody największego spadku),
- jeśli błąd zmalał, zaakceptuj ten krok i zmniejsz wartość -krotnie (założenie o liniowości minimalizowanej funkcji w otoczeniu okazało się wystarczająco ścisłe, więc zwiększamy „wpływ” metody Gaussa-Newtona).
W typowych zastosowaniach W przypadku, gdy jest duże, hesjan w zasadzie nie jest wykorzystywany. Donald Marquardt zauważył, że nawet w takiej sytuacji można wykorzystać informację zawartą w drugiej pochodnej minimalizowanej funkcji, poprzez skalowanie każdego komponentu wektora gradientu w zależności od krzywizny w danym kierunku (co pomaga w źle uwarunkowanych zadaniach minimalizacji typu error valley). Po uwzględnieniu poprawki Marquardta otrzymujemy następującą postać kroku metody:
gdzie:
Największą zaletą algorytmu Levenberga-Marquardta jest jego szybka zbieżność, w porównaniu z konkurencyjnymi metodami. Najkosztowniejszą operacją jest natomiast wyznaczenie macierzy odwrotnej, które w praktyce jest przeprowadzane w sposób przybliżony, na przykład przy użyciu metody SVD. Tym niemniej, nawet w najoszczędniejszych przypadkach koszt jednego kroku rośnie niedopuszczalnie wraz ze wzrostem rozmiaru zadania powyżej tysiąca parametrów. Z drugiej dla zadań o umiarkowanej ilości parametrów (rzędu kilkuset), metoda Levenberga-Marquardta jest dużo szybsza od metody największego spadku.
Zobacz też
[edytuj | edytuj kod]Linki zewnętrzne
[edytuj | edytuj kod]- Numerical Recipes in C, Chapter 15.5: Nonlinear models (en). fizyka.umk.pl. [zarchiwizowane z tego adresu (2009-04-19)].