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

9

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

MLE
источник
Является ли целевая функция гладкой? Это одномерный? Стоит ли оценивать 2-е производное (или гессиан)? Если возможно, я бы хотел увидеть формулу или, по крайней мере, лучше понять, почему она «сложная».
hardmath

Ответы:

10

Выпуклая функция должна удовлетворять е(αИкс+(1-α)Y)αе(Икс)+(1-α)е(Y) для всех α(0,1) а также Икс,Yв области определения. Вы можете просто попытаться проверить эту формулу для большого количества парИкс,Y и пара ценностей αнапример, αзнак равно{1/4,1/2,3/4},

Вольфганг Бангерт
источник
6

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

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

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

Арнольд Ноймайер
источник
Это эволюция DrAmpl, Арнольд?
Майкл Грант
1
@MichaelGrant: Да, это официальная публикация материала доктора AMPL.
Арнольд Ноймайер
2

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

Джед браун
источник
2
Просто чтобы уточнить, что Джед имеет в виду, когда говорит «отрицательно», это то, что матрица вторых производных функции имеет отрицательные собственные значения.
Вольфганг Бангерт