# Downhill-Simplex-Verfahren

Das Downhill-Simplex-Verfahren oder Nelder-Mead-Verfahren ist im Unterschied zum Namensvetter für lineare Probleme (Simplex-Algorithmus) eine Methode zur Optimierung nichtlinearer Funktionen von mehreren Parametern. Er fällt in die Kategorie der Hillclimbing- oder Downhill-Suchverfahren. Angewendet werden kann er z. B. auch beim Kurvenfitten.
Es wurde von John Nelder und Roger Mead 1965 eingeführt.

## Grundlagen

Als Besonderheit kommt dieser Simplex-Algorithmus ohne Ableitungen der Funktion nach den Parametern aus, welche bei manchen Problemstellungen nicht mit vertretbarem Aufwand berechenbar sind. Durch sinnvolle Vergleiche der Funktionswerte mehrerer Punkte im Parameterraum wird ähnlich wie bei einer Regula falsi mit Schrittweitensteuerung die Tendenz der Werte und der Gradient Richtung Optimum angenähert. Das Verfahren konvergiert nicht extrem schnell, ist aber dafür einfach und relativ robust.
Der Algorithmus basiert auf einem Simplex, dem einfachsten Volumen im $N$-dimensionalen Parameterraum, das aus $N+1$ Punkten aufgespannt wird. Im Eindimensionalen auf der Zahlengeraden ist das eine Strecke, im Zweidimensionalen ein Dreieck usw. Jeder Punkt entspricht dabei einem (Koordinaten-)Satz Parameter (bzw. Variablen), und zu jedem Punkt kann man einen Funktionswert berechnen, den man z. B. als Fehler- oder Kostenwert ansehen kann. Unter diesen $N+1$ Punkten ermittelt man dann den „schlechtesten“ und den „besten“. Von einem Iterationsschritt zum nächsten wird normalerweise der „schlechteste“ dieser Punkte durch einen neuen ersetzt, der hoffentlich „besser“ ist. Den „besten“ Punkt behält man als bisher beste Lösung immer bei.
Bei einer Visualisierung im Zweidimensionalen mit Höhenlinien für die zu optimierende Funktion sieht man (in den Bildern rechts) ein Dreieck, das sich zielstrebig dem Optimum nähert, indem es sich um eine seiner Seiten klappt, sich streckt oder in der Nähe des Optimums um dieses zusammenzieht. Siehe auch die Abbildung ganz unten.
Ohne Ableitungen entfallen diverse Fallen wie pathologisches Verhalten dieser Ableitungen bei Unstetigkeiten, sodass das Verfahren zwar im Allgemeinen langsamer konvergiert (nämlich linear) als Optimierungsverfahren mit Ableitungen, aber wesentlich robuster arbeitet. Die möglichen Fallen beim Simplex-Verfahren sind ähnlich wie bei den meisten Optimierungsverfahren unverhoffte lokale Nebenminima (bzw. -optima), auf die konvergiert werden kann, oder dass das Verfahren sich für einen oder mehrere Parameter zu früh auf einen konstanten Wert zusammenzieht.

## Algorithmus

Das Downhill-Simplex-Verfahren findet ein lokales Optimum einer Funktion mit $N$ Variablen (Parametern). Gegeben ist eine Zielfunktion $f:\mathbb {R} ^{N}\rightarrow \mathbb {R}$, die jedem Punkt im Lösungsraum einen Wert (Qualität der Lösung) zuordnet. $\alpha ,\gamma ,\beta ,\sigma \in \mathbb {R}$ sind Parameter des Algorithmus.
* wähle $N+1$ Anfangspunkte $x_{0},x_{1},\cdots ,x_{N}\in \mathbb {R} ^{N}$, die den Simplex bilden
* sortiere die Punkte nach dem Wert der Zielfunktion $f$, so dass $x_{0}$ der beste, $x_{N-1}$ der zweitschlechteste und $x_{N}$ der schlechteste ist
* bilde von allen außer dem schlechtesten Punkt den Mittelpunkt: $m={\frac {1}{N}}\sum \nolimits _{i=0}^{N-1}x_{i}$
* reflektiere den schlechtesten Punkt am Mittelpunkt: $r=m+\alpha (m-x_{N})$
* wenn $r$ besser ist als $x_{0}$: bestimme den expandierten Punkt $e=r+\gamma (r-m)$, ersetze $x_{N}$ durch den besseren der beiden Punkte $e,r$ und gehe zu Schritt 2
* wenn $r$ besser ist als der zweitschlechteste Punkt $x_{N-1}$: ersetze $x_{N}$ durch $r$ und gehe zu Schritt 2
* sei $h$ der bessere der beiden Punkte $x_{N},r$. Bestimme den kontrahierten Punkt $c=h+\beta (m-h)$
* wenn $c$ besser ist als $x_{N}$: ersetze $x_{N}$ durch $c$ und gehe zu Schritt 2
* komprimiere den Simplex: für jedes $i\in \{1,\cdots ,N\}$: ersetze $x_{i}$ durch $x_{i}+\sigma (x_{0}-x_{i})$
* gehe zu Schritt 2
Nach diesen Regeln wird die Iteration so lange weitergeführt, bis ein Konvergenzkriterium erfüllt ist. Der Simplex wird sich dabei in Richtung eines lokalen Optimums verlagern und sich schließlich um dieses herum zusammenziehen.
| Parameter | sinnvoller Bereich | typischer Wert |
| $\alpha$ (Reflexion) | $\alpha >0$ | $\alpha =1$ |
| $\gamma$ (Expansion) | $\gamma >0$ | $\gamma =1$ |
| $\beta$ (Kontraktion) | $0<\beta <1$ | $\beta =0{,}5$ |
| $\sigma$ (Komprimierung) | $0<\sigma <1$ | $\sigma =0{,}5$ |
Die $N+1$ Anfangspunkte müssen so gewählt werden, dass sie einen Simplex der Dimension $N$ aufspannen und nicht alle in einer Hyperebene von kleinerer Dimension liegen, d. h. die Vektoren $x_{1}-x_{0},x_{2}-x_{0},...,x_{N}-x_{0}$ müssen linear unabhängig sein. Man kann z. B. einen Punkt als Startpunkt wählen und $N$ weitere ermitteln, indem man von diesem aus jeweils einen der Parameter um einen von 1 verschiedenen Faktor (falls der Parameter nicht 0 sein kann) oder einen von 0 verschiedenen Summanden erhöht. Alternativ: Man gibt für jeden Parameter zwei verschiedene Werte vor, berechnet den ersten Punkt mit allen Erstwerten und die anderen $N$ Punkte auch mit den Erstwerten, nur dass jeweils einer der Parameter durch seinen Zweitwert ersetzt wird. Oder man wählt Zufallspunkte aus dem Lösungsraum.

