Diskussion:Downhill-Simplex-Verfahren

Konvergenz

"Das Verfahren konvergiert in etwa linear" Kann jemand dafür bitte evtl. eine Quelle angeben? Ich hätte dazu was im zweiten Literaturverweis anhand dessen Titel erwartet (Convergence Properties of the Nelder-Mead Simplex Method in low Dimensions) - aber gerade das "in low Dimensions" ist dort der Haken: die Analysen beschränken sich auf 1 bis 2 Dimensionen. --88.73.211.225 00:53, 9. Mär. 2007 (CET)

Nein, ich kenne keinerlei Literaturverweis auf diese Angabe. Aber im Artikel wird die Parallele zur Regula Falsi gezogen, und die trifft meiner Meinung nach zu. Weniger als linear zu konvergieren geht ja wohl kaum ohne besondere Dummheiten. Ich nehme an, dass das Verfahren wegen seiner Schrittweitensteuerung (die es eben an Regula Falsi erinnern lässt) etwas besser als linear konvergiert, daher die Formulierung "in etwa linear". --PeterFrankfurt 01:40, 9. Mär. 2007 (CET)

Mittelpunkt des Simplex reflektieren

"Am Mittelpunkt des Simplex reflektieren" ist m.E: nicht richtig. Bei Einem Dreieck wird an der Gegenseite reflektiert, beim Tetraeder an der etsprechen Fläche etc. Die lineare Konvergenz von einem 1D auf mehrdimensionales Problem übertragen halte ich für sehr gewagt! --Langläufer 18:47, 18. Jun. 2008 (CEST)

Stimmt, es wird der Mittelpunkt des Simplex minus dem schlechtesten Punkt verwendet, siehe Listing: schlechtester Punkt liegt auf Index 0 im Array N0, und die Mittelwertbildung für P* (Index NP+3) erfolgt erst ab Index 1. Danke für den Hinweis. Werde das mal ändern. --PeterFrankfurt 22:35, 18. Jun. 2008 (CEST)

Code

Zunächst ist der Code komplett unverständlich. Wenn hier Code in Artikel eingebunden wird, dann ist das Pseudocode (und das schon nur in Ausnahmefällen), eben damit man kurz und knapp sieht worums geht. Eine Darstellung in einer antiquierten Programmiersprache die über drei Seiten geht, erfüllt das ganz sicher nicht. --P. Birken 15:37, 21. Sep. 2008 (CEST)

Hmm, ich gebe ja zu, dass der Code überhaupt nicht elegant und auch nicht übermäßig transparent ist. Er ist aber authentisch und in der Praxis bewährt. Wie wäre es mit Plan B, wenn man diesen Code hier auf die Diskussionsseite verlagert (aber eher oben hin), sozusagen als Artikelergänzung, und in den Artikel eine Pseudocodeversion setzt? --PeterFrankfurt 02:00, 22. Sep. 2008 (CEST)

Der BASIC-Code ist nicht schön, aber ganz ohne Code oder Pseudocode wird man den Algorithmus nicht verstehen. Hier auf der Diskussionsseite hat er nichts verloren. --Langläufer 08:57, 22. Sep. 2008 (CEST)

Gegen einen Pseudocode habe ich nichts. --P. Birken 18:54, 25. Sep. 2008 (CEST)

Dann mach ich das mal, kann aber ein bisschen dauern, habe derzeit noch ein paar andere Sachen um die Ohren. --PeterFrankfurt 01:13, 26. Sep. 2008 (CEST)

Also ich bin ziemlich verzweifelt. Das ist jetzt schon mein dritter Anlauf zu diesem Pseudocode. Ich habe gekürzt und gekürzt und abstrahiert, aber einige Implementierungsdetails wollte ich drinlassen, weil das für nicht so Geübte Stolpersteine sein könnten, wenn sie das selbst mal umsetzen wollen. Dann bin ich auf die Idee mit den if-then-else-Klammern links gekommen, um deren Struktur zu verdeutlichen. Aber allgemein fehlt es halt an Übersichtlichkeit. Da war das konkrete BASIC eher besser. --PeterFrankfurt 00:44, 2. Nov. 2008 (CET)

Ist das legal, was ich da gerade mit dem Link zur alten Basic-Implementierung in einer älteren Artikelversion gemacht habe? So wird nicht jedermann damit konfrontiert, sondern nur derjenige, der keine Berührungsängste mit QBasic hat und weiß, was da auf ihn zukommen könnte. --PeterFrankfurt 00:07, 23. Nov. 2008 (CET)

Uneindeutige Beschreibung und fehlende Alternative?

Sowohl auf der englischen Seite als auch in Numerical Recipes gibt es vier Alternativen: "Reflection", "Expansion", "Contraction" und "Shrink step". Der "Shrink step" fehlt hier. Weiß jemand warum das so ist? --Mknauer 14:37, 24. Apr. 2009 (CEST)

