Zur Stützeigenschaft in der multikriteriellen Optimierung

• Antragstellerinnen / Antragsteller: Professorin Dr. Gabriele Eichfelder; Professor Dr. Oliver Stein
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 528525668

Obwohl die Gewichtete-Summe-Skalarisierung eine beliebte Methode ist, um Lösungen multikriterieller Optimierungsprobleme zu bestimmen, ist bekannt, dass auf diese Weise im Allgemeinen nicht alle, sondern nur die gestützten Lösungen gefunden werden können. Eine Standardannahme, unter der alle Lösungen gestützt sind, ist die Konvexität des multikriteriellen Problems. Das erste Hauptziel dieses Projekts ist die Identifizierung einer erheblich größeren Klasse multikriterieller Probleme, für die alle Lösungen gestützt sind und daher per Gewichtete-Summe-Skalarisierung berechnet werden können. Solche multikriteriellen Probleme nennen wir gestützt. Da die wesentliche Konsequenz der Konvexität eines multikriteriellen Problems die Konvexität seiner sogenannten oberen Bildmenge ist, besitzen auch versteckt-konvexe Probleme die gewünschte Eigenschaft, womit wir nichtkonvexe Probleme mit konvexer oberer Bildmenge meinen. Darüber hinaus kann ein multikriterielles Problem selbst bei nichtkonvexer oberer Bildmenge gestützt sein. Wir zielen auf ein besseres Verständnis der Klasse der gestützten multikriteriellen Probleme ab, die im obigen Sinne eine zwischen den konvexen und den nichtkonvexen Problemen angesiedelte Kategorie bildet. In diesem Zusammenhang untersuchen wir auch Relaxierungstechniken für multikriterielle Probleme, wie kopositive oder semidefinite Reformulierungen. Wir zielen dabei auf ein besseres Verständnis dafür ab, welche Relaxierungstechniken in der multikriteriellen Optimierung die Eigenschaft besitzen, dass sie nur in gestützten Lösungen exakt sind und alternativ durch einkriterielle Relaxierungstechniken für Gewichtete-Summe-Skalarisierungen erhalten werden können. Das zweite Hauptziel des Projekts basiert auf der Beobachtung, dass die Stützeigenschaft von Lösungen multikriterieller Probleme keine intrinsische Eigenschaft ist, sondern dass sie durch passende Bildraumtransformationen für manche oder sogar alle Lösungen hergestellt werden kann. Nach einer gründlichen Untersuchung dieser Technik befassen wir uns mit algorithmisch umsetzbaren Konstruktionen, die nicht-gestützte in gestützte Probleme verwandeln. Probleme, für die dies möglich ist, nennen wir versteckt-gestützt. Die Transformationstechnik erlaubt die Verallgemeinerung von Algorithmen zur Berechnung gestützter Lösungen, wie das Benson-Verfahren oder einige Verfahren der gemischt-ganzzahligen linearen multikriteriellen Optimierung, für die Berechnung nicht-gestützter Lösungen. Insbesondere liefert dies nichtlineare Schnitte, die im Rahmen von Branch-and-Bound-Verfahren engere Schranken erlauben. Hauptziele dieses Projekts sind also die Untersuchungen theoretischer und algorithmischer Aspekte der Stützeigenschaft, von der Erkennung versteckt-konvexer und versteckt-gestützter Probleme bis zur Untersuchung der Exaktheit von Relaxierungen und der Verallgemeinerung von Algorithmen für die Berechnung nicht-gestützter Lösungen.

• DFG-Verfahren: Sachbeihilfen