MultiApprox – Allgemeine Approximationsverfahren für multikriterielle Optimierungsprobleme
Das Projekt MultiApprox wird durch die DFG vom 01. Juni 2018 bis 31. August 2021 gefördert.
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 Projekt sollen daher Approximationsverfahren für multikriterielle Optimierungsprobleme entwickelt werden, die
- unter schwachen Voraussetzungen anwendbar sind,
- eine beweisbar gute Approximation liefern und
- eine beweisbare Worst-Case-Laufzeit haben.
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 des Projekts trägt diesen beiden Erkenntnissen Rechnung und unterscheidet zwischen Minimierungs- und Maximierungsproblemen mit zwei bzw. mehr als zwei Zielfunktionen.
Nach Abschluss des Projekts 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.
Partner
- Hochschule Weihenstephan-Triesdorf – Professur für komplexe Netzwerke – Prof. Dr. Clemens Thielen
- Technische Universität Kaiserslautern – Arbeitsgruppe Optimierung – Prof. Dr. Stefan Ruzika
Förderung
