Allgemeine Approximationsverfahren für multikriterielle Optimierungsprobleme

• Antragsteller: Professor Dr. Stefan Ruzika; Professor Dr. Clemens Thielen
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 398572517

Bei vielen Optimierungsproblemen sollen mehrere, sich widersprechende Zielfunktionen gleichzeitig optimiert werden. Solchen multikriteriellen Optimierungsproblemen liegen Optimalitätskonzepte zugrunde, die auf Ordnungsrelationen basieren. Das verbreitetste Konzept ist die Pareto-Optimalität, die Optimallösungen als Minima (bzw. Maxima) bzgl. der komponentenweisen Ordnung in reellen Räumen charakterisiert. Für viele Optimierungsprobleme sind jedoch die Menge der Pareto-Lösungen und die zugehörige Bildmenge sehr groß und sehr schwer exakt zu berechnen. In diesem Vorhaben sollen daher Approximationsverfahren für multikriterielle Optimierungsprobleme entwickelt werden, die (1) unter schwachen Voraussetzungen anwendbar sind, (2) eine beweisbar gute Approximation liefern und (3) eine beweisbare Worst-Case-Laufzeit haben. Die beiden Antragsteller bringen dazu ihre komplementären Forschungsschwerpunkte (Multikriterielle Optimierung bzw. Approximationsalgorithmen) zusammen und bauen auf gemeinsamen Vorarbeiten auf. Es ist bekannt, dass etliche der verwendeten Methoden für die Approximation multikriterieller Minimierungsprobleme sich nicht auf die Approximation von Maximierungsproblemen übertragen lassen; Minimierungs- und Maximierungsprobleme brauchen mitunter prinzipiell andere Techniken. Zusätzlich impliziert das Konzept der Pareto-Optimalität einen weiteren wesentlichen Unterschied bezüglich der Schwierigkeit zwischen bikriteriellen und allgemeinen multikriteriellen Problemen. Die Struktur dieses Vorhabens trägt diesen beiden Erkenntnissen Rechnung und unterscheidet zwischen Minimierungs- und Maximierungsproblemen mit zwei bzw. mehr als zwei Zielfunktionen. Am Ende dieses Vorhabens werden neben allgemeinen Approximationsverfahren für diese Optimierungsprobleme auch Zusammenhänge zwischen einkriteriellen Optimierungsproblemen (z. B. aus der robusten, der parametrischen oder etwa der Budget-restringierten Optimierung) und daraus abgeleiteten multikriteriellen Optimierungsproblemen erforscht sein. Somit versprechen wir uns, einerseits eine "beweisbar gute" Alternative zu den gängigen exakten oder heuristischen Verfahren für multikriterielle Optimierungsprobleme zu erarbeiten und andererseits zum grundlegenden Wissensstand in der Theorie der mathematischen Optimierung signifikant beizutragen.

• DFG-Verfahren: Sachbeihilfen