Multikriterielle Optimierung

Multikriterielle Optimierung (auch multikriterielle Programmierung, engl. multi-objective optimization, multi-criteria optimization) ist ein Teilgebiet der mathematischen Optimierung, das sich mit Problemen der simultanen Optimierung von zwei oder mehr Zielfunktionen (Kriterien) befasst, die in der Regel miteinander in Konflikt stehen. Formal wird das Problem als Minimierung einer vektoriellen Zielfunktion über einer Menge zulässiger Lösungen formuliert.

Definition und Terminologie

Ein multikriterielles Optimierungsproblem wird allgemein wie folgt formuliert: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ wobei $S\subseteq {\mathbb{ℝ}}^n$ die nichtleere Menge der zulässigen Lösungen ist und $f_i:S\to \mathbb{ℝ}$ die Zielfunktionen sind ($k\ge 2$). Der Vektor $f(x)=(f_1(x),\dots ,f_k(x))$ wird als Zielvektor bezeichnet.

Im Gegensatz zur skalaren Optimierung gibt es bei einem multikriteriellen Problem in der Regel keine einzelne Lösung, die alle Kriterien gleichzeitig verbessert. Daher wird der klassische Begriff des Optimums durch das Konzept der Pareto-Optimalität verallgemeinert.

• Pareto-optimale Lösung (auch Pareto-effiziente Lösung): Eine zulässige Lösung $x^{*}\in S$, für die keine andere Lösung $x\in S$ existiert, sodass $f_i(x)\le f_i(x^{*})$ für alle $i=1,\dots ,k$ gilt und gleichzeitig $f_j(x)<f_j(x^{*})$ für mindestens einen Index $j$. Mit anderen Worten ist eine Lösung Pareto-optimal, wenn kein Kriterium verbessert werden kann, ohne mindestens ein anderes Kriterium zu verschlechtern.
• Pareto-Front (oder Pareto-Menge): Die Menge aller Zielvektoren, die den Pareto-optimalen Lösungen entsprechen.
• Schwach Pareto-optimale Lösung: Eine Lösung $x^{*}\in S$, für die keine andere Lösung $x\in S$ existiert, sodass $f_i(x)<f_i(x^{*})$ für alle $i$ gilt.

Wichtige Eigenschaften und Theoreme

• Theorem der gewichteten Summe: Bei konvexen Problemen (bei denen alle Funktionen $f_i(x)$ und die Menge $S$ konvex sind) ist jede Pareto-optimale Lösung $x^{*}$ auch eine Lösung des skalarisierten Problems der Minimierung der gewichteten Summe der Kriterien, $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$, für einen Satz nichtnegativer Gewichte $w_i\ge 0$. Bei nicht-konvexen Problemen kann diese Methode jedoch möglicherweise nicht alle Teile der Pareto-Front finden.

• Karush-Kuhn-Tucker-Bedingungen (KKT-Bedingungen): Die notwendigen Optimalitätsbedingungen für glatte Probleme lassen sich auf den multikriteriellen Fall verallgemeinern. An einem Pareto-optimalen Punkt existiert ein nicht-trivialer Satz nichtnegativer Multiplikatoren (Gewichte), für den die Gradienten der Zielfunktionen und der aktiven Nebenbedingungen linear abhängig sind.

• Eigenschaften der Lösungsmenge: Die Pareto-Front besitzt eine Reihe wichtiger qualitativer Merkmale. Ihre Grenzen werden durch den idealen Punkt (der aus den komponentenweisen Minima aller Kriterien besteht) und den Nadir-Punkt (der aus den komponentenweisen Maxima auf der Front besteht) bestimmt.

Beispiele

• Lineares Problem: Minimiere $f_1(x)=-x_1$ und $f_2(x)=-x_2$ unter der Nebenbedingung $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Hier führt die Verbesserung eines Kriteriums (z. B. die Erhöhung von $x_1$) unweigerlich zur Verschlechterung des anderen (Verringerung von $x_2$). Die Menge der Pareto-optimalen Lösungen ist das Liniensegment $x_1+x_2=1$.
• Nicht-konvexes Problem: Minimiere $f_1(x)=x^2$ und $f_2(x)=(x-2{)}^2$ auf dem Intervall $[0,2]$. Die Pareto-Front ist nicht konvex. Die Methode der gewichteten Summe mit positiven Gewichten kann keine Lösungen im Inneren dieses Intervalls finden (z. B. am Punkt $x=1$), da die Linearkombination der Kriterien ihr Minimum nur an den Endpunkten $x=0$ oder $x=2$ erreicht.

Verwandte Konzepte und Anwendungen

Die multikriterielle Optimierung ist eng mit der multikriteriellen Entscheidungsfindung (MCDM) verbunden, die sich mit der Auswahl der besten Alternative unter Berücksichtigung der Präferenzen eines Entscheidungsträgers befasst. Die wichtigsten Methoden zur Umwandlung eines multikriteriellen Problems in ein skalares Problem (Skalarisierung) umfassen:

• Die Methode der gewichteten Summe.
• Die $\epsilon$-Constraint-Methode: Ein Kriterium wird optimiert, während die anderen in Nebenbedingungen der Form $f_i(x)\le {\epsilon }_i$ umgewandelt werden. Diese Methode kann auch Lösungen in nicht-konvexen Teilen der Front finden.

Die multikriterielle Optimierung findet breite Anwendung im Ingenieurwesen, in der Wirtschaft (z. B. Portfolio-Optimierung), im Management und in der Ökologie.

Siehe auch

• Pareto-Optimalität
• Vektoroptimierung
• Entscheidungstheorie
• Entscheidungsunterstützungssysteme
• Operations research