Algorytmy optymalizacji równoległej dla problemu z bardzo kosztowną funkcją celu

Optymalizuję funkcję 10-20 zmiennych. Zła wiadomość jest taka, że ​​ocena każdej funkcji jest kosztowna, około 30 minut obliczeń szeregowych. Dobrą wiadomością jest to, że mam do dyspozycji klaster z kilkudziesięcioma węzłami obliczeniowymi.

Zatem pytanie: czy są dostępne algorytmy optymalizacji, które pozwolą mi efektywnie wykorzystać całą moc obliczeniową?

Po jednej stronie spektrum byłoby wyczerpujące poszukiwanie: podziel całą przestrzeń poszukiwań na drobną siatkę i obliczyć funkcję w każdym punkcie siatki niezależnie. Jest to z pewnością bardzo równoległe obliczenie, ale algorytm jest strasznie nieefektywny.

Po drugiej stronie spektrum byłyby algorytmy quasi-Newtona: inteligentnie zaktualizuj kolejną ocenę parametrów na podstawie wcześniejszej historii. Jest to wydajny algorytm, ale nie wiem, jak to zrobić równolegle: koncepcja „oszacowania parametrów na podstawie wcześniejszej historii” brzmi jak obliczenia szeregowe.

Algorytmy kwadratowe wydają się być gdzieś pośrodku: można zbudować początkowy „model zastępczy”, obliczając kilka wartości równolegle, ale nie wiem, czy pozostałe iteracje są równoległe.

Wszelkie sugestie dotyczące tego, jakie metody optymalizacji bez gradientu przydałyby się w klastrze? Czy dostępne są obecnie równoległe implementacje algorytmów optymalizacyjnych?

Jak stwierdza Paweł, bez dodatkowych informacji trudno jest udzielać rad bez założeń.

Przy 10–20 zmiennych i kosztownych ocenach funkcji istnieje tendencja do rekomendowania algorytmów optymalizacji bez pochodnych. Nie zgadzam się zdecydowanie z radą Paula: ogólnie potrzebujesz gradientu precyzji maszyny, chyba że używasz jakiejś specjalnej metody (na przykład stochastyczny spadek gradientu w uczeniu maszynowym wykorzysta formę celu, aby wymyślić rozsądny szacunki gradientu).

Każdy krok quasi-Newton będzie miał postać:

gdzie jest pewnym przybliżeniem macierzy Hesji, d k jest kierunkiem wyszukiwania, x k jest wartością zmiennych decyzyjnych przy bieżącej iteracji, f jest funkcją celu, a ∇ f jest gradientem celu, a zmienne decyzyjne są aktualizowane jak x k + 1 = x k + α k d k , gdzie α $\tilde{H}$$d_{k}$$x_{k}$$f$$\nabla{f}$$x_{k+1} = x_{k} + \alpha_{k}d_{k}$$\alpha_{k}$to wielkość kroku określona w pewien sposób (np. wyszukiwanie linii). Możesz uciec od przybliżenia Hesji na różne sposoby, a twoje iteracje zbiegną się, chociaż jeśli użyjesz czegoś w rodzaju przybliżonej skończonej różnicy Hesji za pomocą dokładnych gradientów, możesz cierpieć z powodu problemów z powodu złego warunkowania. Zazwyczaj Hesjan jest aproksymowany przy użyciu gradientu (na przykład metody typu BFGS z aktualizacjami 1-go rzędu dla Hesji).

Przybliżenie Hesji i gradientu zarówno różnicami skończonymi jest złym pomysłem z wielu powodów:

• będziesz miał błąd w gradiencie, więc zastosowana metoda quasi-Newtona jest zbliżona do znalezienia źródła funkcji szumu
• $N$$N$
• jeśli masz błąd w gradiencie, będziesz miał więcej błędów w swoim Hesji, co jest dużym problemem pod względem warunkowania układu liniowego
• $N^{2}$

Aby uzyskać jedną złą iterację quasi-Newtona, robisz coś w rodzaju do 420 ocen funkcji przy 30 minutach na ocenę, co oznacza, że ​​albo będziesz czekał chwilę na każdą iterację, albo będziesz potrzebuję dużego klastra tylko do oceny funkcji. Rzeczywiste rozwiązania liniowe będą składały się z macierzy 20 na 20 (co najwyżej!), Więc nie ma powodu, aby je równolegle łączyć. Jeśli możesz uzyskać informacje o gradiencie, na przykład rozwiązując problem przylegania, może być bardziej opłacalne, w takim przypadku warto spojrzeć na książkę taką jak Nocedal & Wright.

