Optimisation globale lorsque la fonction exponentielle est impliquée

Question

Je me demande s'il existe des méthodes pour déterminer l'optimum global des problèmes MINLP, lorsque les fonctions non linéaires impliquées ne sont que de la forme $Z = Y e^{- \alpha X}$, où $Y \ge 0$ et $X \ge 0$.

Existe-t-il des articles décrivant une telle approche? Ces fonctions présentent-elles des caractéristiques susceptibles d'être exploitées?

En utilisant des logarithmes, je peux réécrire les fonctions comme $\log(Z) = \log(Y) - \alpha X$, mais je ne pense pas gagner quoi que ce soit.

Answer 1

Il s'agit d'un problème d'optimisation globale non convexe. La manière la plus moderne de résoudre ce problème consiste à utiliser une relaxation factorielle.

Un aperçu clé ici est que $e^{-\alpha X}$ est convexe (puisque votre $\alpha$ est positif).

La méthodologie serait la suivante:

• Introduire une nouvelle variable auxiliaire $w=e^{-\alpha X}$
• Vous avez maintenant $Z=Yw$, et $w=e^{-\alpha X}$
• Étant donné que les deux contraintes ne sont pas convexes, vous divisez chacune en deux inégalités:

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

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

Le premier ensemble d'inégalités peut être convexifié en utilisant une relaxation de McCormick .

Le deuxième ensemble d'inégalités est respectivement convexe et concave. L'inégalité convexe peut être assouplie en utilisant une approximation externe et l'inégalité concave en utilisant une sécante.

Vous branchez ensuite votre problème détendu dans un algorithme de branchement et lié et il convergera quadratiquement.

Notez que cette méthodologie est indépendante des signes de $Z,Y,X$.

Vous pouvez également le brancher sur un solveur global qui fera tout cela pour vous automatiquement. Couenne est un choix open-source, et si vous êtes un universitaire / étudiant, vous pouvez également utiliser SCIP ou notre propre moteur Octeract gratuitement.

Answer 2

En supposant que la relaxation continue est convexe, vous pouvez très probablement utiliser l'optimisation conique avec le cône exponentiel. Le livre de recettes de modélisation Mosek a les détails.

Sans surprise, Mosek peut résoudre la version mixte de ces problèmes.

Answer 3

Vous pouvez trouver une réponse partielle à votre question dans l'article suivant (à paraître en OR) par JP Vielma et J Huchette https://arxiv.org/abs/1708.00050

Dans cet article, les auteurs considèrent le problème de l'approximation des fonctions non linéaires d'une ou deux variables dans l'objectif via la disjonction de plusieurs hyperplans. Vous pouvez ensuite transmettre le MIP résultant à un solveur d'entiers mixtes à usage général.

Cet article contient des citations à d'autres sources qui peuvent également être utiles.