BFGS vs. Koniugatowa metoda gradientowa

25

Jakie uwagi powinienem wziąć pod uwagę przy wyborze między BFGS a gradientem sprzężonym w celu optymalizacji? Funkcją, którą próbuję dopasować do tych zmiennych, są funkcje wykładnicze; jednak faktyczna funkcja celu obejmuje między innymi integrację i jest bardzo kosztowna, jeśli w ogóle pomaga.

drjrm3
źródło
3
Cóż, BFGS jest z pewnością bardziej kosztowny pod względem przechowywania niż CG. Jeden wymaga utrzymania przybliżonego Hesji, podczas gdy drugi potrzebuje tylko kilku wektorów od ciebie. Z drugiej strony oba wymagają obliczenia gradientu, ale powiedziano mi, że dzięki BFGS można uniknąć przybliżania różnic skończonych zamiast pisać procedurę dla gradientu (ale wersja z różnicami skończonymi zbiega się nieco oczywiście wolniej niż ten, który wykorzystuje rzeczywiste gradienty). Jeśli masz funkcję automatycznego różnicowania, jedynym zmartwieniem jest przechowywanie.
JM,
trzeba dopasować tylko ~ 7 (zdecydowanie mniej niż 10) zmiennych oznacza, że ​​aproksymacja hessiana jest (najwyżej) poprawną macierzą 10x10? w takim przypadku, czy jedno jest szybsze od drugiego?
drjrm3
Nie sądzę, żeby istniała tak duża różnica prędkości; jeśli cokolwiek, myślę, że częścią twojego obliczenia, która prawdopodobnie zabrałaby najwięcej czasu, są kwadratury, które musisz zrobić dla oceny funkcji. Naprawdę powinieneś sam zrobić kilka eksperymentów, jeśli liczba parametrów jest tak mała, jak się twierdzi.
JM,

Odpowiedzi:

13

JM ma rację co do przechowywania. BFGS wymaga przybliżonego Hesji, ale możesz zainicjować go za pomocą macierzy tożsamości, a następnie po prostu obliczyć aktualizacje drugiego stopnia przybliżonego Hesji w miarę, jak masz dostępną informację o gradiencie, najlepiej analitycznie niż poprzez skończone różnice. BFGS jest metodą quasi-Newtona i będzie zbiegać się w mniejszej liczbie kroków niż CG, i ma nieco mniejszą tendencję do „utknięcia” i wymaga niewielkich poprawek algorytmicznych w celu osiągnięcia znacznego spadku dla każdej iteracji.

Natomiast CG wymaga produktów macierz-wektor, które mogą być przydatne, jeśli możesz obliczyć pochodne kierunkowe (ponownie, analitycznie lub używając różnic skończonych). Obliczanie różnic skończonych pochodnych kierunkowych będzie znacznie tańsze niż obliczanie różnic skończonych w Hesji, więc jeśli zdecydujesz się skonstruować algorytm przy użyciu różnic skończonych, po prostu oblicz bezpośrednio pochodną kierunkową. To spostrzeżenie jednak nie dotyczy BFGS, który obliczy przybliżonych Hesjan za pomocą wewnętrznych produktów informacji gradientowej.

Jeśli chodzi o wskaźniki konwergencji, jeśli jest liczbą zmiennych decyzyjnych w twoim problemie, to iteracje n CG w przybliżeniu są równe jednemu krokowi metody Newtona. BFGS jest metodą quasi-Newtona, ale taka sama obserwacja powinna się odbyć; prawdopodobnie uzyskasz zbieżność w mniejszej liczbie iteracji z BFGS, chyba że istnieje kilka kierunków CG, w których występuje duże zejście, a następnie po kilku iteracjach CG ponownie ją uruchomisz. Metody podobne do CG są tańsze, jeśli produkty matrycowo-wektorowe są tanie, a problem jest tak duży, że przechowywanie Hesji jest trudne lub niemożliwe. BFGS wymaga kilku produktów wektorów-wektorów do aktualizacji przybliżonego Hesji, więc każda iteracja BFGS będzie droższa, ale będziesz potrzebować mniej z nich, aby osiągnąć lokalne minimum.nn

