WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

FMINSEARCH - BFGS oder Nelder Mead

 

neuner9
Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 19.03.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 19.03.2009, 12:19     Titel: FMINSEARCH - BFGS oder Nelder Mead
  Antworten mit Zitat      
Ich benutze die Funktion fminsearch, um lokale Minima einer mehrdimensionalen nichtlinearen Funktion zu finden. Ich hatte aber immer wieder die Meldung “maximum number of iterations has been exceeded” sprich, es wurde kein Minimum gefunden. Ein Kollege hat uns darauf aufmerksam gemacht, dass fminsearch eventuell den Algorithmus nach BFGS benutzt und daher „hängen“ bleibt. Ein Algorithmus nach Nelder Mead wäre besser…

Ich habe nun im Help bzw. im Internet keine genauen Infos gefunden, welchen Algorithmus fminsearch wirklich verwendet bzw. ob es eine „bessere“ Funktion gibt, die das gewünschte Minimum findet.

Habt ihr da einen Tipp?

Vielen Dank.

neuner9
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden


derOli
Forum-Meister

Forum-Meister


Beiträge: 579
Anmeldedatum: 19.03.08
Wohnort: Leipzig
Version: 2010a
     Beitrag Verfasst am: 19.03.2009, 12:32     Titel:
  Antworten mit Zitat      
In der Hilfe zu dem Befehl steht diese Referenz:


[1] Lagarias, J.C., J. A. Reeds, M. H. Wright, and P. E. Wright, "Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions," SIAM Journal of Optimization, Vol. 9 Number 1, pp. 112-147, 1998.

Hier habe ich diese gefunden: http://www.aoe.vt.edu/~cliff/aoe5244/nelder_mead_2.pdf

Also anscheinend benutzt matlab schon den nelder mead algorithmus.

Mehr weiß ich darüber auch nicht, ich weiß ja nicht was deine Aufgabe ist, aber ich habe auch mal einen Minimum Algorithmus geschrieben, allerdings ist der sehr einfach und sucht alle Samples ab.

Viele Grüße,

der Oli

Zuletzt bearbeitet von derOli am 19.03.2009, 12:58, insgesamt einmal bearbeitet
Private Nachricht senden Benutzer-Profile anzeigen
 
Bijick
Ehrenmitglied

Ehrenmitglied



Beiträge: 914
Anmeldedatum: 18.06.07
Wohnort: Nürnberg
Version: R2006b, R2008b
     Beitrag Verfasst am: 19.03.2009, 12:34     Titel:
  Antworten mit Zitat      
Hallo neuner9,

fminsearch verwendet den Nelder-Mead-Simplex-Algorithmus. BFGS wird von fminunc in der Optimization Toolbox verwendet.

Die Fehlermeldung besagt nur, dass die Optimierung mit der Standard-Anzahl von Iterationsschritten nicht auskommt. Du kannst also in einem ersten Schritt die Anzahl erhöhen. Das geht so:

Code:
[x,fval] = fminsearch(fun,x0, optimset('MaxIter',5000));


Herzliche Grüße
Bijick
_________________

>> why
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
neuner9
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 19.03.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 19.03.2009, 13:15     Titel: THX
  Antworten mit Zitat      
Hi ihr beiden

Vielen Dank für eure raschen Antworten. Möchte mich zuerst entschuldigen, dass ich die Anrede vergessen habe.

Die Standardanzahl von Iterationsschritten haben wir bereits mehrmals nach oben geschraubt - leider auch erfolglos. Tut mir Leid, dass ich das vorher nicht erwähnt hatte.

Habt ihr sonst noch einen Tipp?

Besten Dank again.

Hear you neuner9
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
Bijick
Ehrenmitglied

Ehrenmitglied



Beiträge: 914
Anmeldedatum: 18.06.07
Wohnort: Nürnberg
Version: R2006b, R2008b
     Beitrag Verfasst am: 19.03.2009, 13:42     Titel:
  Antworten mit Zitat      
Hallo neuner9,

für weitere Tipps bräuchte ich mehr Informationen. Hast Du die Optimization Toolbox zur Verfügung? Dann probier doch einfach mal fminunc.

Sonst müssen wir bei der Zielfunktion ansetzen. Ist die vielleicht verrauscht? Woher kommt genau die Nichtlinearität? Wieviele Optimierungsvariablen hast Du? Könnte man die eventuell reduzieren, um wenigstens einen Überblick zu bekommen? Verschiedene Startpunkte habt Ihr sicher schon probiert. Achtung: Der Ursprung ist bei diesem Verfahren denkbar ungünstig.

Herzliche Grüße
Bijick

P.S. Ich sehe gerade erst das "Meat" im Titel. Darf ich das ändern, bitte?
_________________

>> why
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
neuner9
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 19.03.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 19.03.2009, 13:59     Titel: Antworten
  Antworten mit Zitat      
Hi again

Hier unsere weiteren Infos betreffend deiner Rückfragen:

1. Toolbox haben wir
2. Wir machen Prognosen mit dem Kalman-Filter für ökonomische Zeitreihen
3. zu Zeit ist das Ganze noch univariat
4. Anzahl zu optimierende Variable zu Zeit deren 2, wird aber bei multivariaten Reihen ansteigen
5. zu optimierende Funktion likelihood
6. die zu optimierende Funktion ist verrauscht
7. Meat ist zwingend zu ändern :-) THX

THX.

