Wie kann man intelligent versuchen, Konvexität auszuschließen?

Ich möchte eine komplizierte Zielfunktion minimieren und bin mir nicht sicher, ob sie konvex ist. Gibt es einen netten Algorithmus, der zu beweisen versucht, dass er nicht konvex ist? Natürlich könnte der Algorithmus dies nicht beweisen. In diesem Fall würde ich nicht wissen, ob er konvex ist oder nicht, und das ist in Ordnung. Ich möchte nur versuchen, Konvexität auszuschließen, bevor ich viel Zeit damit verbringe, analytisch festzustellen, ob die Zielfunktion konvex ist, indem ich beispielsweise versuche, das Problem in einer als konvex bekannten Standardform umzuschreiben. Ein schneller Test wäre der Versuch, von verschiedenen Ausgangspunkten aus zu minimieren. Wenn auf diese Weise mehrere lokale Minima gefunden werden, ist dies nicht konvex. Aber ich habe mich gefragt, ob es einen besseren Algorithmus gibt, der für dieses Ziel entwickelt wurde.

$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\}$

Eine Reihe praktisch nützlicher Konvexitäts- / Nichtkonvexitätsprüfungen finden Sie unter (Selbstausschluss, ich bin der dritte Autor in diesem Artikel):

R. Fourer, C. Maheshwari, A. Neumaier, D. Orban und H. Schichl, Konvexitäts- und Konkavitätsdetektion in Computergraphen. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.

Es ist zu beachten, dass es viele Funktionen gibt, die im interessierenden Bereich konvex sind, aber nicht leicht diszipliniert werden können, dh in einer der Formen geschrieben werden, die von strukturierten konvexen Lösern wie CVX benötigt werden .

Eine Funktion kann ohne mehrere Minima nicht konvex sein. Es gibt eine Vielzahl von Optimierungsmethoden, die (lineare oder nichtlineare) konjugierte Gradienteniterationen anwenden, die abgeschnitten werden, wenn eine negative Operatornorm berechnet wird. Der negative Wert gibt eine Richtung mit negativer Krümmung an (was bei konvexen Funktionalen nicht möglich ist). Wenn eine negative Krümmung selten auftritt, konvergieren diese Methoden in einer kleinen Anzahl von Optimierungsiterationen. (Wenn ein Qualitätsvorkonditionierer verfügbar ist, sollten auch die inneren Schritte schnell konvergieren.)