## Grafische Darstellung eines Beispiellaufs

Das Bild zeigt das Ergebnis eines Programmlaufs. Die roten und blauen Linien stellen die Gefällelinien für Täler bzw. Berge dar. Es handelt sich um einen Kreisgraben in einer schrägen Ebene, es interessiert hier das lokale Minimum innerhalb des Kreisgrabens. Die Simplex-Iteration findet das Minimum an der Kreuzungsstelle der roten Linien. In $x$- und $y$-Richtung reicht die Grafik von 0 bis 4.

## Erweiterungen für Notfälle

Wie bei anderen Verfahren besteht immer die Gefahr, dass auf ein Nebenoptimum konvergiert wird. Diese Gefahr kann man durch mehrere Maßnahmen mindern:
* Nach einer bestimmten Anzahl von Schritten wird neu angesetzt. Dazu wird der bisher beste Punkt beibehalten und um ihn herum ein neuer Start-Simplex aufgebaut, indem bei jedem weiteren Punkt die Koordinate (nur) eines Parameters z. B. um 5 % variiert wird.
* Genau wie eben, nur werden die zusätzlichen Simplex-Punkte durch Zufallswerte noch mehr flexibilisiert.
* Statt solche Maßnahmen nach einer festen Anzahl von Schritten zu ergreifen, kann man den Zeitpunkt auch vom aktuellen Stand der Iteration abhängig machen. Dazu muss das Problem natürlich besser bekannt sein, dass man sich dessen auch sicher sein kann.
* Alternativ kann man sogar den Zeitpunkt der Neuansetzung per Zufallszahl variabel gestalten.
* Eine zusätzliche Sicherheitsabfrage könnte den Fall abfangen, dass sich nur einer der Parameter vorzeitig festgelaufen hat, dann könnte man ihm eine Spezialbehandlung zukommen lassen.
All diese Varianten erfordern eine intensive Beschäftigung mit dem jeweiligen konkreten Problem, es gibt leider keine allgemein gültigen Kochrezepte dafür.

## Erweiterung zum Kurvenfitten

Will man nicht eine einzelne analytische Funktion von $N$ Parametern (Koordinaten) optimieren, sondern eine Theoriefunktion an eine Messkurve anpassen, ist nur ein kleiner zusätzlicher Schritt notwendig: Als zu optimierende Funktion verwendet man oft die Fehlerquadratsumme, also die Summe aus den Quadraten der Differenzen aus den einzelnen Messwerten (Kurvenpunkten) und den Theoriefunktionswerten an denselben Stellen, wobei letztere einerseits von der $x$-Koordinate der Messkurve abhängen und zusätzlich von den $N$ Parametern. Ob man aus der Fehlerquadratsumme noch die Wurzel zieht, ist für das Simplex-Verfahren irrelevant. Siehe hierzu auch Methode der kleinsten Quadrate.
Jedoch ist das Downhill-Simplex-Verfahren sehr flexibel (anders als etwa der Levenberg-Marquardt-Algorithmus), man kann also je nach Situation auch andere Funktionen zur Optimierung verwenden:
* Die Daten haben eine starke Streuung: Statt der Summe der quadrierten Abweichung minimiert man die Summe der Beträge der Abweichungen. Ausreißer beeinflussen das Ergebnis weniger.
* Kurvenanpassung arbeitet normalerweise mit der Annahme, dass der Fehler der abhängigen Variable $(\Delta y=y_{calc}-y_{obs})$ unabhängig von der zugehörigen unabhängigen Variable ist (Homoskedastizität). In manchen Fällen ist jedoch $\Delta y$ eine Funktion von $x$. Diese Situation tritt insbesondere dann auf, wenn sich $x$ und $y$ über mehrere Größenordnungen erstrecken. Würde man in solchen Fällen die Fehlerquadratsumme minimieren, bekäme man eine gute Anpassung bei großen $x/y$-Werten, aber eine sehr schlechte bei kleinen, die zur Fehlerquadratsumme kaum beitragen. In solchen Fällen minimiert man $\chi ^{2}$, also die Summe der quadrierten relativen Abweichungen $\Sigma (\Delta y/y)^{2}$.

## Beispielimplementierung

Pseudocode (C-ähnlich):