imported>Qajnen: /* growthexperiments-addlink-summary-summary:1|1|0 */

2024-12-20T12:59:05Z

growthexperiments-addlink-summary-summary:1|1|0

Neue Seite

'''Robuste Optimierung''' ist ein Gebiet der [[Optimierung (Mathematik)|Optimierung in der Mathematik]]. Dabei geht es um [[Optimierungsproblem|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 Optimierung|lineare Optimierungsproblem]]

: <math> \max_{x,y} \ \{3x + 2y\} \ \ \mathrm { unter\ den\ Nebenbedingungen }\ \ x,y\ge 0; cx + dy \le 10, \forall (c,d)\in P </math>
mit <math>P</math> als Untermenge von <math>\mathbb{R}^{2}</math>.

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

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

Für den Fall, dass <math>P</math> 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 '''[[Stochastik|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]]:

: <math>\hat{\rho}(x,\hat{u}):= \max_{\rho\ge 0}\ \{\rho: u\in S(x), \forall u\in B(\rho,\hat{u})\}</math>

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

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

== Globale Robustheit ==

Gegeben sei das robuste Optimierungsproblem

: <math>\max_{x\in X}\ \{f(x): g(x,u)\le b, \forall u\in U\}</math>

wobei <math>U</math> die Menge aller ''möglichen'' Werte von <math>u</math> bezeichnet, die in Frage kommen.

Dies ist ein ''globales'' robustes Optimierungsproblem dahingehend, dass die robuste Nebenbedingung <math>g(x,u)\le b, \forall u\in U</math> alle ''möglichen'' Werte von <math>u</math> betrachtet.

Die Schwierigkeit bei solch einer ''globalen'' Nebenbedingung besteht darin, dass eine Situation auftreten kann, in der es kein <math>x\in X</math> gibt, dass diese Nebenbedingung erfüllt. Selbst wenn solch ein <math>x\in X</math> existiert, kann die Nebenbedingung selber zu ''konservativ'' sein. Sie kann dazu führen, dass die Lösung <math>x\in X</math> nur zu einem kleinen Zielfunktionswert <math>f(x)</math> führt, der jedoch nicht repräsentativ für andere Lösungen <math>x\in X</math> steht. Es könnte zum Beispiel ein <math>x'\in X</math> geben, das die robuste Nebenbedingung nur ganz leicht verletzt, aber einen viel größeren Zielfunktionswert <math>f(x')\in X</math> 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 <math>g(x,u)\le b</math> zu erfüllen, wobei <math>x\in X</math> die Entscheidungsvariable bezeichnet und <math>u</math> einen Parameter mit den möglichen Werten <math>U</math>. Gibt es kein <math> x\in X</math>, so dass <math>g(x,u)\le b,\forall u\in U</math>, dann ist folgendes Maß für Robustheit plausibel:

: <math>\rho(x):= \max_{Y\subseteq U} \ \{size(Y): g(x,u)\le b, \forall u\in Y\} \ , \ x\in X</math>

wobei <math>size(Y)</math> ein angemessenes Maß für die "Größe" der Menge <math>Y</math> darstellen soll. Ist beispielsweise <math>U</math> eine endliche Menge, dann kann <math>size(Y)</math> als die [[Mächtigkeit (Mathematik)|Kardinalität]] der Menge <math>Y</math> betrachtet werden.

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

Dadurch entsteht das folgende robuste Optimierungsproblem:

: <math>\max_{x\in X, Y\subseteq U} \ \{size(Y): g(x,u) \le b, \forall u\in Y\}</math>

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 (Wirtschaftswissenschaftler)|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).

[[Kategorie:Optimierung]]

Robuste Optimierung - Versionsgeschichte

imported>Qajnen: /* growthexperiments-addlink-summary-summary:1|1|0 */