Algorithmen zur Projektion von konvexen Mengen und deren Anwendung zum Lösen von nichtkonvexen Optimierungsproblemen und für ein Kalkül konvexer Mengen

• Antragsteller: Professor Dr. Andreas Löhne
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2015 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 271835661

Die zentrale mathematische Aufgabe des Projekts ist die Berechnung der Projektion einer endlich-dimensionalen konvexen Menge in einen Raum von niedrigerer Dimension. Ausgehend von einer analytischen Darstellung einer konvexen Menge im Ausgangsraum, soll die projizierte Menge auf zwei Arten beschrieben werden. Zum einen, indem die Menge polyedrisch approximiert wird. Ein anderer Ansatz ist die Beschreibung der Menge durch lineare Matrixungleichungen, bzw. falls das nicht möglich ist, durch eine Approximation mit solchen.Das Projektionsproblem soll angewendet werden, um bestimmte Klassen nichtkonvexer Optimierungsprobleme exakt zu lösen. Mögliche Problemklassen sind Zweiebenenprobleme mit konvexer unterer Ebene, DC-Probleme mit bekannter DC-Darstellung der Zielfunktion und Probleme mit quasi-konkaver Zielfunktion und konvexen Restriktionen.Dieser Zugang wurde im laufenden Projekt bereits für den polyedrischen Spezialfall bearbeitet. Es wurde gezeigt, dass das polyedrische Projektionsproblem äquivalent zu einem linearen Vektoroptimierungsproblem (VLP) ist. Somit konnten polyedrische Varianten der genannten globalen Optimierungsprobleme mit dem VLP-Solver ‘bensolve’ gelöst werden. Entsprechende Ergebnisse sollen für den nicht-polyedrischen konvexen Fall entwickelt werden. Insbesondere sollen globale skalare Optimierungsprobleme mit einem Solver für konvexe Vektoroptimierungsprobleme behandelt werden. Alternativ werden die aus der konvexen Vektoroptimierung bekannten Algorithmen so modifiziert, dass direkt konvexe Projektionsprobleme gelöst werden können. Sogenannte lokalisierte Varianten der Algorithmen lösen ein Projektionsproblem nur lokal (das heißt, nur interessante Bereiche der projizierten Menge werden berechnet) und führen zu verbesserter Effizienz der Verfahren für die globalen skalaren Optimierungsprobleme. Polyederprojektion wurde im laufenden Projekt auch verwendet, um einen numerischen Kalkül für polyedrische konvexe Mengen und polyedrische konvexe Funktionen zu entwickeln, der in einer freien Software umgesetzt worden ist. Die für den polyedrischen Fall im laufenden Projekt entwickelte Software ‘bensolve tools’, soll um entsprechende Ergebnisse zum nicht-polyedrischen konvexen Fall erweitert werden.

• DFG-Verfahren: Sachbeihilfen