Глобальная оптимизация, когда задействована экспоненциальная функция

Question

Интересно, существуют ли методы определения глобального оптимума задач MINLP, когда задействованные нелинейные функции имеют только форму $Z = Y e^{- \alpha X}$, где $Y \ge 0$ и $X \ge 0$.

Есть ли статьи, описывающие такой подход? Обладают ли эти функции какими-либо характеристиками, которые могут быть использованы?

Используя логарифмы, я могу переписать функции как $\log(Z) = \log(Y) - \alpha X$, но я не думаю, что что-то выигрываю.

Answer 1

Это невыпуклая задача глобальной оптимизации. Самый современный способ решить эту проблему - использовать факультативную релаксацию.

Ключевым моментом здесь является то, что $e^{-\alpha X}$ выпуклый (так как ваш $\alpha$ положительный).

Методология будет следующей:

• Ввести новую вспомогательную переменную $w=e^{-\alpha X}$
• Теперь у вас есть $Z=Yw$, и $w=e^{-\alpha X}$
• Поскольку оба ограничения невыпуклые, каждое из них разбивается на два неравенства:

$Z\leq Yw, -Z\leq -Yw$

$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$

Первый набор неравенств может быть выпуклым с помощью релаксации Маккормика .

Второй набор неравенств бывает выпуклым и вогнутым соответственно. Выпуклое неравенство может быть ослаблено с помощью внешнего приближения, а вогнутое неравенство - с помощью секущей.

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

Обратите внимание, что эта методика не зависит от признаков $Z,Y,X$.

Кроме того, вы можете подключить это к глобальному решателю, который сделает все это за вас автоматически. Couenne - это выбор с открытым исходным кодом, и если вы академик / студент, вы также можете бесплатно использовать SCIP или наш собственный Octeract Engine .

Answer 2

Предполагая, что непрерывная релаксация является выпуклой, вы, скорее всего, можете использовать коническую оптимизацию с экспоненциальным конусом. Моделирование поваренной Mosek имеет детали.

Неудивительно, что Mosek может решать смешанную целочисленную версию таких задач.

Answer 3

Вы можете найти частичный ответ на свой вопрос в следующей статье (готовится в операционном зале) JP Vielma и J Huchette. https://arxiv.org/abs/1708.00050

В этой статье авторы рассматривают проблему приближения нелинейных функций одной или двух переменных в цели через дизъюнкцию нескольких гиперплоскостей. Затем вы можете передать полученный MIP в универсальный решатель для смешанных целых чисел.

Эта статья содержит ссылки на другие источники, которые также могут оказаться полезными.