|
|
|
Klassifizierung Trust-Region und Line-Search-Verfahren |
|
| anna |
Gast
|
 |
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 14.02.2008, 17:49
Titel: Klassifizierung Trust-Region und Line-Search-Verfahren
|
 |
| |
 |
 |
Hallo,
zwar bezieht sich meine Frage nicht direkt auf die Toolbox gehört aber in das Thema Optimierung. In der Hilfe von Matlab hab ich mich versucht, durch die verschiedenen Optimierungsverfahren zu kämpfen. Dabei bin ich ein wenig verwirrt worden durch die verschiedenen Möglichkeiten Optimierungsverfahren zu klassifizieren.
Zum Beispiel gibt es die Klassifizierung, ob das Verfahren den Gradienten benutzt:
gradientenfreie Verfahren: Simplex
gradientenbasierte Verfahren: Methode des steilsten Abstiegs, PCG-Verfahren, Quasi-Newton, Newton-Verfahren, SQP
Dann gibt es noch eine Klassifizierung, je nachdem, was für ein Optimierungsproblem es ist:
ohne Nebenbedingungen: Simplex, alle Abstiegsverfahren (Methode des steilsten Abstiegs, PCG,...) , Quasi-Newton, Newton
mit Nebenbedingungen: SQP
Bitte korrigiert mich, wenn ich die Einteilung falsch gemacht habe.
Jetzt meine Frage zur Einteilung in Line-Search-Verfahren und Trust-Region-Verfahren:
1. Was sind die Merkmale eines LS- und eines TR-Verfahrens?
2. Welche von den oben genannten Verfahren sind LS-Verfahren und welche TR-Verfahren bzw.
3. sind das etwa eigene Verfahren?
Ich hoffe, jemand nimmt sich meinem Problem an und kann mir kurz erläutern, was es mit LS- und TR-Verfahren auf sich hat.
|
|
|
|
|
|
| Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
|
Verfasst am: 15.02.2008, 10:39
Titel:
|
|
| |
|
|
Hallo anna,
schöne Frage.  Hier meine Überlegungen dazu:
1. In einem Line-Search-Optimierungsverfahren wird zunächst eine
Suchrichtung und dann eine Schrittweite entlang dieser Richtung (line) bestimmt (search). Bei einer Trust-Region-Methode wird die Zielfunktion durch eine Modellfunktion approximiert. Innerhalb eines Gebietes (Region) vertraut (trust) man auf die Güte dieser Approximation und legt dadurch eine maximale Schrittweite fest. Dann erst bestimmt man die beste Suchrichtung. Lesetipp: www.mathematik.uni-regensburg.de/Ma.....rlesung/Sem0607/blank.pdf
2. Soweit ich weiß, kann man fast jedes Optimierungsverfahren entweder als Line-Search oder als Trust-Region-Methode gestalten (jedenfalls wenn eine Modellfunktion verwendet wird). Jedenfalls trifft das auf die Newton- und Quasi-Newton-Verfahren zu. Manchmal werden die Methoden auch kombiniert, um in Spezialfällen die besten Ergebnisse zu bekommen. Daher kann man nicht die Verfahren einteilen, sondern nur die Algorithmen.
3. Nein.
Was nun Matlab und die Optimization Toolbox angeht, kann man recht eindeutig sagen, wann Trust-Region-Algorithmen zum Einsatz kommen, nämlich bei den Large-Scale-Problemen (also solche mit vielen Variablen und/oder vielen Nebenbedingungen. Line Search wird für fast alle Medium-Scale-Probleme verwendet. Manchmal kann man selbst die Auswahl treffen. Lesetipp: Matlab-Hilfe "Medium- and Large-Scale Algorithms"
Ich hoffe, das hilft erst mal weiter. Herzliche Grüße
Bijick
_________________
>> why
|
|
|
|
| anna |
Gast
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 16.02.2008, 01:06
Titel:
|
|
Hallo Bijick,
das waren echt super Antworten auf meine Fragen. Du hast mir sehr weitergeholfen!!
Vielen Dank.
anna
|
|
|
|
| anna |
Gast
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 16.02.2008, 01:28
Titel:
|
|
da fällt mir jetzt doch noch was ein, wo du gerad erläutert hast, was Large-Scale-Algorithmus und Medium-Scale-Algorithmus bedeutet. wenn ich fmincon bzw fminunc für mein optimierungsproblem benutze, kommen jeweils folgende Hinweise:
bei fminunc:
Warning: Gradient must be provided for trust-region method;
using line-search method instead.
->Kann ein Trust-Region-Verfahren also nicht mit numerischen Gradienten durchgeführt werden!? Warum?
bei fmincon:
Warning: Large-scale (trust region) method does not currently solve this type of problem, switching to medium-scale (line search).
-> Ist hier auch auf medium-scale gewechselt worden wegen des fehlenden Gradienten oder weil mein Optimierungsproblem zu wenig Variablen hat?
|
|
|
|
| Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
|
Verfasst am: 18.02.2008, 11:10
Titel:
|
|
| |
|
|
Hallo anna,
bei deinen neuen Fragen verlasse ich etwas das sichere Terrain und spekuliere nur mal nach meinem Wissensstand.
1. Kann ein Trust-Region-Verfahren also nicht mit numerischen Gradienten durchgeführt werden!? Warum?
Ob ein Verfahren damit fertig wird, inexakte Werte zu verarbeiten, hängt am meisten vom Algorithmus und seiner Robustheit ab. Vermutlich ist der SQP-Algorithmus in Matlab besonders robust und verträgt numerische Gradienten. Ob man Trust-Region-Verfahren nie mit numerischen Gradienten machen kann, weiß ich schlicht nicht. Die Matlab-Programmierer glauben jedenfalls für ihren Algorithmus nicht an verwertbare Ergebnisse. Es könnte im Einzelfall natürlich trotzdem klappen, wenn deine Funktion gutmütig ist, aber das wissen die ja nicht.
Nachlesen in der Hilfe brachte noch folgende Überlegung: Innerhalb des Trust-Region-Algorithmus wird ein CG-Verfahren eingesetzt. Das könnte sensibler auf numerische Gradienten reagieren als SQP, weil ja hier außer dem Gradienten gar keine Informationen eingehen. Aber das ist nur Spekulation.
2. -> Ist hier auch auf medium-scale gewechselt worden wegen des fehlenden Gradienten oder weil mein Optimierungsproblem zu wenig Variablen hat?
Das Wechseln kann mehrere Gründe haben (siehe auch Hilfe zu fmincon): Das Large-Scale-Verfahren kommt für die Entwickler nur in Betracht, wenn
1. der Gradient angegeben wird
2. die Option 'GradObj' auf 'on' gesetzt ist (logisch)
3. und die Trust-Region entweder durch untere und obere Schranken oder durch Gleichheitsrestriktionen (mehr Variable als Gleichungen) vorgegeben ist.
Interessanterweise gibt es keine Überprüfung, wieviele Variablen vorhanden sind. In der Hinsicht ist Large-Scale wohl Geschmackssache. Erwähnt wird noch, dass die Matrix Aeq bei Large-Scale-Problemen typischerweise dünnbesetzt ist. Die Bezeichnung ist jedenfalls erst ab 6x6 richtig sinnvoll. Abgebrochen würde aber anscheinend auch bei nur zwei Variablen nicht, wenn die anderen Kriterien erfüllt sind. 
Hab ich also auch mal wieder was gelernt.
Herzliche Grüße
Bijick[/b]
_________________
>> why
|
|
|
|
| anna |
Gast
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 21.02.2008, 15:22
Titel:
|
|
hallo bijick,
ich danke dir für deine stets umfangreichen, informativen antworten. dieses forum bringt einem wirklich was.
lg, anna
|
|
|
|
|
|
|
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.
|
|
