McCormick-based efficient global optimization in the space of degrees of freedom

Najman, Jaromil; Mitsos, Alexander (Thesis advisor); Naumann, Uwe (Thesis advisor)

Aachen : RWTH Aachen University (2020, 2021)
Buch, Doktorarbeit

In: Aachener Verfahrenstechnik series. Process systems engineering 7 (2020)
Seite(n)/Artikel-Nr.: 1 Online-Ressource (XIV, 174 Seiten) : Illustrationen, Diagramme

Kurzfassung

Die Popularität von deterministischer globaler Optimierung im Feld der mathematischen Optimierung steigt stetig. Die Entwicklung von innovativen Algorithmen zusammen mit der erhöhten Rechenleistung ermöglichen die Lösung von immer komplexeren Optimierungsproblemen. Da die Berechnung von konvexen Relaxierungen einen wichtigen Baustein der deterministischen globalen Optimierung darstellt, steigt die Bedeutung von generellen Methoden für die Konstruktion von validen konvexen und konkaven Relaxierungen. Die Propagationsregeln von McCormick stellen eine solche generelle Methode dar, die insbesondere auch den Vorteil bietet, dass sie in dem Raum der ursprünglichen Optimierungsvariablen agiert. In dieser Arbeit analysieren wir die Konvergenzeigenschaften von und entwickeln spezialisierte Algorithmen und Heuristiken für McCormick Relaxierungen. Außerdem bestimmen wir enge Relaxierungen bzw. Einhüllende von Funktionen, die man häufig in energietechnischen und verfahrenstechnischen Optimierungsproblemen auffindet und bieten einen Weg zur Berechnung von konvexen Relaxierungen von komponentenweise konvexen Funktionen. Zunächst analysieren wir die Konvergenzordnungen in der Hausdorff und der punktweisen Metrik für multivariate McCormick Relaxierungen. Zusätzlich entwickeln wir spezialisierte Resultate für die Konvergenzordnungen an bestimmten Punkten der Definitionsmenge. Die Konvergenzordnungen der durch die multivariaten Regeln konstruierten Relaxierungen sind mindestens so gut wie die Relaxierungen, die mit Hilfe der ursprünglichen McCormick Regeln gebaut werden. Darüber hinaus untersuchen wir die Eigenschaft der Verankerung von Relaxierungen, welche besagt, dass eine Relaxierung an bestimmten Punkten des Definitionsbereiches exakt sind. Die theoretischen Resultate untermauern wir mit illustrativen Beispielen. Als Nächstes werden Einhüllende bzw. enge Relaxierungen von der mittleren logarithmischen Temperaturdifferenz, Funktionen auftretend in Mischungsmodellen und Modellen für Anlagenkosten vorgestellt. Die Relaxierungen und Einhüllende werden analytisch bestimmt. Alle resultierenden Relaxierungen liefern signifikante Zeiteinsparungen in Rahmen eines räumlichen Branch-and-Bound Algorithmus. Zusätzlich präsentieren wir einen Weg zur Konstruktion von konvexen Relaxierungen von komponentenweise konvexen Funktionen, wenn die partiellen Ableitungen bestimmte Monotonitätseigenschaften erfüllen. Zuletzt entwickeln wir Algorithmen spezialisiert für McCormick Relaxierungen. Die erste Methode nutzt die Subgradientinformationen, die während der McCormick Propagation zur Verfügung stehen um zunächst jeden Zwischenfaktor und anschließend die finalen Relaxierungen zu verbessern. Das Ziel der darauffolgenden Algorithmen ist es eine Menge von möglichst guten Linearisierungspunkten zu bestimmen, die dann zur Berechnung des unteren Beschränkungproblems genutzt werden. Der letzte vorgestellte Algorithmus kombiniert die McCormick Methode mit der state-of-the-art Hilfsvariablen Methode. Die präsentierte Methode fügt nur eine begrenzte Anzahl an Hilfsvariablen zum unteren Beschränkungsproblem hinzu. Alle Heuristiken liefern deutliche Einsparungen in der Rechenzeit eines räumlichen Branch-and-Bound Algorithmus für die betrachteten Probleme.

Identifikationsnummern

Downloads