zum Directory-modus

Grundlagen der Parameterschätzung/Optimierung

Simplexverfahren nach Nelder-Mead

Nelder und Mead haben durch Hinzunehmen von Reflexions-, Expansions- und Kontraktionsregeln einen unregelmäßigen Simplex aufgebaut, dessen Größe an die jeweilige Situation angepasst werden kann. Zur Abgrenzung des Namen Simplex gegenüber dem Simplex-Verfahren bei linearen Problemen wird dieses Verfahren Simplex-Verfahren nach Nelder-Mead genannt.

Grundsätzlich funktioniert der Aufbau eines neuen Simplex ähnlich wie bei der Basismethode. Wir möchten diese Methode an Hand eines zweidimensionalen Raumes erklären. Wie aus der Einführung bekannt, bedeutet das für den Simplex, dass er drei Ecken besitzt.

Ziel des Verfahrens ist es, nicht - wie bei der Basismethode - möglichst mit einem Eckpunkt das gewünschte Optimum zu erreichen, sondern den Simplex hinreichend klein zu bekommen, um mit ziemlicher Genauigkeit sagen zu können, wo sich das Optimum befindet.

Bitte Flash aktivieren.

Abb.1

Entwicklung eines Simplex nach Nelder-Mead

Es sei ein Simplex gewählt, beschrieben durch die Punkte (xs,xb,xz). Nun wird der Eckpunkt herausgesucht, der den schlechtesten Zielfunktionswert xs besitzt.Dieser Punkt wiederum wird am Schwerpunkt xp der übrigen beiden Punkte reflektiert. Es ist ein Simplex entstanden mit einem neuen Punkt, dem Reflexionspunkt xr.

Abb.2

Der Zielfunktionswert des neuen Punktes xr wird berechnet: xr=xp+α·(xp+xs)

Der Reflexionskoeffizient α ist positiv zu wählen. Für α=1 findet eine einfache Spiegelung (analog zur Basismethode) statt.

Ist f(xr) kleiner als der zweitbeste Punkt des Ausgangs-Simplex f(xz) und größer/gleich f(xb), wird wieder von vorn begonnen, jedoch wird xs (schlechtester Punkt) nun durch xr (Reflexionspunkt) ersetzt.

Abb.3

Ist f(xr) kleiner, also besser als f(xb) (bester Punkt), wird die Suche in Reflexionsrichtung fortgesetzt, da diese Richtung erfolgversprechend scheint. Dies erfolgt durch Erstellen des Expansionspunktes xe. xe berechnet sich aus: xe=xp+y·(xp-xs)

Der Expansionskoeffizient γ muss größer 1 sein, damit es zur Expansion kommt.

Ist die Expansion mit f(xe)<f(xb) erfolgreich (also besitzt der Expansionspunkt einen kleineren Zielfunktionswert als der bisherige beste Punkt), dann wird der schlechteste Punkt xs durch den Expansionspunkt xe ersetzt. Anschließend erfolgt die Prüfung auf Abbruch. Verbessert die Expansion nicht den besten Punkt, also gilt f(xe)f(xb), dann wird der schlechteste Punkt durch den Reflexionspunkt ersetzt. Dann erfolgt die Prüfung auf Abbruch.

Abb.4

Ist f(xr)>f(xz), wäre der neue Punkt (Reflexionspunkt) im modifizierten Simplex der schlechteste. Bei der Basismethode (hier für α=1) kommt es zur Oszillation, es erfolgt jetzt eine Kontraktion des Simplex. Wenn f(xr)>f(xs) gilt, berechnet sich der Kontraktionspunkt xk zu xk=xp+β·(xs-xp)

Der Kontraktionskoeffizient β ist eine Zahl zwischen 0 und 1. Dieser Kontraktionspunkt liegt zwischen dem schlechtesten Punkt und dem Schwerpunkt.

Bei f(xk)f(xs) ersetzt der Kontraktionspunkt den schlechtesten Punkt, dann wird auf Abbruch geprüft. Ist f(xk)>f(xs), wird der gesamte Simplex zum besten Punkt hin kontrahiert. Alle Simplexpunkte werden nach Vorschrift durch xj+xb/2 ersetzt.

Abb.5

Ist f(xr)f(xs), also der Reflexionspunkt nicht schlechter als der bisherige schlechteste Punkt, dann wird der Kontraktionspunkt berechnet gemäß: xk=xp+β·(xr-xp)

Dieser Kontraktionspunkt liegt zwischen dem Reflexionspunkt und dem Schwerpunkt.

Ist f(xk)f(xs), also besser als der schlechteste Punkt, ersetzt er diesen. Trifft das nicht zu, f(xk)>f(xs), wird der gesamte Simplex zum besten Punkt hin kontrahiert. Alle Simplexpunkte werden wie oben ersetzt. Anschließend erfolgt die Prüfung auf Abbruch. Sie ist nach verschiedenen Methoden möglich. Eine Methode besteht darin, den Abbruch dann vorzunehmen, wenn die Abweichung (Standardabweichung) kleiner als eine vorgegebene Schranke ε ist. Meist gibt man sich jedoch eine Anzahl von Schritten vor, da es sonst zur unendlichen Iteration kommen kann.

Zusammenfassend sollte man die folgende Animation ansehen. Durch das in der Animation dargestellte Flussdiagramm werden die Zusammenhänge zwischen den einzelnen Schritten, die der Simplex bei diesem Verfahren durchläuft, klarer. Es wird hier das gleiche Problem, wie bei der Basismethode - die Minimumsuche - gelöst.

Animation: Flussdiagramm Simplex-Verfahren nach Nelder-Mead

Seite 12 von 19