Czy pochylenie gradientu można zastosować do funkcji niewypukłych?

Właśnie uczę się o optymalizacji i mam problem ze zrozumieniem różnicy między optymalizacją wypukłą i nie wypukłą. Z mojego zrozumienia funkcja wypukła to taka, w której „odcinek linii między dowolnymi dwoma punktami na wykresie funkcji znajduje się powyżej lub na wykresie”. W takim przypadku można zastosować algorytm spadku gradientu, ponieważ istnieje jedno minimum, a gradienty zawsze doprowadzą Cię do tego minimum.

A co z funkcją na tym rysunku:

Tutaj segment niebieskiej linii przecina się poniżej czerwonej funkcji. Jednak funkcja nadal ma jedno minimum, więc opadanie gradientu nadal doprowadziłoby cię do tego minimum.

Więc moje pytania to:

1) Czy funkcja na tej figurze jest wypukła, czy nie wypukła?

2) Jeśli nie jest wypukły, to czy nadal można zastosować wypukłe metody optymalizacji (opadanie gradientu)?

Wykreślona funkcja rzeczywiście nie jest wypukła. Jest jednak quasiconvex .

Spadek gradientu jest ogólną metodą ciągłej optymalizacji, więc może być i jest bardzo często stosowany do funkcji niewypukłych. Dzięki płynnej funkcji i rozsądnie dobranej wielkości kroku wygeneruje sekwencję punktów$x_1, x_2, \ldots$ o ściśle malejących wartościach $f(x_1) > f(x_2) > \ldots$.

Opadanie gradientu ostatecznie zbiegnie się w stacjonarny punkt funkcji, niezależnie od wypukłości. Jeśli funkcja jest wypukła, będzie to globalne minimum, ale jeśli nie, może to być lokalne minimum, a nawet punkt siodłowy.

Funkcje quasiconvex są interesującym przypadkiem. Każde lokalne minimum funkcji quasiconvex jest również globalnym minimum, ale funkcje quasiconvex mogą również mieć stacjonarne punkty, które nie są lokalnymi minimami (weź$f(x) = x^3$na przykład). Więc teoretycznie możliwe jest, że opadanie gradientu utknie w takim punkcie stacjonarnym i nie przejdzie do globalnej wartości minimalnej. W twoim przykładzie, jeśli ramię po lewej stronie wykresu idealnie się wyrówna, nachylenie gradientu może utknąć w tym miejscu. Jednak warianty takie jak metoda ciężkiej piłki mogą być w stanie „przetoczyć się” i osiągnąć globalną wartość minimalną.

Paweł wspomniał już o jednym ważnym punkcie:

• jeśli f jest wypukły, nie ma punktów siodłowych, a wszystkie lokalne minima są również globalne. W ten sposób GD (z odpowiednim krokiem) gwarantuje znalezienie globalnego minimalizatora.

To, co utrudnia optymalizację niewypukłą, to obecność punktów siodłowych i lokalnych minimów, w których gradient wynosi (0, ..., 0) i które mają dowolnie złą wartość obiektywną.

Znalezienie globalnego minmizera w takim ustawieniu jest na ogół trudne NP, a zamiast tego ustala się cel znalezienia lokalnego minimalizatora.

Należy jednak pamiętać, że:

• Prawdopodobieństwo, że GD utknie w siodle, wynosi w rzeczywistości 0 ( patrz tutaj ).
• Jednak obecność punktów siodłowych może znacznie spowolnić postęp GD w dół, ponieważ kierunki niskiej krzywizny są wykorzystywane zbyt wolno ( patrz tutaj )

W zależności od wymiarów problemu może być wskazane wybranie procedury optymalizacji drugiego rzędu.