Dekompositionsverfahren für globale Optimierung

Das Ziel dieses Projektes ist die Schaffung eines Verfahrens zur globalen Optimierung, (i) das alle globalen Optima eines nichtlinearen Optimierungsproblems oder alle Lösungen eines Systems nichtlinearer Gleichungen findet, (ii) sodass die Lösungen garantiert korrekt sind, sogar wenn Rundungsfehler auftreten, (iii) das Unzulässigkeit des Problems beweisen kann, (iv) für das vorausgesetzt, dass die Jacobimatrix dünnbesetzt ist und dass das Problem geeignet in kleinere Teilprobleme zerlegt werden kann der Rechenaufwand polynomial mit der Anzahl der Subprobleme skaliert und im ungünstigsten Fall exponentiell nur mit der Größe des größten Teilproblems. Numerische Belege deuten darauf hin, dass lineare Zeitkomplexität für Destillationskolonnen, welche für dieses Projekt von zentraler Bedeutung sind, erreichbar ist. Globale Konvergenz wird garantiert, indem Branch-and-bound-Methoden und Intervallarithmetik eingesetzt werden. Intervallarithmetik schließt Rundungsfehler automatisch ein. Anders als bei konventionellen Iterationsverfahren, kann in einem Branch-and-bound-System Unzulässigkeit auf natürlichem Weg bewiesen werden. Ein Dekompositionsverfahren wird sicherstellen, dass der Rechenaufwand gut in der Problemgröße skaliert (vorausgesetzt, dass das Problem eine passende Struktur mit dünnbesetzter Jacobimatrix aufweist). Im Chemieingenieurwesen war die wahrscheinlich erste publizierte Dekompositionsmethode, um den Rechenaufwand zu reduzieren, das berühmte Stage-by-Stage-Verfahren aus den 1930ern: Das hochdimensionale Gleichgewichtsmodell wird zerlegt und eine Folge niedrigdimensionaler Teilprobleme wird stattdessen gelöst. Diese Zerlegungsidee wurde später erweitert und wurde als Partitionierung, Präzedenzordnung und Tearing bekannt. Unglücklicherweise kann das zerlegte System äußerst sensitiv auf Änderungen der Anfangsschätzungen reagieren, sodass die Berechnung einer Lösung notorisch schwierig oder gar unmöglich wird. Diese Sensibilitätsprobleme wurden niemals zufriedenstellend gelöst. Tearing ähnelt einer Baumzerlegung. Der Hauptunterschied ist, dass Tearing auf stetige Probleme adaptiert ist, wohingegen die Baumzerlegung für diskrete Optimierungs und Zulässigkeitsprobleme entwickelt wurde. Baumzerlegung ist sehr populär in anderen Wissenschaftsgebieten, da der diskrete Fall inherent frei von den Sensibilitätsproblemen ist, die für Tearing charakteristisch sind. Das jüngste Resultat unserer Gruppe hat uns in diesem Zusammenhang an den Rand eines Durchbruchs geführt. Wir haben entdeckt, dass die Sensibilitätsprobleme des Tearing (die seit den 1930ern ungelöst waren, obwohl enorme Forschungsanstrengungen unternommen worden sind) tatsächlich gelöst werden können; es ist möglich, Baumzerlegung auch auf stetige nichtlineare Probleme zu adaptieren. Der Machbarkeitsnachweis für die neue Methode im Rahmen einer Prototypimplementation findet alle Lösungen eines schwierigen Problems aus dem Chemieingenieurwesen ohne weiteres Eingreifen des Benutzers und ohne Anfangsschätzungen. Dabei wurden weder Branch-and-bound noch Intervallmethoden in die Prototypimplementation integriert. Im Rahmen dieses Projekts wollen wir den Status unserer Methoden von die ersten Resultate sind sehr vielversprechend vorantreiben zu generischen Algorithmen, die stabil und effizient laufen.

Globale Optimierung ist die Aufgabe, die absolut bestmögliche Wahl für den Wert der Veränderlichen eines Problems zu treffen, sodass vorgegebene Beziehungen zwischen den Werten dieser Veränderlichen berücksichtigt werden. Die Güte der Wahl wird dabei durch die Werte der sogenannten Zielfunktion gemessen, und die Beziehungen werden mathematisch durch Gleichungen und Ungleichungen ausgedrückt, den sogenannten Nebenbedingungen. Die Zielfunktion zusammen mit den Nebenbedingungen nennen wir ein globales Optimierungsproblem, und solche Optimierungsprobleme haben vielfältige Anwendungen in Technik und Wirtschaft. Ist die Zielfunktion konstant, also der Wert aller Wahlen gleich, dann ist die Hauptaufgabe, irgendeine Kombination von Werten der Veränderlichen zu finden, sodass alle Nebenbedingungen erfüllt sind. Die Zielfunktion ist in diesem Fall überflüssig, und wir nennen das entstehende Problem ein Zulässigkeitsproblem. Allgemeine globale Optimierungsprobleme und Zulässigkeitsprobleme sind in der Regel extrem schwierig zu lösen, besonders wenn die Dimension also die Anzahl der Veränderlichen hoch ist. Im Verlauf dieses Projekts haben wir wichtige Schritte in Richtung eines Verfahrens zur globalen Optimierung gemacht, das beweisbar alle globalen Optima eines nichtlinearen Optimierungsproblems findet, oder alle Lösungen eines nichtlinearen Zulässigkeitsproblems, selbst wenn bei der Rechnung Rundungsfehler auftreten. Das Besondere an den in diesem Projekt entwickelten Verfahren ist, dass das Problem bei geeigneter Struktur in kleine Teilprobleme zerlegt wird, die nur schwach miteinander verbunden sind, sodass der Lösungsalgorithmus durch Konzentration auf die kleinen Teilprobleme einen geringeren Gesamtrechenaufwand aufweist, als würde er das Problem in seiner Gesamtheit behandeln. In der technischen Chemie sind Zerlegungsverfahren schon seit den 1930er Jahren bekannt, allgemein unter dem Namen Tearing, doch die dort betrachteten hochdimensionalen Probleme werden numerisch sehr instabil, wenn sie in einer Baumstruktur zerlegt werden, und diese Sensitivitätsprobleme waren vor diesem Projekt im Wesentlichen ungelöst. Die Verfahren, die in diesem Projekt entwickelt wurden, erlauben es, diese numerischen Schwierigkeiten zu beseitigen und auch hochdimensionale Gleichgewichtsmodelle in manchen Anwendungen sehr effizient zu lösen. Es wurde dafür ein spezieller Algorithmus geschrieben, und die entwickelten Zerlegungsverfahren wurden in Gloptlab, eine der globalen Optimierungsplatformen der Gruppe, integriert.