Jak w inteligentny sposób wykluczyć wypukłość?

Chcę zminimalizować skomplikowaną funkcję celu i nie jestem pewien, czy jest ona wypukła. Czy istnieje fajny algorytm, który próbuje udowodnić, że nie jest wypukły? Oczywiście algorytm może tego nie udowodnić, w takim przypadku nie wiedziałbym, czy jest wypukły, czy nie, i to jest OK; Chcę po prostu spróbować wykluczyć wypukłość, zanim spędzę dużo czasu próbując analitycznie ustalić, czy funkcja celu jest wypukła, na przykład, próbując przepisać problem w standardowej formie znanej jako wypukła. Jednym szybkim testem będzie próba zminimalizowania z różnych punktów początkowych, a jeśli w ten sposób znajdzie się wiele lokalnych minimów, to nie będzie wypukła. Zastanawiałem się jednak, czy istnieje lepszy algorytm, który został zaprojektowany z myślą o tym celu.

Funkcja wypukła musi spełniać dla wszystkich i w dziedzinie definicji. Możesz po prostu spróbować zweryfikować tę formułę dla dużej liczby par i kilku wartości , np. .$f(\alpha x + (1-\alpha)y) \le \alpha f(x) + (1-\alpha)f(y)$$\alpha\in(0,1)$$x,y$$x,y$$\alpha$$\alpha=\{1/4,1/2,3/4\}$

Aby zapoznać się z szeregiem praktycznych testów weryfikacyjnych wypukłości / niekonwekcyjności, zobacz (samorzeczenie się, jestem trzecim autorem tego artykułu):

R. Fourer, C. Maheshwari, A. Neumaier, D. Orban i H. Schichl, Wykrywanie wypukłości i wklęsłości w grafach obliczeniowych. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.

Należy zauważyć, że istnieje wiele funkcji, które są wypukłe w dziedzinie zainteresowań, ale nie można ich łatwo „zdyscyplinować”, tj. Napisane w jednej z form wymaganych przez ustrukturyzowane wypukłe rozwiązania, takie jak CVX .

Funkcja może być niewypukła bez wielu minimów. Istnieje wiele metod optymalizacji, które stosują (iteracje liniowe lub nieliniowe) iteracje gradientu sprzężonego, obcinane przy obliczaniu normy operatora ujemnego. Wartość ujemna wskazuje kierunek krzywizny ujemnej (co nie może się zdarzyć w przypadku wypukłych funkcjonałów). Jeśli rzadko występuje krzywizna ujemna, metody te zbiegają się w niewielkiej liczbie iteracji optymalizacyjnych. (Jeśli dostępny jest wysokiej jakości warunek wstępny, kroki wewnętrzne również powinny się szybko zbiegać).