Gruss neuner9
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
Bijick
Ehrenmitglied

Ehrenmitglied



Beiträge: 914
Anmeldedatum: 18.06.07
Wohnort: Nürnberg
Version: R2006b, R2008b
     Beitrag Verfasst am: 19.03.2009, 14:42     Titel:
  Antworten mit Zitat      
Hallo neuner9,

bei zwei Variablen sollte es eigentlich keine Probleme mit fminsearch geben.

Eine Frage hab ich noch: Wie ist denn der Optimierungsverlauf, also was wird als "Procedure" angegeben bei optimset('Display','iter')?

1. Wenn noch oft "reflect" vorkommt, dauert es bei Eurem Problem einfach so lang, bzw. der Startwert ist weit vom Minimum entfernt.

2. Wenn schon oft "contract inside" oder "contract outside" vorkommt, dann ist das Abbruchkriterium im Verhältnis zum Rauschen vielleicht zu groß.

Herzliche Grüße
Bijick
_________________

>> why
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
neuner9
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 19.03.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 20.03.2009, 17:10     Titel: Frage zu Procedure
  Antworten mit Zitat      
Hi Bijick

Danke für deine Tipps. Haben nun teilweise bessere Werte erreicht, da wir nicht dem MaxFunEvals herumgeschraubt hatten. Hatten dies verwechselt :-( Nun, nur so lernt man...

Noch eine Frage zu dem Inhalt von Procedure:
Was genau bedeuten die Begriffe reflect, shrink, contract outside bzw. contract inside?

Kann man die irgendwie zählen lassen, sprich eine Statistik machen und daraus schliessen, ob die eventuell gefundene Lösung Sinn macht?

Anschlussfrage, wann genau wäre dann eine Lösung sinnvoll bzw. eben nicht?

Hast du da eine Idee?

Besten Dank.

Have a nice weekend!

neuner9
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
Bijick
Ehrenmitglied

Ehrenmitglied



Beiträge: 914
Anmeldedatum: 18.06.07
Wohnort: Nürnberg
Version: R2006b, R2008b
     Beitrag Verfasst am: 20.03.2009, 17:55     Titel:
  Antworten mit Zitat      
Hallo neuner9,

die Angaben zur "procedure" hängen ganz eng mit dem Algorithmus zusammen. Der funktioniert so:

Im R^n (n=Anzahl der Variablen) werden n+1 Punkte erzeugt (abhängig vom Startwert), die einen Simplex bilden. Im R^2 also ein Dreieck, im R^3 eine Pyramide, usw. Bleiben wir mal beim Dreieck. Dann wird in jedem Schritt

1. der schlechteste der drei Punkte (also mit dem höchsten Funktionswert) ausgewählt und
2. an der gegenüberliegenden Seite gespiegelt ("reflect").
3. Jetzt wird der Funktionswert an der neuen Stelle mit den drei vorherigen Funktionswerten verglichen.

Je nach der exakten Verbesserung wird der Punkt noch weiter in die gleiche Richtung hinausgeschoben ("expand"), weniger weit "gespiegelt" ("contract outside") oder wieder halb zurückgespiegelt ("contract inside") und der neue Wert wieder mit den vorherigen verglichen. Der beste der neuen Punkte wird ausgewählt und bildet mit den zwei besseren Punkten des alten Dreiecks ein neues Dreieck. Sind alle Punkte schlechter als der alte, so wird der ganze Simplex zusammengezogen, um das "Modell" zu verbessern. Dann geht es weiter mit Schritt 1.

reflect und expand bewirken dabei, dass das Dreieck durch den Raum "wandert", eben in Richtung des Minimums. contract inside bewirkt, dass sich das Dreieck zusammenzieht, also sich von außen dem Minimum nähert. Bei contract outside passiert beides gleichzeitig. Der Algorithmus meldet Erfolg, wenn sich das Dreieck genügend zusammengezogen hat, so dass jeder Punkt innerhalb als Minimum gelten kann. shrink ist die einzig schlechte Meldung. Wenn nur geschrumpft wird, ist das "Tal" der Funktionswerte sehr schmal, in fast alle Richtungen geht es also aufwärts. In diesem Fall wäre fminunc vorzuziehen, da dort die Suchrichtung aufgrund von Ableitungsinformationen berechnet wird.

Eine Statistik ist nicht so sinnvoll, weil es auch auf den Verlauf ankommt. Am Anfang möchte man große Schritte ("expand"), am Ende eine schnelle Kontraktion.

Wann eine Lösung "sinnvoll" ist, ist nicht so leicht zu sagen. In meinen Ingenieur-Anwendungen reicht "besser als der Startwert" meist aus. In meinen mathematischen Problemen brauche ich dagegen das globale Minimum oder wenigstens eine Stelle mit verschwindendem Gradienten. Dafür nehme ich dann andere Verfahren als fminsearch, zumindest für die Postoptimierung. Ich hoffe, diese Nichtantwort hilft Euch trotzdem weiter.

Herzliche Grüße
Bijick
_________________

>> why
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
neuner9
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 19.03.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 25.03.2009, 08:47     Titel: THX
  Antworten mit Zitat      
Hi Bijick

In der Hitze des Gefechts habe ich es ganz versäumt dir für deine äusserst ausführliche Antwort zu danken. Bitte entschuldige das Versehen...

Gruss neuner9
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

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 | goMatlab RSS Button 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.