Czy istnieje jakakolwiek technika polegająca na wyszukiwaniu absolutnego minimum (maksimum) funkcji w przestrzeni wielowymiarowej?

Znam algorytm spadku gradientu, który może znaleźć lokalne minimum (maksimum) danej funkcji.

Czy jest jakaś modyfikacja spadku gradientu, która pozwala znaleźć absolutne minimum (maksimum), gdzie funkcja ma kilka ekstremów lokalnych?

Czy istnieją jakieś ogólne techniki, jak ulepszyć algorytm, który może znaleźć ekstremum lokalne, w celu znalezienia ekstremum ekstremalnego?

Zakładam, że mówisz o nieograniczonej minimalizacji. Twoje pytanie powinno określać, czy rozważasz konkretną strukturę problemu. W przeciwnym razie odpowiedź brzmi „nie”.

Najpierw powinienem rozwiać mit. Klasyczna metoda opadania gradientu (zwana również metodą najbardziej stromego spadku ) nie gwarantuje nawet znalezienia lokalnego minimalizatora. Zatrzymuje się, gdy znajdzie punkt krytyczny pierwszego rzędu, tj. Punkt, w którym gradient zanika. W zależności od konkretnej funkcji, która jest minimalizowana i punktu początkowego, możesz bardzo dobrze skończyć w punkcie siodłowym lub nawet w globalnym maksymalizatorze!

Rozważmy na przykład i punkt początkowy . Najbardziej stromy kierunek zniżania to . Jeden krok metody z dokładnym wyszukiwaniem linii pozostawia cię w gdzie zanika gradient. Niestety, jest to punkt siodłowy. Można to zrealizować, badając warunki optymalności drugiego rzędu. Ale teraz wyobraź sobie, że funkcja to . Tutaj jest nadal punktem siodłowym, ale liczbowo warunki drugiego rzędu mogą ci nie powiedzieć. Ogólnie rzecz biorąc, powiedzmy, że ustalono, że Heski ma wartość własną równą$f(x,y) = x^2 - y^2$$(x_0,y_0) := (1,0)$$-\nabla f(1,0) = (-2,0)$$(0,0)$$f(x,y) = x^2 - 10^{-16} y^2$$(0,0)$$\nabla^2 f(x^*,y^*)$$-10^{-16}$. Jak to czytasz? Czy to ujemna krzywizna czy błąd numeryczny? Co powiesz na ?$+10^{-16}$

Rozważmy teraz funkcję taką jak

$x_0 = -2$

Obecnie praktycznie wszystkie metody optymalizacji oparte na gradiencie cierpią z tego powodu. Twoje pytanie naprawdę dotyczy globalnej optymalizacji . Ponownie odpowiedź brzmi nie, nie ma ogólnych przepisów na modyfikację metody, aby zagwarantować zidentyfikowanie globalnego minimalizatora. Po prostu zadaj sobie pytanie: jeśli algorytm zwraca wartość i mówi, że jest globalnym minimalizatorem, w jaki sposób sprawdziłbyś, czy to prawda?

Istnieją globalne metody optymalizacji. Niektórzy wprowadzają randomizację. Niektórzy stosują strategie wielokrotnego startu. Niektórzy wykorzystują strukturę problemu, ale są to przypadki szczególne. Wybierz książkę o globalnej optymalizacji. Spodoba ci się.

Prawdopodobnie nie ma jednej uniwersalnej odpowiedzi na twoje pytanie. Ale możesz przyjrzeć się symulowanym algorytmom wyżarzania lub innym podejściom, które opierają się na metodach Markowa w łańcuchu Monte Carlo (MCMC). Można je również łączyć z lokalnymi metodami, takimi jak opadanie gradientu.

istnieje wiele odniesień do „globalnej optymalizacji sieci neuronowych”. techniki są podobne do symulowanego wyżarzania [patrz inna odpowiedź]. podstawową ideą jest ponowne uruchomienie opadania gradientu sieci, rozpoczynając od wielu różnych punktów początkowych masy, losowo lub systematycznie próbkowanych. każdy wynik spadku gradientu jest wtedy jak „próbka”. im więcej próbek zostanie pobranych, tym większe prawdopodobieństwo, że jedna z próbek jest globalnym optymalnym, szczególnie jeśli funkcja celu jest „dobrze zachowana” w sensie ciągłości, różniczkowania itp.

referencje online

[1] Globalna optymalizacja wag sieci neuronowych autorstwa Hamm et al

[2] Globalne podejście optymalizacyjne do szkolenia sieci neuronowej Voglis / Lagaris

[3] Kalibracja sztucznych sieci neuronowych przez Global Optimization Pinter

[4] Globalna optymalizacja sieci neuronowych za pomocą deterministycznego podejścia hybrydowego Beliakov

[5] Globalna optymalizacja do szkolenia w sieci neuronowej Shang / Wah

Zasadniczo trudno jest pod względem obliczeniowym zoptymalizować wielowymiarowe funkcje niewypukłe. Twardość występuje w różnych smakach (kryptograficzna, NP-twarda). Jednym ze sposobów na to jest to, że modele mieszanki (takie jak mieszanka Guassianów lub HMM) są trudne do nauczenia, ale byłoby to łatwe (*), gdyby można było skutecznie zmaksymalizować prawdopodobieństwo. Aby uzyskać wyniki dotyczące trudności uczenia się HMM, patrz http://alex.smola.org/journalclub/AbeWar92.pdf http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36 http: // www.math.ru.nl/~terwijn/publications/icgiFinal.pdf

(*) modulo zwykłe warunki niedegeneracji i identyfikowalności

muszę się nie zgodzić z Dominique. w połowie lat osiemdziesiątych Hajek wykazał, że wyżarzanie nie wypukłego problemu w pewnych ściśle określonych warunkach gwarantuje osiągnięcie globalnego minimum: http://dx.doi.org/10.1287/moor.13.2.311