Robuste Optimierung

Robuste Optimierung ist ein Gebiet der Optimierung in der Mathematik. Dabei geht es um Optimierungsprobleme, in denen nach Stabilität gegenüber Unsicherheit und/oder Variabilität in den Werten der Problemparameter gestrebt wird.

Geschichte

Die Ursprünge der Robusten Optimierung gehen zurück auf die Begründung der modernen Entscheidungstheorie in den 1950er Jahren. Dabei wurden Worst-Case-Analysen entwickelt, um mit hohen Unsicherheiten umgehen zu können. Robuste Optimierung wurde in den 70er Jahren zu einem eigenen Forschungsgebiet mit verschiedenen Entwicklungen in Gebieten wie Operations Research, Kontrolltheorie, Statistik, Wirtschaftswissenschaft u. a.

Beispiel

Gegeben sei das einfache lineare Optimierungsproblem

$\max _{x,y}\ \{3x+2y\}\ \ \mathrm {unter\ den\ Nebenbedingungen} \ \ x,y\geq 0;cx+dy\leq 10,\forall (c,d)\in P$

mit $P$ als Untermenge von $\mathbb {R} ^{2}$.

Die Bedingung $\forall (c,d)\in P$ in den Nebenbedingungen macht dieses Problem zu einem 'robusten' Problem. Sie bedeutet, dass für jedes Paar $(x,y)$ die Nebenbedingungen $cx+dy\leq 10$ für den 'schlimmsten' Fall von $(c,d)\in P$ gelten muss, also auch für das Paar $(c,d)\in P$, das den Wert von $cx+dy$ für gegebene $(x,y)$ maximiert.

Für den Fall, dass der Parameterraum $P$ endlich ist und damit nur aus endlich vielen Elementen besteht, ist dieses Robuste Optimierungsproblem selber ein lineares Optimierungsproblem: Für jedes Paar $(c,d)\in P$ gibt es eine lineare Nebenbedingung $cx+dy\leq 10$.

Für den Fall, dass $P$ nicht eine endliche Menge ist, ist dieses Problem ein lineares, semi-infinites Optimierungsproblem, also ein lineares Optimierungsproblem mit endlich vielen (zwei) Entscheidungsvariablen und unendlich vielen Nebenbedingungen.

Klassifizierung

Es gibt eine Reihe von Klassifizierungskriterien für Probleme bzw. Modelle der Robusten Optimierung. So ist z. B. eine Unterscheidung zwischen Problemen mit lokalen oder globalen Robustheitsmodellen möglich, oder auch zwischen stochastischen und nichtstochastischen Robustheitsmodellen. Moderne Verfahren der Robusten Optimierung sind vor allem auf nichtstochastischen Robustheitsmodellen aufgebaut, die sich am schlimmsten (Worst-Case-)Fall orientieren.

Lokale Robustheit

Modelle mit lokaler Robustheit versuchen, den nominalen Wert eines Parameters gegen kleine Störeinflüsse zu schützen. Ein Modell dafür ist das Modell des Stabilitätsradius:

${\hat {\rho }}(x,{\hat {u}}):=\max _{\rho \geq 0}\ \{\rho :u\in S(x),\forall u\in B(\rho ,{\hat {u}})\}$

mit ${\hat {u}}$ als dem nominalen Wert des Parameters, $B(\rho ,{\hat {u}})$ als eine Kugel mit Radius $\rho$, die zentriert ist im Punkt ${\hat {u}}$, und $S(x)$ als die Menge an Werten von $u$, die die für die Entscheidung $x$ gegebenen Stabilitäts- bzw. Effizienzeigenschaften erfüllen.

Die Robustheit (bzw. der Stabilitätsradius) der Entscheidung $x$ ist damit der Radius der größten Kugel, die zentriert ist im Punkt ${\hat {u}}$, von der alle Elemente die Stabilitätskriterien von $x$ erfüllen.

Globale Robustheit

Gegeben sei das robuste Optimierungsproblem

$\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}$

wobei $U$ die Menge aller möglichen Werte von $u$ bezeichnet, die in Frage kommen.

Dies ist ein globales robustes Optimierungsproblem dahingehend, dass die robuste Nebenbedingung $g(x,u)\leq b,\forall u\in U$ alle möglichen Werte von $u$ betrachtet.

Die Schwierigkeit bei solch einer globalen Nebenbedingung besteht darin, dass eine Situation auftreten kann, in der es kein $x\in X$ gibt, dass diese Nebenbedingung erfüllt. Selbst wenn solch ein $x\in X$ existiert, kann die Nebenbedingung selber zu konservativ sein. Sie kann dazu führen, dass die Lösung $x\in X$ nur zu einem kleinen Zielfunktionswert $f(x)$ führt, der jedoch nicht repräsentativ für andere Lösungen $x\in X$ steht. Es könnte zum Beispiel ein $x'\in X$ geben, das die robuste Nebenbedingung nur ganz leicht verletzt, aber einen viel größeren Zielfunktionswert $f(x')\in X$ erreicht. In diesen Fällen kann es notwendig sein, die robuste Nebenbedingung etwas aufzuweichen und/oder die Formulierung des Problems zu ändern.

Beispiel

Angenommen, das Ziel ist es, die Nebenbedingung $g(x,u)\leq b$ zu erfüllen, wobei $x\in X$ die Entscheidungsvariable bezeichnet und $u$ einen Parameter mit den möglichen Werten $U$. Gibt es kein $x\in X$, so dass $g(x,u)\leq b,\forall u\in U$, dann ist folgendes Maß für Robustheit plausibel:

$\rho (x):=\max _{Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in Y\}\ ,\ x\in X$

wobei $size(Y)$ ein angemessenes Maß für die "Größe" der Menge $Y$ darstellen soll. Ist beispielsweise $U$ eine endliche Menge, dann kann $size(Y)$ als die Kardinalität der Menge $Y$ betrachtet werden.

Die Robustheit der Entscheidung ist damit die Größe der größten Untermenge von $U$, für die die Nebenbedingung $g(x,u)\leq b$ für jedes $u$ in dieser Menge erfüllt ist. Die optimale Entscheidung ist damit diejenige mit dem größten Robustheitswert.

Dadurch entsteht das folgende robuste Optimierungsproblem:

$\max _{x\in X,Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in Y\}$

Die beschriebene Bedeutung von Globaler Robustheit wird in der Praxis nicht oft verwendet, da die dadurch entstehenden robusten Optimierungsprobleme normalerweise (jedoch nicht immer) sehr schwer zu lösen sind.

Literatur

• Armin Scholl: Robuste Planung und Optimierung. Grundlagen, Konzepte und Methoden, experimentelle Untersuchungen. Physica-Verlag, Heidelberg 2001, ISBN 3-7908-1408-3 (zugl. Dissertation, TU Darmstadt).