Optimización global cuando está involucrada la función exponencial
Me pregunto si hay métodos para determinar el óptimo global de los problemas de MINLP, cuando las funciones no lineales involucradas son solo de la forma $Z = Y e^{- \alpha X}$, dónde $Y \ge 0$ y $X \ge 0$.
¿Hay artículos que describan este enfoque? ¿Tienen estas funciones alguna característica que pueda ser explotada?
Usando logaritmos puedo reescribir las funciones como $\log(Z) = \log(Y) - \alpha X$, pero no creo que esté ganando nada.
Respuestas
Este es un problema de optimización global no convexo. La forma más moderna de resolver esto es utilizar una relajación factorizable.
Una idea clave aquí es que $e^{-\alpha X}$ es convexo (ya que tu $\alpha$ es positivo).
La metodología sería la siguiente:
- Introducir una nueva variable auxiliar $w=e^{-\alpha X}$
- Ahora tienes $Z=Yw$y $w=e^{-\alpha X}$
- Debido a que ambas restricciones no son convexas, divide cada una en dos desigualdades:
$Z\leq Yw, -Z\leq -Yw$
$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$
El primer conjunto de desigualdades se puede convexificar mediante una relajación de McCormick .
El segundo conjunto de desigualdades son convexas y cóncavas respectivamente. La desigualdad convexa se puede relajar usando una aproximación externa y la desigualdad cóncava usando una secante.
Luego, conecte su problema relajado en un algoritmo de bifurcación y límite y convergerá cuadráticamente.
Tenga en cuenta que esta metodología es independiente de los signos de $Z,Y,X$.
Alternativamente, puede conectar esto a un solucionador global que hará todo esto automáticamente. Couenne es una opción de código abierto, y si eres un académico / estudiante, también puedes usar SCIP o nuestro propio motor Octeract Engine de forma gratuita.
Suponiendo que la relajación continua es convexa, lo más probable es que pueda utilizar la optimización cónica con el cono exponencial. El libro de cocina de modelado de Mosek tiene los detalles.
Como era de esperar, Mosek puede resolver la versión entera mixta de tales problemas.
Puede encontrar una respuesta parcial a su pregunta en el siguiente artículo (de próxima publicación en OR) de JP Vielma y J Huchette https://arxiv.org/abs/1708.00050
En ese artículo, los autores consideran el problema de aproximar funciones no lineales de una o dos variables en el objetivo mediante la disyunción de múltiples hiperplanos. A continuación, puede pasar el MIP resultante a un solucionador de enteros mixtos de propósito general.
Ese artículo contiene citas de otras fuentes que también pueden ser de ayuda.