BFGS vs. Koniugatowa metoda gradientowa

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.

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.$n$$n$

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.

$m$$m$

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$

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.