WikiDer > Nelder-Mead-Methode

Das Nelder-Mead-Methode ist ein Algorithmus zur Bestimmung des Minimums von a Funktion in mehreren Variablen. Es wurde 1965 von den Briten John Nelder und Roger Mead eingeführt.^[1]

Die Methode findet das Minimum einer Funktion von nein Variablen durch Vergleich der Funktionswerte in der (nein 1) Ecken eines Generals Simplex. Es ist ein Simplex konvexe Schale von nein 1 unabhängige Punkte in der nein-dimensionaler Raum; zum Beispiel ein Dreieck in der zweidimensionalen Ebene oder ein Tetraeder im dreidimensionalen Raum. In jedem Iterationsschritt wird der Scheitel mit dem höchsten Funktionswert durch einen neuen Punkt ersetzt. Der Simplex passt sich somit der Form der Funktion an und zieht sich schließlich um das Minimum zusammen.

Die Methode verwendet nur Funktionswerte, nicht zuerst oder höher Derivate. Es eignet sich daher zur Minimierung von Funktionen, deren analytische Form unbekannt ist, deren Funktionswerte aber das Ergebnis einer Messung oder eines (eventuell teuren) Experiments sind. Die einzigen Annahmen sind, dass die Funktion kontinuierlich und hat ein eindeutiges Minimum im gesuchten Bereich.

Beschreibung der Methode

Die Methode beginnt mit einem anfänglichen Simplex, das durch (nein 1) Punkte ${Displaystil P_{0},P_{1},Punkte P_{n}}$ in dem nein-dimensionaler Raum. Die entsprechenden Funktionswerte sind ${displaystyle y_{0},y_{1},dots y_{n}}$. Wir bezeichnen mit ${displaystyle P_{h}}$ der Punkt mit dem höchsten Funktionswert ${displaystyle y_{h}}$, und mit ${displaystyle P_{l}}$ der Punkt mit dem niedrigsten Funktionswert ${displaystyle y_{l}}$. Es Schwerpunkt aller Punkte außer ${displaystyle P_{h}}$ wird bezeichnet mit ${displaystyle {ar {P}}}$.

In einem Iterationsschritt wird ${displaystyle P_{h}}$ durch einen neuen Punkt ersetzt. Dazu werden drei Operationen verwendet: Reflexion, Kontraktion und Erweiterung.

Das Reflexion von ${displaystyle P_{h}}$ ist ein neuer Punkt ${Anzeigestil P^{*}}$, deren Koordinaten durch die Gleichung gegeben sind:

${displaystyle P^{*}=(1 alpha ){ ar {P}}-alpha P_{h}}$

Das Reflexionsfaktor${displaystyle alpha }$ ist eine vorbestimmte positive Konstante. ${Anzeigestil P^{*}}$ steht auf der linie ${displaystyle P_{h}}$ und ${displaystyle {ar {P}}}$ verbindet quer ${displaystyle {ar {P}}}$ relativ zu ${displaystyle P_{h}}$.

Wenn nun der Funktionswert ${displaystyle y^{*}}$ im ${Anzeigestil P^{*}}$ liegt zwischen ${displaystyle y_{h}}$ und ${displaystyle y_{l}}$, dann ersetzen wir ${displaystyle P_{h}}$ durch ${Anzeigestil P^{*}}$ und beginnen Sie mit dem neuen Simplex von vorne.