Porównałbym dwa algorytmy małego problemu testowego dla twojej aplikacji, jeśli wiesz, że pamięć nie będzie problemem. Bez znajomości specyfiki twojego problemu, domyślam się, że BFGS będzie szybszy, ale naprawdę powinieneś przetestować dwa algorytmy, aby dowiedzieć się, który z nich będzie działał lepiej.

Na koniec słowo o automatycznym różnicowaniu: mając pewne doświadczenie z wewnętrzną funkcją automatycznego różnicowania (AD) dla Fortran ( DAEPACK ), mogę powiedzieć, że narzędzia AD są często wybredne. Mogą niekoniecznie być w stanie odróżnić generowany przez siebie kod. Istnieją dwa rodzaje narzędzi AD:

  • narzędzia AD typu source-to-source
  • przeciążenie operatora narzędzia AD

Narzędzia typu źródło-źródło to zasadniczo zmodyfikowane kompilatory, które pobierają napisany kod źródłowy, analizują go i automatycznie generują nowy kod źródłowy, który oblicza gradient funkcji w kodzie źródłowym. Przeciążanie operatorów Narzędzia AD wymagają użycia przeciążonych operatorów AD w kodzie źródłowym, aby można było obliczyć pochodne, co wymagałoby dodatkowego wysiłku z Twojej strony, aby obliczyć analityczne pochodne z AD.

Geoff Oxberry
źródło
22

mm

Z mojego doświadczenia wynika, że ​​BFGS z dużą ilością aktualizacji przechowuje informacje zbyt daleko od obecnego rozwiązania, aby były naprawdę przydatne w przybliżeniu nieobciążonego jakobianu, a można faktycznie stracić zbieżność, jeśli przechowujesz zbyt dużo. Istnieją „bez pamięci” warianty BFGS, które wyglądają bardzo podobnie do nieliniowych gradientów sprzężonych (patrz ostatnia aktualizacja opisana dla jednego z nich) tylko z tych powodów. Dlatego jeśli chcesz wykonać L-BFGS zamiast BFGS, problemy z pamięcią znikają i metody są powiązane . Niepotwierdzone dowody wskazują, że wznowienie pracy jest trudnym zagadnieniem, ponieważ czasami jest to zbędne, a czasem bardzo konieczne.

Twój wybór między tymi dwoma zależy również w dużym stopniu od problemów, którymi jesteś zainteresowany. Jeśli masz zasoby, możesz wypróbować oba problemy i zdecydować, które z nich będzie lepsze. Na przykład osobiście nie robię optymalizacji za pomocą tych algorytmów, ale zależy mi na rozwiązaniu układów równań nieliniowych. Dla tych stwierdziłem, że NCG działa lepiej i łatwiej jest wykonywać nieliniowe wstępne kondycjonowanie. BFGS jest bardziej niezawodny.

m

Peter Brune
źródło
Zupełnie zapomniałem o L-BFGS. +1 za to.
JM
15

W małych wymiarach dobrze zaimplementowana metoda BFGS jest na ogół zarówno szybsza, jak i bardziej niezawodna niż CG, szczególnie jeśli funkcja nie jest bardzo daleka od kwadratyki.

Ani BFGS, ani CG nie potrzebują żadnych założeń dotyczących wypukłości; tylko początkowe przybliżenie Hesji (dla BFGS) lub. warunek wstępny (dla CG) musi być określony pozytywnie. Ale zawsze można je wybrać jako matrycę tożsamości, w małych wymiarach bez większych szkód. Zobacz także /scicomp//a/3213/1117

W przypadku braku zaprogramowanego gradientu marnowanie liczbowych gradientów jest dużym marnotrawstwem, szczególnie gdy wartości funkcji są drogie. Zamiast tego należy stosować algorytm wolny od pochodnych. Zobacz http://archimedes.cheme.cmu.edu/?q=dfocomp na ostatnim badaniu.

Arnold Neumaier
źródło
Link daje mi komunikat „Nie znaleziono 404”, czy możesz to naprawić?
Stiefel,
@Stiefel: Naprawiłem to. Nowy link wskazuje na znacznie ulepszoną wersję.
Arnold Neumaier,