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

15

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?

Michael
źródło
1
Zawsze możesz obliczyć gradient równolegle (dla metod quasi-Newtona z wykorzystaniem różnic skończonych) i uzyskać przyspieszenie proporcjonalne do liczby parametrów, tj. 10x-20x.
stali
@stali: Potrzebujesz optymalizacji w metodach quasi-Newtona. Obliczanie Hesji za pomocą skończonych różnic w ocenach funkcji nie jest naprawdę dobrym pomysłem. Obliczanie przybliżonych różnic skończonych gradientu w celu optymalizacji również nie jest dobrym pomysłem.
Geoff Oxberry
Wiele metod quasi-Newtonowych, takich jak BFGS, nie wymaga jawnego Hesji. Myślę, że używając gradientów, w połączeniu z L-BFGS, OP może szybko osiągnąć to, czego chce.
stali
@stali: Wskazałem, dlaczego użycie przybliżenia skończonej różnicy do gradientu byłoby złym pomysłem w mojej odpowiedzi. Zmniejszy to konwergencję poprzez wprowadzenie błędu po prawej stronie iteracji quasi-Newtona. Ponadto marnuje oceny funkcji, ponieważ nie ma możliwości ponownego użycia starych ocen (w przeciwieństwie do metod zastępczych). Korzystanie z BFGS rozwiązuje tylko połowę problemów z proponowanym podejściem.
Geoff Oxberry
Jest to bardziej odpowiedni komentarz, a nie odpowiedź. Ale nie mam wyboru, ponieważ nie mam wystarczającej liczby przedstawicieli, aby opublikować komentarz. Michael, mam bardzo podobny typ problemu: kosztowne oceny funkcji obejmujące złożone symulacje działające w klastrze. Czy kiedykolwiek znalazłeś kod odpowiedni do uruchomienia optymalizacji, gdy ocena funkcji obejmuje symulację w klastrze?
MoonMan

Odpowiedzi:

16

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ć:

H.~(xk)rek=-fa(xk),

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 α kH.~rekxkfafaxk+1=xk+αkrekαkto 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.

Geoff Oxberry
źródło
2
To dla mnie przyjemność całkowicie się mylić i nauczyć się czegoś nowego i przydatnego w tym procesie :).
Paweł
Dzięki! Jeszcze jedno wyjaśnienie: który z tych algorytmów jest w stanie wykonywać oceny funkcji równolegle? Na przykład na siatce k-way wykonującej iteracje n + 1, ..., n + k na podstawie tylko informacji uzyskanych z iteracji 1, ..., n?
Michael
k
3

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.

Zhan Dawei
źródło
2

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).

Chris Rackauckas
źródło
0

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) .

Paweł
źródło
5
O ile nie są dostępne gradienty precyzji maszyny (analitycznie, poprzez obliczenia przyległe, poprzez jakąś analizę wrażliwości w przód), to podejście nie jest naprawdę dobrym pomysłem; wymagałoby to ogromnej liczby symulacji na ocenę Hesji, a lepiej byłoby wziąć te oceny funkcji i użyć ich do zbudowania modelu zastępczego (na przykład BOBYQA; ORBIT mógłby zbudować model zastępczy wN.
-2

Oto rozwiązanie twojego problemu.

Opis metody matematycznej znajduje się w tym artykule .

Paweł
źródło
3
Witamy w SciComp.SE. Czy możesz podać szczegółowe informacje na temat podejścia opisanego w dokumencie i wdrożonego w oprogramowaniu? Jaka jest zastosowana metoda? Dlaczego to jest dobre? Co zapewnia takie podejście, czego nie obejmują inne odpowiedzi?
nicoguaro
2
Wygląda też na to, że to twoja praca. Jeśli to prawda, proszę to wyraźnie zaznaczyć w swojej odpowiedzi.
nicoguaro
@nicoguaro: dziękuję, ale wiem, jak klikać linki.
Michael
3
@Michael, to nie jest dla ciebie. Filozofią tej witryny jest zbiór odpowiedzi. Otrzymujesz dziś odpowiedź, ale w przyszłości ktoś może potrzebować takiej samej pomocy. Właśnie dlatego istnieją standardy de facto dotyczące dobrej odpowiedzi.
nicoguaro