Ottimizzazione globale quando è coinvolta la funzione esponenziale
Mi chiedo se esistono metodi per determinare l'ottimo globale dei problemi MINLP, quando le funzioni non lineari coinvolte sono solo della forma $Z = Y e^{- \alpha X}$, dove $Y \ge 0$ e $X \ge 0$.
Esistono documenti che descrivono un simile approccio? Queste funzioni hanno caratteristiche che possono essere sfruttate?
Usando i logaritmi posso riscrivere le funzioni come $\log(Z) = \log(Y) - \alpha X$, ma non credo di vincere nulla.
Risposte
Questo è un problema di ottimizzazione globale non convesso. Il modo più avanzato per risolvere questo problema è utilizzare un rilassamento fattorizzabile.
Una visione chiave qui è quella $e^{-\alpha X}$ è convesso (poiché il tuo $\alpha$ è positivo).
La metodologia sarebbe la seguente:
- Introduci una nuova variabile ausiliaria $w=e^{-\alpha X}$
- Adesso hai $Z=Yw$, e $w=e^{-\alpha X}$
- Poiché entrambi i vincoli sono non convessi, dividi ciascuno in due disuguaglianze:
$Z\leq Yw, -Z\leq -Yw$
$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$
Il primo insieme di disuguaglianze può essere convesso utilizzando un rilassamento di McCormick .
Il secondo insieme di disuguaglianze sono rispettivamente convesse e concave. La disuguaglianza convessa può essere attenuata usando un'approssimazione esterna e la disuguaglianza concava usando una secante.
Quindi inserisci il tuo problema rilassato in un algoritmo branch-and-bound e converge quadraticamente.
Si noti che questa metodologia è indipendente dai segni di $Z,Y,X$.
In alternativa, puoi collegarlo a un risolutore globale che farà tutto questo automaticamente. Couenne è una scelta open source e se sei un accademico / studente puoi anche utilizzare SCIP o il nostro Octeract Engine gratuitamente.
Supponendo che il rilassamento continuo sia convesso, molto probabilmente puoi usare l'ottimizzazione conica con il cono esponenziale. Il ricettario di modellismo Mosek ha i dettagli.
Non sorprende che Mosek possa risolvere la versione mista intera di tali problemi.
Puoi trovare una risposta parziale alla tua domanda nel seguente articolo (di prossima pubblicazione in OR) di JP Vielma e J Huchette https://arxiv.org/abs/1708.00050
In quel documento, gli autori considerano il problema dell'approssimazione di funzioni non lineari di una o due variabili nell'obiettivo tramite la disgiunzione di più iperpiani. È quindi possibile passare il MIP risultante a un risolutore di numeri interi misti generico.
Questo articolo contiene citazioni ad altre fonti che potrebbero essere di aiuto.