Jeśli zamierzasz wykonać wiele ocen funkcji równolegle, powinieneś zamiast tego spojrzeć na metody modelowania zastępczego lub na generowanie metod wyszukiwania zestawów, zanim podejmiesz podejście quasi-Newton. Klasyczne artykuły przeglądowe to te autorstwa Riosa i Sahinidisa na temat metod wolnych od pochodnych , które zostały opublikowane w 2012 roku i zapewniają naprawdę dobre, szerokie porównanie; artykuł porównawczy More and Wild z 2009 roku; podręcznik z 2009 r. „Wprowadzenie do optymalizacji bez pochodnych instrumentów” Conn, Scheinberg i Vicente; oraz artykuł przeglądowy na temat generowania metod wyszukiwania zestawów przez Kolda, Lewis i Torczon z 2003 roku.

Jak wspomniano powyżej, pakiet oprogramowania DAKOTA będzie implementował niektóre z tych metod, podobnie jak NLOPT , który implementuje DIRECT, oraz kilka zastępczych metod modelowania Powell. Możesz także rzucić okiem na MCS ; jest napisany w MATLAB, ale być może możesz przenieść implementację MATLAB na wybrany język. DAKOTA to przede wszystkim zbiór skryptów, których można użyć do uruchomienia drogiej symulacji i zebrania danych do algorytmów optymalizacyjnych, a NLOPT ma interfejsy w wielu językach, więc wybór języka programowania nie powinien stanowić dużego problemu przy korzystaniu z dowolnego pakietu oprogramowania; Nauka DAKOTA zajmuje jednak trochę czasu i ma do przeszukania ogromną ilość dokumentacji.

Być może szukasz algorytmów optymalizacji opartych na zastępczych parametrach. Algorytmy te wykorzystują modele zastępcze w celu zastąpienia rzeczywistych drogich obliczeniowo modeli podczas procesu optymalizacji i próbują znaleźć odpowiednie rozwiązanie, wykorzystując jak najmniej ocen modeli drogich obliczeniowo, jak to możliwe.

Myślę, że do rozwiązania problemu można zastosować metodę próbkowania w trybie Mode . Algorytm ten wykorzystuje model zastępczy RBF do aproksymacji drogiej funkcji celu i może obsłużyć ograniczenia nieliniowe. Co ważniejsze, wybiera wielu kandydatów do wykonania kosztownych ocen funkcji, dzięki czemu można dystrybuować tych kandydatów do obliczeń równoległych w celu dalszego przyspieszenia procesu wyszukiwania. Kod jest open source i napisany w MATLAB.

Odniesienie

Wang, L., Shan, S., i Wang, GG (2004). Metoda próbkowania dążąca do optymalizacji globalnej optymalizacji kosztownych funkcji czarnej skrzynki. Optymalizacja inżynieryjna, 36 (4), 419–438.

Nie jestem pewien, czy algorytm równoległy jest naprawdę tym, czego szukasz. Oceny funkcji są bardzo kosztowne. To, co chcesz zrobić, to zrównoleglenie samej funkcji, niekoniecznie algorytmu optymalizacji.

Jeśli nie możesz tego zrobić, to między gruntownym wyszukiwaniem a algorytmem Newtona znajduje się środek, to są to metody Monte Carlo. Możesz, na wielu różnych rdzeniach / węzłach, uruchomić ten sam algorytm, który jest podatny na lokalne optymima (powiedzmy algorytmy quasi-Newtona), ale wszystkie z losowymi warunkami początkowymi. W takim razie najlepiej zgadnąć, jakie są prawdziwe optymima, czyli minimum z minimum. Jest to trywialne do zrównoleglenia i może być użyte do rozszerzenia dowolnej metody. Chociaż nie jest idealnie wydajny, jeśli masz wystarczającą moc obliczeniową do dyspozycji, może zdecydowanie wygrać bitwę produktywności kontra wydajność algorytmu (jeśli masz dużą moc obliczeniową, może to zakończyć się, zanim skończysz tworzyć bardziej zaawansowany algorytm).

Wybór algorytmu optymalizacji (a tym samym jego równoległości) w dużym stopniu zależy od właściwości funkcji celu i ograniczeń. Nie wiedząc więcej na temat problemu, trudno jest udzielić jakiejkolwiek sensownej porady.

Ale z twoich rozważań na temat metod Newtona wnioskuję, że twoja funkcja celu jest zróżnicowana. Jeśli to możliwe, twój problem znacznie skorzysta na równoległym obliczeniu oceny funkcji. Jeśli nie jest to możliwe, możesz również rozważyć niedokładną metodę Newtona, która zastępuje dokładne gradienty / hessiany przybliżeniami różnic skończonych. Następnie możesz użyć wszystkich dostępnych procesorów, aby obliczyć każdy niezerowy element jakobianu, jak sugeruje @stali.

Aby uzyskać więcej informacji, przeczytaj Optymalizację numeryczną Nocedal & Wright, rozdział 7 . Istnieje wiele pakietów oprogramowania optymalizacyjnego, które implementują to równolegle. Jednym z najczęściej używanych freeware jest pakiet oprogramowania DAKOTA (Sandia National Labs) .

Oto rozwiązanie twojego problemu.

Opis metody matematycznej znajduje się w tym artykule .