Symmetrien in globaler Optimierung

Dieses Projekt zielt ab auf die Entwicklung eines theoretischen Rahmens, begleitet durch algorithmische Reali- sierung, um Symmetrien in globalen Optimierungsproblemen zu behandeln. Die neu erforschten Algorithmen werden in das frei erhältliche Softwarepaket ``COCONUT Environment`` integriert werden. Für die Behandlung stetiger Symmetrien wird eine verallgemeinerte Intervallanalysis auf Lie-Gruppen und deren Darstellungen entwi- ckelt werden. Diese wird verwendet werden, um symmetrische globale Optimierungsprobleme auf ihrem niedri-ger dimensionalen Orbitraum zu lösen. Globale Optimierung ist die Aufgabe, die absolut beste Möglichkeit(en) zu finden, ein Ziel unter gegebenen Ne- benbedingungen zu erreichen, unter der Annahme, dass alles in mathematischen Ausdrücken modelliert ist. Ein Spezialfall davon ist das Zulässigkeitsproblem, das darauf abzielt, eine oder alle Lösungen zu finden, die einem vorgegebenen Satz von Nebenbedingungen entsprechen. Beide Probleme sind viel schwieriger als konvexe Op- timierung, die Auffindung lokaler Minima nichtlinearer Optimierungsprobleme oder die Lösung eines algebrai- schen Gleichungssystems, wenn gute Startpunkte bekannt sind. Viele wissenschaftliche und industrielle Anwendungen (z.B. Form-Optimierung in der Strukturmechanik, Design und Analyse von Robotern, Analyse von Phasengleichgewichten, Proteinfaltung, Logistik) führen zu schwierigen globalen Optimierungsproblemen in Dimensionen von weniger als zehn bis zu mehreren tausend Variablen. Im letzten Jahrzehnt hat sich das Interesse an globaler Optimierung substantiell gesteigert, zum Teil, weil immer mehr Anwendungen entstanden sind, aber auch, weil die algorithmische Entwicklung den Punkt erreicht hat, ab dem viele kleinere Probleme, die aber bereits Industrie-relevante Größenordnungen erreicht haben, zuverlässig gelöst werden können. Um den Herausforderungen realer Anwendungen zu begegnen, ist es oft nötig, neue theoretische Methoden zu erforschen und sie einzusetzen, die die speziellen Eigenschaften der Anwendung be-sonders ausnützen. Wie in vielen Bereichen, die sich mit schwierigen Rechner-intensiven-Problemen beschäfti-gen, kommt der Erfolg viel häufiger über theoretische Fortschritte als durch die Erhöhung der reinen Rechenstär-ke im Hardware-Bereich oder durch geschickte Nutzung bereits vorhandener Software-Pakete. Globale Optimierungsprobleme und Zulässigkeitsprobleme tendieren dazu, besonders schwierig zu werden, wenn sie intrinsische Symmetrien enthalten; die meisten der oben genannten Probleme enthalten eine große Anzahl von Symmetrien. Der für die Schwierigkeiten beim Lösen ist, dass vollständige Lösungsalgorithmen für globale Optimierungsprobleme und Zulässigkeitsprobleme auf keinen Fall Lösungen verlieren dürfen. Treten ste-tige Symmetrien auf, führt das zu einer Teilmannigfaltigkeit (einem Orbit) äquivalenter Lösungen. Gibt es diskrete Symmetrien, dann hat das Problem eine riesige Anzahl gleichwertiger isolierter Lösungen. Die meisten Problem- klassen der globalen Optimierung sind NP-hart, und die besten vollständigen Löser vermeiden den exponenti-ellen Lösungsaufwand durch sorgfältige Wahl der Teilungsstrategien und die Verwendung mächtiger Abschät- zungsmethoden. Tritt nun eine große Anzahl äquivalenter Lösungen auf, verlieren diese Abschätzungsmethoden meist ihre Effektivität und zwingen den Algorithmus, das Problem vorwiegend durch Teilung zu lösen, was zu ex- ponentiellem Aufwand führt. Um diskrete Symmetrien (z.B. Permutationssymmetrie) in diskreten Optimierungsproblemen zu behandeln, gibt es viele Ansätze in der wissenschaftlichen Literatur. Es ist allerdings schwierig, diese Ansätze auf stetige Proble-me zu übertragen. Stetige Symmetrien (z.B. Rotationssymmetrie) sind im Vergleich noch schwieriger, da kaum Ideen in der Literatur zum Umgang mit diesen Symmetrien existieren. In diesem Projekt planen wir, eine Verallgemeinerung der Intervallanalysis auf Matrix-Lie-Algebren und Lie- Gruppen und deren Darstellungen zu entwickeln, um rigoros in Lie-Gruppen rechnen zu können, inklusive expli- ziter Fehleranalyse. Danach haben wir vor, diese Methoden anzuwenden, um symmetrische Optimierungspro-bleme auf die Orbiträume zu reduzieren, die entstehen, wenn man die Lie-Gruppenwirkung aus der zulässigen Menge faktorisiert. Außerdem werden wir Optimalitätsbedingungen für symmetrische Probleme bestimmen, um die Degeneration der Lösung, die durch die stetigen Symmetrien hervorgerufen werden, zu eliminieren. Wir wer-den angepasste Teilungsstrategien für das Branch-and-Bound Schema erforschen und, wenn notwendig, Anpas-sungen der lokalen Optimierung (wie etwa die Suchpfad-Erzeugung im Orbitraum), um die Geschwindigkeit der lokalen Optimierung zu steigern. Auswirkungen auf Constraint Propagation werden auch betrachtet werden. Die in diesem Projekt neu erarbeiteten Methoden zur verifizierten Rechnung in Lie-Gruppen werden es erlauben, die Techniken des computergestützten Beweisens auf Differentialgeometrie, Darstellungstheorie, Differentialgleichungen auf Mannigfaltigkeiten, sowie auf alle mathematischen Gebiete auszudehnen, in denen Lie- Gruppen eine prominente Rolle spielen.

