Byłem bardzo zaskoczony, kiedy zacząłem czytać ogólnie o optymalizacji niewypukłej i zobaczyłem takie stwierdzenia:
Wiele ważnych problemów praktycznych jest niewypukłych, a większość problemów niewypukłych jest trudna (jeśli nie niemożliwa) do rozwiązania dokładnie w rozsądnym czasie. ( źródło )
lub
Zasadniczo trudno jest znaleźć lokalne minimum i wiele algorytmów może utknąć w punkcie siodłowym. ( źródło )
Codziennie robię rodzaj niewypukłej optymalizacji - mianowicie rozluźnienie geometrii molekularnej. Nigdy nie uważałem tego za coś podstępnego, powolnego i podatnego na utknięcie. W tym kontekście mamy wyraźnie wielowymiarowe, niewypukłe powierzchnie (> 1000 stopni swobody). Używamy głównie technik pierwszego rzędu pochodzących z najbardziej stromego zejścia i dynamicznego gaszenia, takich jak FIRE , które zbiegają się w kilkuset krokach do lokalnego minimum (mniej niż liczba DOF). Oczekuję, że po dodaniu stochastycznego hałasu musi być solidny jak diabli. (Globalna optymalizacja to inna historia)
Jakoś nie mogę sobie wyobrazić, jak powinna wyglądać powierzchnia energii potencjalnej , aby zablokować te metody optymalizacji lub je powoli zbiegać. Np. Bardzo patologiczny PES (ale nie z powodu niewypukłości) jest tą spiralą , ale nie jest to taki duży problem. Czy możesz podać przykładowy przykład patologicznego niewypukłego PES?
Więc nie chcę kłócić się z powyższymi cytatami. Mam raczej wrażenie, że coś tu brakuje. Być może kontekst.
źródło
Odpowiedzi:
Gdy jest wypukły, oba składniki są łatwo dostępne. Zejście gradientu lokalizuje rozwiązanie kandydujące które powoduje, że gradient zanika . Dowód optymalności wynika z prostego faktu nauczanego w MATH101, że jeśli jest wypukły, a jego gradient znika przy , to jest rozwiązaniem globalnym.x ⋆ ∇ f ( x ⋆ ) = 0 f ∇ f x ⋆ x ⋆fa x⋆ ∇ f( x⋆) = 0 fa ∇ f x⋆ x⋆
Gdy jest wypukłe, rozwiązanie kandydujące może być nadal łatwe do znalezienia, ale dowód optymalności staje się niezwykle trudny. Na przykład możemy uruchomić opadanie gradientu i znaleźć punkt . Ale gdy jest wypukłe, warunek jest konieczny, ale nie wystarcza już dla globalnej optymalności. Rzeczywiście, nie jest to nawet wystarczające dla lokalnej optymalności, tzn. Nie możemy nawet zagwarantować, że jest lokalnym minimum na podstawie samych informacji o gradiencie. Jednym z podejść jest wyliczenie wszystkich punktów spełniających , a może to być ogromne zadanie nawet na jednym lub dwóch wymiarach.fa ∇ f( x⋆) = 0 fa ∇ f( x ) = 0 x⋆ ∇ f( x ) = 0
Kiedy matematycy mówią, że większości problemów nie da się rozwiązać, naprawdę twierdzą, że nie da się zbudować dowodu (nawet lokalnej) optymalności . Ale w prawdziwym świecie często jesteśmy zainteresowani jedynie opracowaniem „wystarczająco dobrego” rozwiązania, które można znaleźć na nieskończoną liczbę sposobów. W przypadku wielu wysoce niep wypukłych problemów nasza intuicja podpowiada nam, że „wystarczająco dobre” rozwiązania są w rzeczywistości globalnie optymalne, nawet jeśli nie jesteśmy w stanie tego udowodnić!
źródło
Przykładem trudnego problemu niskiego wymiaru może być:
Biorąc pod uwagę, że osiągnąłeś lokalne minima, skąd możesz mieć pewność, że jest to coś tak zbliżonego jak minima globalne? Skąd wiesz, czy Twój wynik jest unikalnym optymalnym rozwiązaniem, biorąc pod uwagę, że jest optymalne globalnie? Jak stworzyć algorytm odporny na wszystkie wzgórza i doliny, aby się gdzieś nie utknął?
Przykładem takim jest sytuacja, w której sprawy mogą stać się trudne. Oczywiście nie wszystkie problemy są takie, ale niektóre są. Co gorsza, w środowisku przemysłowym funkcja kosztu może być czasochłonna, aby obliczyć ORAZ mieć problematyczną powierzchnię jak ta powyżej.
Przykład prawdziwego problemu
Przykładem, z którym mogę się zmierzyć w pracy, jest optymalizacja algorytmu naprowadzania pocisków, który mógłby być niezawodny w wielu warunkach startu. Za pomocą naszego klastra mogę uzyskać pomiary wydajności, których potrzebuję w około 10 minut dla pojedynczego warunku. Teraz, aby odpowiednio ocenić solidność, chcielibyśmy mieć przynajmniej próbkę warunków do oceny. Powiedzmy, że uruchamiamy sześć warunków, dzięki czemu ocena tej funkcji kosztów zajmuje godzinę.
Nieliniowa dynamika pocisków, dynamika atmosferyczna, dyskretne procesy czasowe itp. Powodują dość nieliniową reakcję na zmiany w algorytmie naprowadzania, co utrudnia optymalizację. Fakt, że ta funkcja kosztów nie jest wypukła, sprawia, że ocena dużego problemu jest czasochłonna. Przykładem takim jest to, w którym staramy się uzyskać jak najwięcej w wyznaczonym czasie.
źródło
Problemem są punkty siodłowe, omówione w poście, który podłączyłeś. Ze streszczenia jednego z powiązanych artykułów :
Zasadniczo możesz mieć funkcje, w których masz punkty siodłowe, których nie można odróżnić od lokalnych minimów, patrząc na 1., 2. i 3. pochodną. Możesz rozwiązać ten problem, przechodząc do optymalizatora wyższego rzędu, ale pokazują one, że sfinalizowanie lokalnego minimum 4-go rzędu jest trudne.
Możesz użyć szeregu heurystyk, aby uniknąć takich punktów, co może działać w wielu (najbardziej?) Rzeczywistych przykładach, ale nie można udowodnić, że zawsze działają.
W poście na blogu, który podlinkowałeś, omawiają również warunki, w których możesz uciec przed takimi punktami siodłowymi w czasie wielomianowym.
źródło