|
|
Simplex (fminsearch) Anzahl Iterationen |
|
Gast |
Gast
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 25.07.2011, 16:39
Titel: Simplex (fminsearch) Anzahl Iterationen
|
|
Hi,
ich verwende den Simplex aus fminsearch um ein Modell an Daten
zu fitten. Das zugrundeliegende Modell ist eine ODE die in jeder
Iteration mit ode45 gelöst wird.
Folgende Beobachtung: Die Anzahl Iterationen für einen Fittingprozess
ist extrem hoch und die Schrittgrößen sind extrem klein im Vergleich
zu anderenen Optimierungsprogrammen mit einem Simplex.
Kennt jemand dieses Phänomen?
Ist die Implentierung des Simplex in Matlab vielleicht nicht die optimal?
Mich würden einfach ein paar Kommentare dazu interessieren
thx
|
|
|
|
|
Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
Verfasst am: 26.07.2011, 12:49
Titel:
|
|
Hallo Gast,
der Algorithmus für fminsearch ist der so genannte Nelder-Mead-Simplex-Algorithmus, auch Downhill-Simplex-Verfahren genannt. Kann es sein, dass Du den mit dem Simplex-Algorithmus von Dantzig für die lineare Optimierung verwechselst? Oder was meinst Du genau mit "anderen Optimierungsprogrammen mit einem Simplex"?
Der fminsearch-Algorithmus ist zum Fitten tatsächlich nicht ideal, dafür gibt es ja lsqcurvefit oder lsqnonlin oder so.
Herzliche Grüße
Bijick
_________________
>> why
|
|
|
Gast |
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 26.07.2011, 13:45
Titel:
|
|
Hi Bijick
danke für deine Antwort.
Ich vergleiche fminsearch mit einer Nelder-Mead Implementation in
Fortran (kann dir aber nicht genau sagen ob die aus der NAG stammt
oder nicht)
Bei äquivalenten Startwerten braucht die Matlab Implementation ca
den Faktor 5 bis 10 mehr an Iterationen. Läuft aber in das äquivalente
Minimum wie auch der NM-Simplex in Fortran.
Und das macht mich irgendwie stutzig.
Richtig, ich hab bisher auch immer mit lsqcurvefit gearbeitet.
Allerdings ist hier das Problem, dass nie wirklich das
Minimum erreicht wird sondern immer vorher abgebrochen wird.
Das liegt wohl daran, dass der Gradient nicht genau genug intern
berechnet wird. Deswegen war die Idee auf ein ableitungsfreies
Verfahren zu wechslen.
|
|
|
Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
Verfasst am: 26.07.2011, 20:07
Titel:
|
|
Ah so, jetzt verstehe ich. Vielen Dank für die zusätzlichen Infos.
Ich würde an Deiner Stelle einfach mal in den fminsearch-Code schauen, da sieht man ja genau, wie er gemacht ist. Ein Unterschied könnte sein, wie der Start-Simplex gebaut wird. Ich erinnere mich dunkel, das der ungeschickt war, wenn ich Nullen und andere Werte gemischt als Startwerte hatte.
Aber vielleicht hat ja auch jemand anders hier noch Erfahrungen mit fminsearch?
Herzliche Grüße
Bijick
_________________
>> why
|
|
|
Gast |
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 26.07.2011, 20:57
Titel:
|
|
Okay danke, aber so ins Detail will ich nicht gehen und den
Matlab Code auseinander nehmen. Dafür hab ich gerade nicht die
Zeit und nicht die Nerven
Was aber halt schon sehr heftig ist, ist der direkte Vergleich:
Fortran Implementation ca. 200 Iterationen, Dauer ca. 15 sec
Matlab Implementation ca. 1600 Iterationen, Dauer ca. 3 Std.
Und dabei bin ich eigentlich ein Matlab Fan, aber das ...
|
|
|
Harald |
Forum-Meister
|
|
Beiträge: 24.495
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
Verfasst am: 26.07.2011, 21:40
Titel:
|
|
Hallo,
wenn das Minimum nicht erreicht wird, dann würde ich nicht die Funktion wechseln, sondern die Abbruchkriterien von LSQCURVEFIT anpassen (über das letzte Argument bzw. OPTIMSET). Es wird ja normalerweise angegeben, welches Abbruchkriterium gegriffen hat, und dann muss man eigtl nur dieses Kriterium "aufweichen". Die Möglichkeit, dass man in ein lokales Minimum läuft, ist natürlich immer noch gegeben, aber das dürfte bei den meisten (wenn nicht allen) Algorithmen der Fall sein.
Ein eventuelles Problem ist natürlich auch, dass das Bilden von Ableitungen über finite Differenzen unter Simulationsungenauigkeiten von ODE45 leidet. Ich würde also sicherheitshalber die Simulationsungenauigkeit (AbsTol, RelTol) in ODE45 verbessern, um da unerwünschte Effekte zu vermeiden.
Was die Laufzeit angeht, ist u.a. auch die Frage, ob dein MATLAB-Code optimal geschrieben ist - z.B. die Funktion, in der die DGL ausgewertet wird.
Grüße,
Harald
|
|
|
Gast |
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 26.07.2011, 22:16
Titel:
|
|
|
|
|
Hallo Harald,
danke für deine Tipps.
Wie gesagt in jeder Iteration muss eine ODE gelöst werden. Ich löse die ODE mit ode45 und werte dann sol mit deval an den entsprechenden Messzeitpunkten aus für die Least-Squares Summe. Wenn man das noch optimieren kann wäre ich dir für jeden Tipp dankbar.
Mir ist natürlich klar, dass z.b. LSODA in Fortran extrem schneller ist als ode45 in Matlab. Meine Versuche haben ergeben, dass LSODA um den Faktor 50 schneller ist als ode45 im direkten Vergleich bei einer Auswertung. Was ich bisher gehört hab ist, dass einige Leute ode45 z.b. durch einen in C geschrieben Solver ersetzen. Aber darum gehts mir nicht wirklich.
Betreff lsqcurvefit: Da ich die analytische Lsg der ODE natürlich nicht kenne verwende ich die interne Option jacobian = on um den Gradienten per Diffquot zu berechnen. Natürlich könnte man den Gradienten auch über Variationsgleichungen (siehe AMANN) berechnen, aber das bedeutet, dass meine ursprüngliche ODE (System aus 4 ODEs) extrem aufgeblassen wird. Aber würde das was bringen? Wenn dazu jemand Kommentare/Ideen hat würden die mich sehr interessieren.
Ich könnte auch den Diffquot selber mit beliebiger Genauigkeit berechnen aber um das effektiv durchzuführen habe ich gerade keine Idee. Also wie oben, Kommentare/Ideen sind erwünscht.
Also ich muss gestehen, dass ich schon so ziemlich an allen Einstellungen von LSQCURVEFIT rumgeschraubt habe. Aber kann man die Genauigkeit des Diffquot in LSQCURVEFIT auch von außen angeben?
Um auf die Ausgangsfrage zurückzukommen, ich hab einfach das Gefühlt dass der Simplex Code in Matlab nicht wirklich optimal programmiert ist, wegen dem Vergleich zu alten Fortran Programmen, Vergleich Anzahl Iterationen.
|
|
|
Gast |
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 26.07.2011, 22:26
Titel:
|
|
Was ich vielleicht noch erwähnen sollte ist, dass die zugrundeliegende ODE
x'=f(t,x,theta)
in t nur stückweise stetig ist. Aber kann das was damit zu tun haben?
theta sind die zu fittenden Parameter
|
|
|
Gast |
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 26.07.2011, 22:35
Titel:
|
|
|
|
Harald |
Forum-Meister
|
|
Beiträge: 24.495
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
Verfasst am: 28.07.2011, 20:43
Titel:
|
|
|
|
|
Hallo,
Zitat: |
Wie gesagt in jeder Iteration muss eine ODE gelöst werden. Ich löse die ODE mit ode45 und werte dann sol mit deval an den entsprechenden Messzeitpunkten aus für die Least-Squares Summe. Wenn man das noch optimieren kann wäre ich dir für jeden Tipp dankbar. |
Wie gesagt: Simulationsgenauigkeit erhöhen.
Wenn vor der Simulation bekannt ist, an welchen Punkten die Lösung gebraucht wird, dise Punkte direkt in TSPAN angeben.
Ungenauigkeiten in der Lösung ruinieren naheliegenderweise den Differenzenquotienten. Insofern würde ich auch über die Option DiffMinChange bei FSOLVE sicherstellen, dass die Schrittweite für die finiten Differenzen nicht zu klein gewählt wird (erhöht die Gefahr potentieller Probleme durch Simulationsungenauigkeiten).
Dass du in deinem Fall Probleme mit der Effizienz hast, ist naheliegend. Ob das an FSOLVE oder deiner Programmierung (siehe Hinweise oben) liegt, kann ich aus der Ferne nicht beurteilen. In der Regel beurteilt man die Güte eines Algorithmus jedoch anhand einer ganzen Serie von Testproblemen und nicht anhand eines einzigen Problems.
Da Code leichter verständlich als Worte ist, bitte nach Möglichkeit darauf zurückgreifen. Die beste Möglichkeit zur Hilfestellung besteht sicher, wenn du ein Beispiel, anhanddessen das Problem erkennbar ist, zur Verfügung stellen kannst.
Grüße,
Harald
|
|
|
Gast |
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
Verfasst am: 30.07.2011, 17:49
Titel:
|
|
Danke der Tipp "DiffMinChange" ist Gold wert.
|
|
|
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
| RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|