Ottimizzazione globale quando è coinvolta la funzione esponenziale

Aug 19 2020

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

4 NikosKazazakis Aug 20 2020 at 19:43

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.

4 ErlingMOSEK Aug 20 2020 at 12:28

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.

2 ClaudioContardo Aug 21 2020 at 03:32

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.