Dlaczego niewypukłość powinna stanowić problem w optymalizacji?

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.

optimization nonconvex

— Prokop Hapala
źródło

Kluczowym słowem jest tutaj „ogólnie” - możesz konstruować dowolnie nieprzyjemne funkcjonale, szczególnie w bardzo dużych wymiarach, które są w zasadzie „wszystkimi punktami siodłowymi”. Z drugiej strony specyficzne klasy nie wypukłych funkcjonałów mogą być bardzo dobrze zachowane, szczególnie jeśli zastosujesz odpowiednie strategie globalizacji.

— Christian Clason

Myślę, że optymalna teoria sterowania i aplikacje do inżynierii / badań operacyjnych kładą duży nacisk na poprawność / solidność, podczas gdy uważasz, że dostanie się gdzieś „wystarczająco dobrze” jest wystarczająco dobre. Mogą istnieć limity wydajności (konwergencja musi być zagwarantowana, aby trajektoria robota była obliczana w czasie) lub limity poprawności (jeśli zmienisz nieco parametry problemu, nieoczekiwanie nie otrzymasz zupełnie innego wyniku). Nie wystarczy więc uzyskać optymalne punkty, konieczne jest również, aby miały określone właściwości.

— Kirill

Odpowiedzi:

$\arg\min f(x)$

Rozwiązanie kandydujące: szczególny wybór zmiennej decyzyjnej i odpowiadającej jej wartości obiektywnej , ORAZ $x^\star$ $f(x^\star)$
Dowód optymalności: matematyczny dowód, że wybór jest globalnie optymalny, tj. Że dla każdego wyboru . $x^\star$ $f(x) \ge f(x^\star)$ $x$

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. $f$ $x^\star$ $\nabla f(x^\star)=0$ $f$ $\nabla f$ $x^\star$ $x^\star$

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. $f$ $\nabla f(x^\star)=0$ $f$ $\nabla f(x)=0$ $x^\star$ $\nabla 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ć!

— Richard Zhang
źródło

optymalizacja globalna vs. lokalna to zupełnie inna kwestia. Ale reszta ma sens. Czy można powiedzieć więcej o „nie może nawet zagwarantować, że x jest lokalnym minimum na podstawie samej informacji o gradiencie”, lub lepiej to zilustrować?

— Prokop Hapala

Załóżmy, że mamy funkcje i jako czarne skrzynki (tzn. Możemy tylko oceniać, ale nie widzimy ich formy). Punkt

powoduje, że oba gradienty zanikają, tj.

, ale punkt jest tylko lokalnym minimum dla

. W rzeczywistości ich drugie pochodne są w tym momencie również zerowe, więc dwa scenariusze są identyczne z samymi pierwszymi dwoma pochodnymi!

f (x) = x^{3}

$f(x)=x^3$

g (x) = x^{4}

$g(x)=x^4$

x = 0

$x=0$

f^{'} (x) = 0

$f'(x)=0$

g^{'} (x) = 0

$g'(x)=0$

g

$g$

— Richard Zhang

AHA, OK, zawsze automatycznie przyjąć, bezwładność => że algorytm nie wydają się zbiegać z punktu w

w ogóle. Ale oczywiście używamy dodatkowych informacji (bezwładności) z poprzednich kroków, a nie tylko gradientu w jednym punkcie.

x = 0

$x=0$

g (x) = x^{3}

$g(x)=x^3$

— Prokop Hapala

Rozumiem twój punkt widzenia. I być może właśnie dlatego w ścisłym sensie matematycznym optymalizacja niewypukła jest uważana za trudną. Ale nadal bardziej interesuje mnie praktyczne zastosowanie, w którym heurystyka (którą uważam za naturalną część algorytmu) zawiodłaby.

— Prokop Hapala

Co z quasiconvexity? Zgodnie z tą logiką ((

wystarczy), czy quasiconvex problemy nie byłyby tak łatwe do optymalizacji jak problemy wypukłe ?. Rozumiem, że to ostatnie nie jest prawdziwe (problemy wypukłe są nadal łatwiejsze).

\nabla f (x) = 0

$\nabla f(x)=0$

— Amelio Vazquez-Reina

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.

— spektr
źródło

OK, myślę, że to inny problem ... problem globalnej optymalizacji, która jest wyraźnie trudna i nierozwiązywalna w większości sytuacji. Ale nie o tym ludzie mówią w odniesieniu do optymalizacji niewypukłej, gdzie mówią, że NP-trudno znaleźć lokalne minimum i wiele algorytmów może utknąć w punkcie siodłowym.

— Prokop Hapala

@ProkopHapala Moje komentarze bardziej odnosiły się do cytatu Wiele praktycznych problemów o istotnym znaczeniu 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 , zwłaszcza że OP mówił o tym, jak proste zajęli się oni problemami niewypukłymi w badaniach. Dla mnie dokładne rozwiązanie to dążenie do globalnie optymalnego rozwiązania (lub czegoś bliskiego). Chciałem więc namalować rzeczywiste wyzwania związane z tymi komentarzami.

— spektr

Rozumiem. Ściśle mówiąc, masz rację, ale myślę, że to nie dotyczy tego, co miałem na myśli ... być może powinienem był to lepiej sformułować.

— Prokop Hapala

Problemem są punkty siodłowe, omówione w poście, który podłączyłeś. Ze streszczenia jednego z powiązanych artykułów :

Jednak ogólnie trudno jest zagwarantować, że takie algorytmy są nawet zbieżne z lokalnym minimum, ze względu na istnienie skomplikowanych struktur punktów siodełka w dużych wymiarach. Wiele funkcji ma zdegenerowane punkty siodłowe, tak że pochodne pierwszego i drugiego rzędu nie mogą ich rozróżnić z lokalnymi optymami . W tym artykule wykorzystujemy pochodne wyższego rzędu, aby uniknąć tych punktów siodłowych: projektujemy pierwszy skuteczny algorytm, który gwarantuje zgodność z lokalnym optimum trzeciego rzędu (podczas gdy istniejące techniki są co najwyżej drugim rzędem). Pokazujemy również, że trudno jest rozszerzyć to na znalezienie lokalnych optymów czwartego rzędu.

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.

$x^2y+y^2$

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.

— LKlevin
źródło

x^{2} y + y^{2}

$x^2y+y^2$

Musisz spojrzeć na to z innej strony. Nie chodzi o to, że wiemy, że stochastyczne zejście gradientu zawiedzie, ale o to, że nie wiemy, że się powiedzie. W przypadku problemów z zabawkami jest to mało prawdopodobne w praktyce, ale może się zdarzyć w przypadku problemów z wyższymi wymiarami. Założę się, że dla twoich problemów chemicznych nigdy tak się nie stanie, ale ciężko byłoby mi to udowodnić.

— LKlevin