Optimierungssolver auf basis kopositiver Optimierung

Bei unserem Projekt geht es um das Lösen von Optimierungsproblemen, also Probleme sich für einen bestimmten Input zu entscheiden um dadurch einen bestimmten Output zu optimieren. Zum Beispiel sucht man einen Weg von A nach B um Dinge wie die Reisezeit und -Kosten zu minimieren (Output). Dazu muss man eine Entscheidung über Variablen wie Route, Zeitpunkt der Reise und Fortbewegungsmittel treffen (Input). Ein anderes Beispiel bietet die Optimierung von Netzwerken aus Kraftwerken. Die Frage ist welches Kraftwerk zu welchen Zeitpunkt wie viel Strom erzeugen soll (Input), um die Kosten so klein wie möglich zu halten und trotzdem physikalische Grenzen des Stromnetzes einzuhalten und die Nachfrage der Konsumenten zu befriedigen, was die zulässigen Inputs deutlich einschränkt. In der Mathematik unterscheiden wir zwischen konvexen und nicht-konvexen Problemen. Erstere gleichen der Suche nach dem tiefsten Punkt in einem Tal, oder einer Badewanne: solange man sich nach unten bewegt wird man irgendwann die tiefste Stelle finden. Nicht-konvexe Probleme gleichen der Suche nach dem tiefsten Punkt in der Sahara: Wenn man einfach nur nach unten geht, landet man zwar in einer Senke die tiefer liegt als der Startpunkt, wie sprechen von einem lokalen Optimum, aber aller Wahrscheinlichkeit nach handelt es sich dabei nicht um die Tiefste, das globale Optimum. Tatsächlich müsste man alle Senken der Sahara untersuchen, also reicht bloßes nach Unten gehen hier nicht aus. Nicht-konvexe Probleme sind daher viel schwerer zu lösen als konvexe. Zum Glück gibt es eine Theorie namens kopositive Optimierungstheorie, die es uns erlaubt nicht- konvexe Probleme in konvexe zu verwandeln. Das hat allerdings seinen Preis. Reformulierungen dieser Art haben meist viel mehr Variablen als die ursprünglichen Probleme, nebst andere Komplikationen technischer Natur. Kopositive Reformulierung sind daher berüchtigt schwere Probleme, trotzdem es sich bei ihnen um konvexe Probleme handelt. Aus diesem Grund hatte die kopositive Optimierung bisher wenig praktische Relevanz, trotz ihrer mathematischen Eleganz. In unserem Projekt geht es uns darum diese Lücke zu schließen. Wir haben gute Gründe anzunehmen, dass die angesprochen technischen Schwierigkeiten überwindbar sind, sofern man es schafft gewisse günstige Eigenschaften der kopositiven Reformulierung geschickt auszunutzen. Wir wollen darüber hinaus auch zeigen, das der Anwendungsbereich der kopositiven Optimierung deutlich größer ist als bisher bekannt. Vorläufige Resultate lassen uns hoffen, dass es uns gelingt kopositive Optimierung als ein unabhängiges, alternatives Paradigma in der globalen, nicht- konvexen Optimierung zu etablieren.