AG Optimierung

General Approximation Methods for Multicriteria Optimization Problems

Das Projekt (in Deutsch „Allgemeine Approximationsverfahren für multikriterielle Optimierungsprobleme“) wird vom 01. Juni 2018 bis 31. Mai 2021 von der Deutschen Forschungsgesellschaft (DFG) 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

  1. unter schwachen Voraussetzungen anwendbar sind,
  2. eine beweisbar gute Approximation liefern und
  3. 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.

Förderung

Zum Seitenanfang