Globale Optimierung

  Urheberrecht: © SVT  

Den Technical Report über die derzeitige Version von MAiNGO finden Sie hier.
Die open-source Beta Version von MAiNGO finden Sie hier.

McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization (MAiNGO) ist eine deterministisch globale Optimierungssoftware zur Lösung von gemischt-ganzzahligen nichtlinearen Programmen (MINLPs), welche am Lehrstuhl für Systemverfahrenstechnik (AVT.SVT) von Dominik Bongartz, Jaromil Najman, Susanne Sass und Alexander Mitsos entwickelt wurde. Der Löser wird aktiv am AVT.SVT weiterentwickelt.

Jedes (gemischt-ganzzahlige oder kontinuierliche) nichtlineare Programm mit nicht-konvexen Funktionen kann mehrere lokale Optima besitzen. Methoden zur lokalen Optimierung können zu jeder beliebigen lokalen Lösung konvergieren oder bei einer schlechten Wahl des Initialwertes sogar daran scheitern, überhaupt einen zulässigen Punkt zu finden. Heuristische Methoden wie Evolutionäre Algorithmen oder Simulated Annealing konvergieren zum globalen Optimum mit Wahrscheinlichkeit eins nur wenn die Laufzeit gegen unendlich läuft. Im Gegensatz dazu, garantieren global deterministische Methoden endliche Konvergenz zu einer globalen Lösung für durch den Nutzer spezifizierte, von null verschiedene Toleranzen für Zulässigkeit (\(\delta\)) und Optimalität (\(\epsilon\)).

MAiNGO kann MINLPs der Form

\(\begin{align*} \min_{\mathbf{x},\mathbf{y}}\,\,\, &f(\mathbf{x},\mathbf{y}) \newline \text{ s.t. } &h(\mathbf{x},\mathbf{y}) = \mathbf{0} \newline &g(\mathbf{x},\mathbf{y}) \leq \mathbf{0} \newline &\mathbf{x}\in X\in\mathbb{I}\!\mathbb{R}^{n_x} \newline &\mathbf{y}\in Y \subsetneq \mathbb{Z}^{n_y} \end{align*}\)

 

bis zur globalen Optimalität mit Zulässigkeitstoleranz δ und Optimalitätstoleranz ϵ lösen beziehungsweise beweisen, dass kein δ-zulässiger Punkt existiert, wobei Iℝ die Menge aller abgeschlossenen Intervalle in ℝ bezeichnet.

Eine der algorithmischen Besonderheiten von MAiNGO ist die Durchführung der Berechnungen in dem Raum der ursprünglichen Optimierungsvariablen (d.h. es werden keine Hilfsvariablen im Optimierungsprozess eingefügt) mit Hilfe der McCormick Relaxierungen [McCormick1976, Mitsos2009, Tsoukalas2014] berechnet durch die Bibliothek MC++. Außerdem verfügt MAiNGO über eine Heuristik zur Verbesserung von McCormick Relaxierungen [Najman2019a] und spezialisierte Relaxierungen für verschiedene Funktionen (einschließlich relevanten Funktionen in der Verfahrenstechnik) [Najman2016, Najman2019b].

Anwendungen:

Es wurde gezeigt, dass MAiNGO Vorteile bei Problemen mit einer reduced-space Formulierung aufweist [Mitsos2009, Bongartz2017a].

Optimierung von Prozessfließbildern:

Fließbildoptimierung ist eine relevante Anwendung, bei der reduced-space Formulierungen verwendet werden können, welche sich als Hybride zwischen gleichungsbasierten und sequentiell-modularen Ansätzen interpretieren lassen. Gegenüber rein gleichungsbasierten Ansätzen, wie sie bisher für globale Optimierung meist genutzt werden, kann dies zu signifikant reduzierten Laufzeiten führen [Bongartz2017a, Bongartz2017b, Huster2017, Bongartz2018].

Optimierung mit maschinellen Lernmodellen:

Die Optimierung mit maschinellen Lernmodellen ist besonders vorteilhaft, sehen Sie unser spezielles Tool Machine Learning models for Optimization (MeLOn).

Globale dynamische Optimierung:

MAiNGO wurde auch erfolgreich auf die globale dynamische Optimierung angewendet. Insbesondere für den Spezialfall der Hammerstein-Wiener-Modelle [Kappatou2022]. Der verfolgte Ansatz ist diskretisieren-dann-entspannen.