Gestoßen bin ich auf das Problem, da mir die Schritte a) b) c) nicht eindeutig beschrieben erscheinen. Sehe ich das so richtig, dass nach allen Entscheidungen zum Schritt (2) gesprungen wird? --Mknauer 14:37, 24. Apr. 2009 (CEST)

Doch, den shrink step gibt es hier auch, er wird auf deutsch als komprimieren oder Kontraktion bezeichnet. Aber die englische Contraction (sorry für Namenswirrwar) fehlt tatsächlich in der Beschreibung, ist aber im Pseudocode enthalten, da müssen wir mal nachbessern. - Und ja, die Schleife springt immer wieder zum Schritt 2 zurück, siehe Schritt (4). --PeterFrankfurt 00:47, 25. Apr. 2009 (CEST)

So, das müsste jetzt etwas korrekter sein. --PeterFrankfurt 00:57, 25. Apr. 2009 (CEST)

Es scheinz, als ob der Algorithmus jetzt vollständig ist, aber eindeutig ist er an so ziemlich keiner Stelle. In keinem Punkt ist mir eindeutig klar, was gemeint ist. Der Höhepunkt ist dann der Schritt (d) mit "diesem neuen Punkt". Die englische Version ist wesentlich besser. -- 84.169.51.86 19:23, 19. Jun. 2009 (CEST)

Also wenn man den Satz davor liest, wo ein neuer Punkt eingeführt wird, sollte das doch eindeutig sein. Die englische Version mit den schönen Formeln sieht allerdings wirklich netter aus, da könnte sich mal jemand aufraffen und das rüberholen. Obwohl ich mir nicht sicher bin, ob die Formeln alle richtig sind, z. B. geht es bei Mittelungen und so immer von Index 0 bis N+1, wo ich das nur mit dem "Rest" ab Index 1 kenne. --PeterFrankfurt 00:57, 20. Jun. 2009 (CEST)

Unlogischer Schritt im Algorithmus / Bewertung der Expansion

Im vorgeschlagenen Algorithmus wird nach der Expansion geprüft, ob y_e < y_min. Diese Prüfung sollte durch y_e < y_r ersetzt werden. Wenn y_e < y_min aber y_e > y_r, dann würde man x_r zugunsten des schlechteren Simplex x_e verwerfen. Auch die nachfolgenden Ersetzungen erscheinen dadurch logischer. --137.131.17.168 23:06, 16. Aug. 2010 (CEST)

Mein Reden seit langem, siehe Benutzer_Diskussion:PeterFrankfurt#Downhill-Simplex-Verfahren, vor allem gegen Ende dieses Diskussionskapitels. --PeterFrankfurt 02:53, 17. Aug. 2010 (CEST)

J.C. Lagarias (SIAM J. OPTIM. Vol. 9, No. 1, pp. 112-147; 1998) schreibt in einer ausführlichen und weithin beachteten Analyse des Algorithmus: "The 1965 paper contains several ambiguities about strictness of inequalities and tie-breaking that have led to differences in interpretation of the Nelder-Mead algorithm. What we shall call "the" Nelder-Mead algorithm ... includes well-defined tie-breaking rules ... and accepts the better of the rejected and expanded points in step 3 ..." und weiterhin "Standard practice today ... accepts the better of x_r and x_e if both give an improvement over x₁.". Die Benutzung x_e macht nur Sinn, wenn der Algorithmus bei Anwendung auf eine schlecht konditionierte Funktion Gefahr läuft das Minimum zu verfehlen. Andererseits ist das Downhill-Simplex-Verfahren für solche Funktionen nicht geeignet und sollte durch andere Verfahren ersetzt werden. Auch die englische Seite favorisiert x_r (Totschlagargument).--137.131.17.168 01:43, 19. Aug. 2010 (CEST)

Algorithmus

Woher kommt denn das h im Punkt 7? Finde den Alogrithmus daher nicht verständlich. Würde es auch ändern, falls mir nicht jemand sagt, wie das zu verstehen ist. (nicht signierter Beitrag von Vulpinus2 (Diskussion | Beiträge) 09:31, 12. Aug. 2015 (CEST))

Antwort: "h" ist der bessere der beiden Punkte xN (schlechtester Punkt) und des reflektierten Punktes (nicht signierter Beitrag von 129.187.69.251 (Diskussion) 12:39, 13. Aug. 2016 (CEST))

Widersprüchliche Formeln

Bei den Formeln in Abschnitt "Der Algorithmus selbst" für "expandiert" (5.) und "kontrahiert" (7.) sind im Vergleich zur Grafik die Gewichte (oder nach anderer Sichtweise die Punkte) vertauscht, was zwar bei 7. mit beta = 1/2 keine Unterschied macht, bei 5. mit gamma = 2 aber schon.

In der englischen Version https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method wird u. a. auf http://www.brnt.eu/phd/node10.html#SECTION00622200000000000000 verlinkt; in der Grafik dort - übrigens ein imho sehr guter Pseudocode (vgl. Diskussion weiter oben) - stimmen die Formeln mit der Grafik (und nicht der Textvariante) hier überein.

--Sandwichx (Diskussion) 18:34, 18. Mai 2019 (CEST)