Rozwiązywanie nieograniczonych problemów z optymalizacją nieliniową na GPU

18

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

4

Biorąc pod uwagę niewielki rozmiar problemów, nie sądzę, aby wybór algorytmu (np. BFGS) był największym wyzwaniem. Zamiast tego zminimalizuje obciążenie komunikacyjne procesora GPU <->. Prawdopodobnie najlepszym sposobem na to będzie równoległe rozwiązywanie wielu problemów na GPU. Załaduj je wszystkie naraz, rozwiąż je wszystkie naraz, pobierz wyniki wszystkie naraz. Nie mam konkretnej porady na temat algorytmu, ale powiem, że GPU są lepsze z pętlami niż z gałęziami.

— Michael Grant

1

@Michael C. Grant: Cóż, narzut komunikacyjny może być łatwo ukryty przez obliczenia w moim przypadku, więc nie jest to wąskie gardło, jestem bardzo skłonny do używania BFGS o ograniczonej pamięci lub standardowego BFGS tutaj, ale nie jestem pewien, czy istnieją lepsze podejście.

— user0002128

Niektóre osoby zaimplementowały LBFGS z CUDA .

— BenC

8

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.

— LKlevin
źródło

0

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

— Tolga Birdal
źródło

2

Levenberg-Marquart jest przeznaczony dla nieliniowych najmniejszych kwadratów. Nie sądzę, żeby wspominał coś o najmniejszych kwadratach.

— Kurt

0

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

— Nikos M.
źródło