Robuste Optimierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Gegeben sei das einfache lineare Optimierungsproblem

mit als Untermenge von .

Die Bedingung in den Nebenbedingungen macht dieses Problem zu einem 'robusten' Problem. Sie bedeutet, dass für jedes Paar die Nebenbedingungen für den 'schlimmsten' Fall von gelten muss, also auch für das Paar , das den Wert von für gegebene maximiert.

Für den Fall, dass der Parameterraum endlich ist und damit nur aus endlich vielen Elementen besteht, ist dieses Robuste Optimierungsproblem selber ein lineares Optimierungsproblem: Für jedes Paar gibt es eine lineare Nebenbedingung .

Für den Fall, dass 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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:

mit als dem nominalen Wert des Parameters, als eine Kugel mit Radius , die zentriert ist im Punkt , und als die Menge an Werten von , die die für die Entscheidung gegebenen Stabilitäts- bzw. Effizienzeigenschaften erfüllen.

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

Globale Robustheit[Bearbeiten | Quelltext bearbeiten]

Gegeben sei das robuste Optimierungsproblem

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

Dies ist ein globales robustes Optimierungsproblem dahingegen, dass die robuste Nebenbedingung alle möglichen Werte von betrachtet.

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

Beispiel[Bearbeiten | Quelltext bearbeiten]

Angenommen, das Ziel ist es, die Nebenbedingung zu erfüllen, wobei die Entscheidungsvariable bezeichnet und einen Parameter mit den möglichen Werten . Gibt es kein , so dass , dann ist folgendes Maß für Robustheit plausibel:

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

Die Robustheit der Entscheidung ist damit die Größe der größten Untermenge von , für die die Nebenbedingung für jedes in dieser Menge erfüllt ist. Die optimale Entscheidung ist damit diejenige mit dem größten Robustheitswert.

Dadurch entsteht das folgende robuste Optimierungsproblem:

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.

Bibliographie[Bearbeiten | Quelltext bearbeiten]

  • Armin Scholl: Robuste Planung und Optimierung: Grundlagen - Konzepte und Methoden - experimentelle Untersuchungen. Heidelberg 2001, ISBN 3790814083