Vollständige Verfahren zur globalen Optimierung geometrischer Optimierungsprobleme

Dieses Projekt zielt darauf ab, neue Methoden zur Lösung von globalen Optimierungsproblemen zu entwickeln, die starke Bezüge zur Geometrie aufweisen. Wir werden uns auf solche Problemklassen konzentrieren, zu deren Lösung vollständige Suchverfahren notwendig sind (d.h., es müssen alle globalen Optima gefunden werden, zusammen mit einem Beweis ihrer globalen Optimalität). Wir werden darüber hinaus auch Problemklassen betrachten, bei denen diese Suchverfahren sogar vollständig rigoros sein müssen (d.h., die Resultate müssen trotz etwaiger Rundungsfehler mathematisch korrekt sein); dies ist insbesondere dann unabdingbar, wenn dadurch computerunterstützte Beweise für mathematische Probleme gefunden werden sollen. Zunächst werden wir eine Toolbox für geometrische Optimierung im Rahmen des Open-Source-Projekts "COCONUT Environment", einem Framework für globale Optimierungsalgorithmen, implementieren. Diese Toolbox wird einerseits Darstellungen grundlegender geometrischer Formen und andererseits verschiedenste Algorithmen enthalten, wobei auf mathematische Rigorosität besonderer Wert gelegt werden wird. Diese geometrische Toolbox werden wir dazu verwenden, verschiedenste globale Optimierungsprobleme aus der diskreten Geometrie zu bearbeiten. Im Besonderen planen wir, zuvor ungelöste Instanzen für die dichteste Kreispackung in einem Quadrat zu lösen, sowie Packungsprobleme für ungleiche Kreise in verschiedene Container und allgemeine irreguläre Formen mit den neu entwickelten Methoden zu lösen. (Nach unserem Wissensstand existieren noch keinerlei vollständige Lösungsalgorithmen, um die beiden letztgenannten Problemklassen zu bearbeiten, obwohl solche Probleme von signifikanter theoretischer und praktischer Bedeutung sind.) Darüber hinaus werden wir verschieden Kugelpackungsprobleme untersuchen. Speziell ist geplant, W.-Y. Hsiangs Versuch aus dem Jahr 1993, die Keplersche Vermutung zu beweisen, zu klären. Diese Arbeit ist bereits vor T.C. Hales` berühmtem computerunterstütztem Beweis erschienen, gilt aber wegen einiger unverifizierter Behauptungen als unvollständig. Wir zielen darauf ab, Hsiangs Beweis zu vervollständigen, indem wir diese Behauptungen als globale Optimierungsprobleme formulieren und diese mit rigorosen Verfahren lösen. Weiters werden wir einen Versuch starten, das Tammes-Problem für 13 Sphären (auch bekannt als das starke Kissing-Number Problem) zu beweisen, und wenn wir erfolgreich sind, dies auch für mehrere weitere Werte zu wiederholen. Außerdem wollen wir Probleme lösen, die in Beziehung zu Konfigurationen minimaler Energie von Molekülen stehen, wie die Fekete Probleme und die globale Optimierung von molekularen Lennard-Jones- Clustern. Sogar das Lösen einiger kleinerer Instanzen dieser Probleme zur globalen Optimalität wäre ein wesentlicher Beitrag zur aktuellen Forschung in diesen Gebieten und würde der Forschung einen kräftigen Schub hin zur Lösung komplizierterer Energieoptimierungsproblem geben. Schließlich werden wir auch praktisch relevante globale Optimierungsprobleme aus der Technik studieren, die in Beziehung mit geometrischen Strukturen stehen; unter anderem Verhärtungsprobleme sowie die Verifikation von CAD-entworfenen Systemen.

Das Ziel des Projekts war die Entwicklung neuartiger Verfahren zur Lösung globaler geometrierelevanter Optimierungsprobleme. Wir haben dabei Probleme in Angriff genommen, bei denen eine sogenannte globale Suche notwendig ist, um alle globalen Optima des Problems zu finden und dabei zu beweisen, dass sie in der Tat globale Lösungen sind, oder um mathematische Aussagen, die in Zusammenhang mit solchen Optimierungsproblemen stehen, computergestützt zu beweisen.Das Projekt hat viele neue Resultate für verschiedene Probleme geliefert, sowohl aus der diskreten Geometrie, als auch aus Realanwendungen. Aus der ersten Problemgruppe war das bedeutendste Resultat die Lösung der zuvor offenen Frage der Identifikation der dichtesten Kreispackungen von 31, 32 und 33 kongruenten Kreisen in einem Quadrat. Dabei haben wir einen Satz neuer, ausgeklügelter Werkzeuge entwickelt, die wir in einen computerunterstützten Beweis integriert haben. Wir sind davon überzeugt, dass die entwickelte Toolbox geeignet sein wird, auch höhere Instanzen des Kreispackungsproblemes zu lösen und dass sie sich soweit verallgemeinern lassen wird, dass auch andere, wie etwa Packungsprobleme auf der Kugel, damit gelöst werden können.Ein weiteres wichtiges Resultat der diskreten Geometrie war ein computergestützter Beweis zur Identifikation der dichtesten Packung von drei Quadraten in einem zirkulären Behälter, ebenfalls ein offenes Problem vor unserer Lösung. Obwohl diese Problemklasse ähnlich den Kreispackungen erscheint, entstehen dabei wesentlich kompliziertere Optimierungsprobleme, deren globale Lösung ausgesprochen schwierig ist. Wir haben das Problem in der GloptLab Optimierungsumgebung gelöst, nachdem wir ein Zulässigkeitsproblem dafür hergeleitet hatten.Ein weiteres signifikantes Ergebnis des Projekts war die Entwicklung neuer Methoden, um positive Invariantenmengen numerischer Integrationsschemata für Langzeitintegration unter Verwendung großer Schrittweiten zu finden. Die Wichtigkeit dieser Mengen und der damit verbundenen Schrittweiten liegt in der verbesserten Lösung gewöhnlicher Differentialgleichungen für langdauernde chemische oder ähnlich ablaufende Prozesse begründet. Unsere Methode basiert auf der computergestützten Verifikation von Mengeninklusionsrelationen unter Verwendung globaler Suche.Wir haben auch die Überdeckung eines Quadrats mit kongruenten Kreisen minimalen Radius, mit Unsicherheit in der genauen Lokalisation der Kreise untersucht. Dieses Problem hat wichtige praktische Anwendungen, wie die ferngesteuerte Ausbringung von Sensornetzwerken an gefährlichen Orten oder unter Wettereinfluss. Wir haben dabei verschiedene geometrische Formen der Unsicherheitsregionen betrachtet. Wir haben dazu Bilevel-Optimierungsmethoden entwickelt, die vollständige globale Suche und ableitungsfreie Blackbox-Verfahren kombinieren. Während des Projekts wurden zahlreiche Werkzeuge implementiert, die die Lösung geometrischer Optimierungsprobleme mit globaler Suche voranbringen, inklusive neuer Algorithmen und Datenstrukturen in den Software-Umgebungen COCONUT und GloptLab, sowie ein eigenständiges Softwarepaket für Kreispackungen.