Algorithm Engineering für Generische Löser für Konvexe Optimierungsprobleme

• Antragsteller: Professor Dr.-Ing. Sören Laue
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 253965656

Viele Probleme aus den verschiedenen Wissenschaften und der Wirtschaft lassen sich als konvexe Optimierungsprobleme darstellen. Eine nicht erschöpfende Aufzählung beinhaltet Portfolio-Optimierung, Schaltkreisdesign, Probleme aus der Regelungstheorie, Packing und Covering Lineare Programme, Netzwerkflussprobleme, Optimierungsprobleme für hochauflösende Mikroskopie und Probleme aus dem maschinellen Lernen und der Datenanalyse. Allerdings benötiget man zum effizienten Lösen jedes dieser Probleme bis zum heutigen Tage individuelle und hochgradig durchoptimierte Lösungsprogramme.Ziel dieses Projektes ist ein Lösungsprogrammgenerator, der automatisch C++-Code für jede Klasse von konvexen Optimierungsproblemen generiert, die oben erwähnt worden.Der Lösungsprogrammgenerator wird die Benutzerfreundlichkeit einer Prototypensprache wie Matlab/CVX für das Modellieren und Lösen von Optimierungsproblemen zur Verfügung stellen und serienreifen Code generieren, der auch große Probleminstanzen effizient lösen kann. Speziell wollen wir dieselbe Funktionalität wie das populäre Modellierungstool CVX erreichen aber in einer einfacheren und flexibleren Art und Weise und zur selben Zeit so effizient sein wie individuelle Lösungsprogramme, d.h. einige Größenordnungen schneller als CVX kombiniert mit bisherigen state-of-the-art kommerziellen Lösungsprogrammen.Das Projekt umfasst das Entwerfen der Modellierungssprache, die Konzeption und Implementierung eines symbolischen Differenzierungsmoduls für Vektor- und Matrixausdrücke und die Entwicklung und die Implementierung eines generischen Lösungsalgorithmus, der die Ausdrücke für die symbolischen Ableitungen benutzt.Die generierten Lösungsprogramme werden auch in der Lage sein, die wichtige Klasse von Semidefiniten Programmen (SDPs) zu lösen. Zu diesem Zweck werden wir einen neuen Algorithmus zum Lösen von SDPs entwickeln, der einige Größenordnungen schneller sein wird als aktuelle SDP Löser. Daher können viel größere Probleminstanzen gelöst werden. Wir werden für alle Algorithmen mathematische Konvergenzgarantien und Laufzeitanalysen beweisen.

• DFG-Verfahren: Sachbeihilfen