Wenn jedoch ${displaystyle y^{*}$, wir haben ein neues Minimum. Dann versuchen wir es Erweiterung umsetzen von ${Anzeigestil P^{*}}$ zu ${Displaystil P^{**}}$:

${displaystyle P^{**}=gamma P^{*} (1-gamma){ar {P}}}$.

Das Ausdehnungskoeffizient${Displaystil-Gamma }$ eine Konstante und größer als 1 ist. Wenn ${displaystyle y^{**}$ ist die Erweiterung erfolgreich und ersetzen wir ${displaystyle P_{h}}$ durch ${Anzeigestil P^{**}}$ und beginnen Sie mit dem neuen Simplex von vorne. Im anderen Fall brachte die Erweiterung keine Verbesserung; wir ersetzen dann ${displaystyle P_{h}}$ durch ${Anzeigestil P^{*}}$ und fang von vorne an.

Wenn es nach der Reflexion endlich so aussieht, als ob ${displaystyle y^{*}>y_{i}}$ für alle ${Anzeigestil ieq h}$, dann bleibt ${displaystyle y^{*}}$ der maximale Funktionswert, wenn wir ${displaystyle P_{h}}$ wird ersetzt durch ${Anzeigestil P^{*}}$. Für den Fall, dass ${displaystyle y^{*}$ wir ersetzen ${displaystyle P_{h}}$ durch ${Anzeigestil P^{*}}$; sonst halten wir ${displaystyle P_{h}}$. Wir bilden dann

${displaystyle P^{**}= eta P_{h} (1- eta ){ ar {P}}}$

und berechnen ${Anzeigestil y^{**}}$.

Das Kontraktionskoeffizient${displaystyle eta }$ ist eine Konstante zwischen 0 und 1. Wenn die Kontraktion erfolgreich ist (${displaystyle y^{**}$), wir ersetzen ${displaystyle P_{h}}$ durch ${Displaystil P^{**}}$ und neu starten. Wenn die Kontraktion fehlgeschlagen ist, d. h. der Punkt ${Anzeigestil P^{**}}$ ist nicht besser als ${displaystyle P_{h}}$, dann ersetzen wir alle ${displaystyle P_{i}}$Tschüss ${Anzeigestil (P_{i} P_{l})/2}$ und neu starten.

Der Algorithmus stoppt, wenn das Minimum innerhalb einer vorgegebenen Genauigkeit erreicht ist. Als Kriterium dafür haben Nelder und Mead den „Standardfehler“ der Funktionswerte genommen:

${displaystyle {sqrt {frac {sum _{i}{(y_{i}-{ar {y}})^{2}}}{n}}}}$

Der Algorithmus stoppt, wenn dieser Wert kleiner als ein vorbestimmter Wert wird. Sie haben dieses Kriterium verwendet, weil es für statistische Probleme nützlich ist.

Neben dem Abbruchkriterium müssen daher vorab drei Konstanten bestimmt werden: ${displaystyle alpha }$, der Kontraktionskoeffizient ${displaystyle eta }$ und der Ausdehnungskoeffizient ${Displaystil-Gamma }$. Die Wahl dieser Konstanten hat einen Einfluss auf die Konvergenzgeschwindigkeit; die beste Strategie war laut Nelder und Mead ${displaystyle alpha =1, eta ={ frac {1}{2}},gamma =2}$. Die Wahl des Anfangssimplex ist ebenfalls wichtig. In einigen Fällen kann das Verfahren zu einem Punkt konvergieren, der nicht das Minimum ist.

Beispiel

Ablauf der Simplex-Methode in der "Bananenfunktion" von Rosenbrock

Die rechte Abbildung veranschaulicht den Ablauf der Methode bei der Suche nach dem Minimum der Funktion:

${displaystyle y=100(x_{2}-x_{1}^{2})^{2} (1-x_{1})^{2}}$

Diese nichtkonvexe Funktion wurde 1960 von Howard Rosenbrock als Testfunktion für Optimierungsalgorithmen vorgeschlagen. Sie ist bekannt als die Tal von Rosenbrock oder der Bananenfunktion von Rosenbrock. Das globale Minimum liegt in einem langen, schmalen, flachen, parabolischen Tal am Punkt ${displaystyle x_{1},x_{2}=1}$. Man sieht, wie sich der Simplex (hier ein Dreieck) zum Talgrund bewegt und sich dann langsam am Talboden zum Minimum entwickelt.