Próbuję rozwiązać niektóre nieliniowe problemy optymalizacji nieliniowej na GPU (CUDA).
Funkcja celu jest gładką funkcją nieliniową, a jej gradient jest stosunkowo tani do obliczeń analitycznych, więc nie muszę się przejmować przybliżeniem numerycznym.
Chcę rozwiązać ten problem głównie z opcjami matematycznymi fp32 (z różnych powodów), więc która nieliniowa metoda optymalizacji jest bardziej odporna na błędy zaokrąglania, a jednocześnie ma dobrą wydajność? (np. sprzężony gradient / quasi-newton / region zaufania), czy ktoś wypróbował BFGS na GPU z dobrymi wynikami?
BTW, Hesjan, jeśli to konieczne, jest w moim przypadku stosunkowo niewielki (zwykle <64x64), ale muszę jednocześnie rozwiązać tysiące problemów optymalizacji na małą skalę.
optimization
cuda
użytkownik0002128
źródło
źródło
Odpowiedzi:
Zaimplementowałem dość szeroką gamę nieliniowych solverów na GPU, w tym LBFGS, Barzilai Borwein zejście gradientowe i nieliniowy gradient sprzężony.
W tym celu najbardziej nieskuteczny jest nieliniowy gradient sprzężony Dai i Yuan . Zasadniczo inna wersja nieliniowego gradientu sprzężonego może być bardziej wydajna (na przykład CG-DESCENT), ale może być również trudniejsza do wdrożenia.
LBFGS jest ogólnie bardzo dobrym wyborem i chyba, że naprawdę nie masz ochoty na pamięć, to prawdopodobnie najlepsze miejsce na rozpoczęcie.
Zarówno gradient sprzężony, jak i BFGS wymagają przeszukiwania linii, w których fp32 staje się problemem. Zamiast używać standardowych warunków Wolfe'a do wyszukiwania linii, sugerowałbym użycie przybliżonego warunku Wolfe'a sugerowanego tutaj . Artykuł jest trochę zaangażowany, ale ważne jest równanie 4.1. Zasadniczo wyraźnie wprowadzają precyzję, z jaką można obliczyć swoją funkcję.
Uwagi dotyczące GPU:
Masz wiele małych problemów, które nieco różnią się od mojego przypadku użycia jednego dużego problemu. Zastanów się nad uruchomieniem 1 problemu na blok GPU (a raczej wypaczenia), jeśli możesz zrównoleglić oceny funkcji i gradientu, aby użyć wszystkich wątków w bloku. W ten sposób nie stanowi problemu, jeśli różne problemy wymagają innej liczby iteracji.
Jeśli nie jest to opcja, wybrałbym solver LBFGS. Jeśli twoja funkcja jest dobrze zachowana, możesz po prostu użyć kroku o wielkości 1 (unikając przeszukiwania linii) i po prostu uruchomić wszystkie problemy dla określonej liczby iteracji.
źródło
Sugeruję, abyś używał Levenberg Marquardt (wariant regionu zaufania), ponieważ jest on używany w wielu praktycznych zastosowaniach i wykazuje bardzo dobrą wydajność prędkości względem dokładności. Co więcej, dla GPU istnieje kilka bibliotek (np. CuLM https://github.com/zitmen/cuLM ), które można wypróbować. Jeśli nie wykonają zadania, istnieje mnóstwo zasobów do wdrożenia. Wdrożenie LM wcale nie jest trudne. Należy tylko dbać o minimalizację komunikacji GPU. Aby uzyskać krótki pomysł:
http://on-demand.gputechconf.com/gtc/2012/presentations/S0231-Levenberg-Marquardt-Using-Block-Sparse-Matrices-on-CUDA.pdf
źródło
Być może symulowana procedura wyżarzania lepiej radzi sobie z błędami zaokrąglania (i jest łatwa do zrównoleglenia).
Zaczynasz od surowej siatki obszaru wyszukiwania i początkowego parametru „temperatura”
Na każdym kroku obliczasz możliwe punkty rozwiązania (można również zaakceptować punkty nierozwiązane, z pewnym prawdopodobieństwem odwrotnie analogicznym do temperatury)
Następnie zachowaj tylko rozwiązania na tym etapie i zwiększ temperaturę, co zapewnia bardziej drobnoziarniste ruszty do następnej iteracji
Rób to, aż temperatura <podany limit / próg dokładności
źródło