Globale Optimierung ist die Aufgabe, die absolut beste Möglichkeit(en) zu finden, ein Ziel unter gegebenen Nebenbedingungen zu erreichen, unter der Annahme, dass alles in mathematischen Ausdrücken modelliert ist. Ein Spezialfall davon ist das Zulässigkeitsproblem, das darauf abzielt, eine oder alle Lösungen zu finden, die einem vorgegebenen Satz von Nebenbedingungen entsprechen. Beide Probleme sind viel schwieriger als konvexe Optimierung, die Auffindung lokaler Minima nichtlinearer Optimierungsprobleme oder die Lösung eines algebraischen Gleichungssystems, wenn gute Startpunkte bekannt sind. Viele wissenschaftliche und industrielle Anwendungen (z.B. Form-Optimierung in der Strukturmechanik, Design und Analyse von Robotern, Investitionsoptimierung zur Disastervorsorge) führen zu schwierigen globalen Optimierungsproblemen in Dimensionen von weniger als zehn bis zu mehreren tausend Variablen. Wenn solch ein Optimierungsproblem stetige Symmetrien besitzt, dann gibt es eine unendliche Zahl gleichwertiger Lösungen, und diese Degeneration macht es sehr schwierig, alle Lösungen zu identifizieren und die Existenz einer global optimalen Lösung in der Nähe einer approximativen Lösung zu beweisen.In diesem Projekt haben wir ein neues Verfahren zur Behandlung solcher Symmetrien in globalen Optimierungsproblemen entwickelt, indem wir die Intervallanalysis eine Methode für verifiziertes Rechnen im Computer auf Lie-Gruppen eine mathematische Struktur zur Beschreibung von Symmetrien verallgemeinert haben. Darüber hinaus haben wie einen Algorithmus hergeleitet und implementiert, der speziell strukturierte nichtglatte Optimierungsprobleme lösen kann, wie sie als Teilprobleme in globaler Optimierung auftreten. Dieser Algorithmus ist ein erster Schritt hin zu einem allgemeinen Löser für nichtglatte Optimierungsprobleme, eine andere Klasse von Problemen, die für industrielle Anwendungen relevant sind. Die theoretisch hergeleiteten Algorithmen haben wir in ein public-domain Softwarepakete integriert, die Vienna Matrix Template Library (VMTL), die die neue Grundlage für das COCONUT Environment bildet. Wir haben das Gebiet der globalen Optimierung auch durch die folgenden Entwicklungen vorangebracht: Es wurde von uns eine neue Klasse von Unzulässigkeitszertifikaten gefunden; das sind computergestützte Beweise dafür, dass bestimmte mathematische Probleme unlösbar sind. Außerdem haben wir eine neue Klasse quadratischer Relaxationen konstruiert das sind vereinfachte Versionen des Originalproblems, die effizient gelöst werden können und die wertvolle Information für das Originalproblem liefern. Wir haben dazu noch eine Methode zur Aggregation verschiedener Nebenbedingungen zu einer Bedingung entwickelt, die sehr wertvoll zur effizienten Reduktion des Suchbereichs beiträgt.Schließlich haben wir diskrete Symmetriebrechung und nichtlineare Optimierung verwendet, um effektiv einen bekannten Benchmark in Disaster-Vorbereitung zu schließen. Das angesprochene Problem ist das Finden einer optimalen Investitionsstrategie in das Highway-Netzwerk von Istanbul, damit im Erdbebenfall die Evakuierungsrouten so kurz wie möglich bleiben. Unsere Lösungsmethode berechnet das Optimum in Millisekunden. Auch größere Probleme, wie die optimale Investitionsstrategie für das Highway-Netzwerk der Bay-Area um San Francisco, können rasch gelöst werden, und sogar sehr große Probleme mit bis zu 900 Investitionsmöglichkeiten werden möglich.