Как интеллигентно пытаться исключить выпуклость?

Я хочу минимизировать сложную целевую функцию, и я не уверен, является ли она выпуклой. Есть ли хороший алгоритм, который пытается доказать, что он не выпуклый? Конечно, алгоритм может не доказать это, и в этом случае я не буду знать, является ли он выпуклым или нет, и это нормально; Я просто хочу попытаться исключить выпуклость, прежде чем потратить много времени, пытаясь аналитически определить, является ли целевая функция выпуклой, например, пытаясь переписать задачу в стандартной форме, известной как выпуклая. Одним из быстрых тестов было бы попытаться свести к минимуму различные начальные точки, и если таким образом было найдено несколько локальных минимумов, то оно не выпукло. Но мне было интересно, есть ли лучший алгоритм, который был разработан с этой целью.

Выпуклая функция должна удовлетворять $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\}$,

Для ряда практически полезных тестов проверки выпуклости / невыпуклости, см. (Самоотречение, я третий автор в этой статье):

R. Fourer, C. Maheshwari, A. Neumaier, D. Orban, H. Schichl, Обнаружение выпуклостей и вогнутостей в вычислительных графах. Tree Walks для оценки выпуклости, INFORMS J. Computing 22 (2010), 26-43.

Обратите внимание, что есть много функций, которые являются выпуклыми в интересующей области, но не могут быть легко «дисциплинированными», то есть написаны в одной из форм, требуемых структурированными выпуклыми решателями, такими как CVX .

Функция может быть невыпуклой без кратных минимумов. Существует множество методов оптимизации, в которых применяются (линейные или нелинейные) итерации сопряженного градиента, усеченные при вычислении отрицательной нормы оператора. Отрицательное значение указывает направление отрицательной кривизны (что не может иметь место для выпуклых функционалов). Если отрицательная кривизна встречается редко, эти методы сходятся за небольшое количество итераций оптимизации. (Если доступен качественный предварительный кондиционер, внутренние шаги также должны быстро сходиться.)