-> TU München
 
 
-> Zentrum Mathematik
 
-> Homepage der Vorlesung
 
MATLAB-Routinen und Beispiele
 
 Installation

Das tar-Archiv opt3.tar bzw. das zip-Archiv opt3.zip enthält alle nachstehend beschriebenen MATLAB-Routinen und Beispiele, eine kurze Beschreibung der Beispiele sowie die benötigten Hilfsroutinen. Die Archive können durch

tar xvf opt3.tar        bzw.        unzip opt3.zip

entpackt werden. Die Dateien werden im Unterverzeichnis opt3 des aktuellen Verzeichnisses abgelegt.

Alle Beispiele können aus MATLAB heraus durch Aufruf der entsprechenden m-Datei gestartet werden. Hilfe für eine Routine foo.m erhält man unter MATLAB durch Eingabe von help foo.

 Optimierungs-Algorithmen für MATLAB

Robuste Newton-Verfahren
  • newt.m
    Robustes Newton-Verfahren mit Armijo-Goldstein Schrittweitenregel.
    Liegt die Hessematrix im Sparse-Format vor, so wird eine Faktorisierung im Sparse-Format durchgeführt.
  • newtg.m
    Graphische Version von newt.m, die die Iterierten in der x1-x2-Ebene zeichnet. Wird zuvor ein Höhenlinien-Plot der Zielfunktion angelegt, so kann der Optimierungspfad visualisiert werden (siehe z.B. runrosenNg.m).
  • pcgnewt.m
    PCG-Newton-Verfahren mit Armijo-Goldstein Schrittweitenregel.
    Die Newton-Gleichung wird inexakt mit Hilfe des vorkonditionierten CG-Verfahrens mypcg.m gelöst. Der Vorkonditionierer kann vom Benutzer bereitgestellt werden.
    Verfügbare Vorkonditionierer: cholincprec.m (unvollständige Cholesky Zerlegung) ssorprec.m und (SSOR).
(P)CG-Verfahren
  • cg.m
    CG-Verfahren. Das Verfahren bricht ab, falls das relative Residuum die übergeben Toleranz unterschreitet oder eine Richtung nichtpositiver Krümmung auftritt.
  • cgg.m
    Graphische Version von cg.m, siehe newtg.m.
  • mypcg.m
    Vorkonditioniertes CG-Verfahren, sonst wie cg.m. In der Regel ist mypcg.m schneller als die MATLAB-Routine pcg.m.
    Der Vorkonditionierer kann vom Benutzer bereitgestellt werden.
    Verfügbare Vorkonditionierer: cholincprec.m (unvollständige Cholesky Zerlegung) und ssorprec.m (SSOR).
Trust-Region Verfahren
  • tr.m
    Trust-Region Verfahren, das mit exakter Hessematrix arbeitet. Durch ein Flag kann angegeben werden, ob die Trust-Region Probleme exakt unter Verwendung von solvetr.m oder durch ein Steihaug-CG-Verfahren solvetrcg.m gelöst werden soll.
  • trg.m
    Graphische Version von tr.m, die die Iterierten in der x1-x2-Ebene zeichnet. Wird zuvor ein Höhenlinien-Plot der Zielfunktion angelegt, so kann der Optimierungspfad visualisiert werden (siehe z.B. runrosenTRg.m).
  • solvetr.m
    Berechnet die exakte Lösung eines Trust-Region Problems für einen Trust-Region Radius, der in einer vorgegebenen Umgebung des tatsächlichen Trust-Region Radius liegt.
  • solvetrcg.m
    Steihaug-CG-Verfahren zur näherungsweisen Lösung eines Trust-Region Problems.
Variable-Metrik Verfahren
  • BFGS.m
    BFGS-Verfahren mit Powell-Wolfe Schrittweitenregel.
  • BFGSg.m
    Graphische Version von BFGS.m, die die Iterierten in der x1-x2-Ebene zeichnet. Wird zuvor ein Höhenlinien-Plot der Zielfunktion angelegt, so kann der Optimierungspfad visualisiert werden (siehe z.B. runrosenBFGSg.m).
  • LBFGS.m
    Limited-Memory BFGS-Verfahren mit Powell-Wolfe Schrittweitenregel. Implementierung des BFGS-Verfahrens für große Probleme: Es werden maximal die letzten lmax Rang-2-Updates der BFGS-Matrix kompakt gespeichert (Speicherung der darstellenden 2*lmax Vektoren). Daraus kann die Multiplikation der LBFGS-Matrix mit einem Vektor berechnet werden, ohne die Matrix aufzustellen.
Gradienten-Verfahren
  • grad.m
    Gradienten-Verfahren mit Armijo-Goldstein oder Powell-Wolfe Schrittweitenregel.
  • gradg.m
    Graphische Version von grad.m, siehe newtg.m.
 Beispiele

Vergleich von Gradienten-, robusten Newton- und BFGS-Verfahren
  • runquadGg.m (siehe Beispiel 1 in optbsp.pdf)
    Minimierung der quadratischen Funktion Fquad.m mit dem Gradienten-Verfahren gradg.m. Höhenlinien und Optimierungspfad werden graphisch dargestellt. Obwohl die Kondition cond(H)=20 der Hessematrix moderat ist, konvergiert das Gradientenverfahren langsam.
  • runquadCGg.m
    Wie runquadGg.m, jedoch wird das CG-Verfahren cgg.m. verwendet (Konvergenz nach 2 Iterationen).
  • runrosenGg.m (siehe Beispiel 2 in optbsp.pdf)
    Minimierung der Rosenbrock-Funktion Frosenbrock.m mit dem Gradienten-Verfahren gradg.m. Höhenlinien und Optimierungspfad werden graphisch dargestellt. Das Gradientenverfahren konvergiert sehr langsam.
  • runrosenNg.m
    Wie runrosenGg.m, jedoch wird das Newton-Verfahren newtg.m. verwendet.
  • runrosenTRg.m
    Wie runrosenGg.m, jedoch wird das Trust-Region Verfahren trg.m. mit exakter Lösung der Trust-Region Probleme durch solvetr.m verwendet.
  • runrosenTRCGg.m
    Wie runrosenGg.m, jedoch wird das Trust-Region Verfahren trg.m. mit inexakter Lösung der Trust-Region Probleme durch das Steihaug-CG-Verfahren solvetrcg.m verwendet.
  • runrosenBFGSg.m
    Wie runrosenGg.m, jedoch wird das BFGS-Verfahren BFGSg.m. verwendet.

Berechnung von Minimalflächen
  • runminsurfN.m (siehe Beispiel 3 in optbsp.pdf)
    Berechnung einer Minimalfläche über einem Rechteck zu vorgegebenen Randdaten mit Hilfe des Newton-Verfahrens newt.m. Zur Diskretisierung werden lineare finite Elemente auf einer gleichmäßigen Triangulation verwendet. Die Berechnung von Fläche, Gradient und Hessematrix (natürlich sparse) erfolgt in Fminsurf.m.
  • runminsurfNPCG.m
    Wie runminsurfN.m, jedoch wird das PCG-Newton-Verfahren pcgnewt.m. mit Vorkonditionierer cholincprec.m. verwendet.
  • runminsurfTR.m
    Wie runminsurfN.m, jedoch wird das Trust-Region Verfahren tr.m. mit exakter Lösung der Trust-Region Probleme durch solvetr.m verwendet.
  • runminsurfTRCG.m
    Wie runminsurfN.m, jedoch wird das Trust-Region Verfahren tr.m. mit inexakter Lösung der Trust-Region Probleme durch das Steihaug-CG-Verfahren solvetrcg.m verwendet.
  • runminsurfLBFGS.m
    Wie runminsurfN.m, jedoch wird das LBFGS-Verfahren LBFGS.m. verwendet.
  • runminsurfMLN.m, runminsurfMLNPCG.m
    Wie runminsurfN.m und runminsurfNPCG.m, jedoch wird zunächst auf einem groben Gitter minimiert, dann auf einem feineren Gitter mit der interpolierten Grobgitterlösung als Startpunkt usw.

Lösung des Brachistochronen-Problems (Achterbahn-Problem)
  • runbrachiN.m (siehe Beispiel 4 in optbsp.pdf)
    Berechnet mit Hilfe des Newton-Verfahrens newt.m. zwischen zwei gegeben Punkten A,B diejenige Kurve k, auf der ein Massepunkt im Gravitationsfeld mit Geschwindigkeit v im Startpunkt A den Punkt B in minimaler Zeit erreicht. Zur Diskretisierung werden finite Differenzen auf einem gleichmäßigen Gitter verwendet. Die Berechnung von Fahrzeit, Gradient und Hessematrix (natürlich sparse) erfolgt in Fbr.m.
  • runbrachiG.m
    Wie runbrachiN.m, jedoch mit dem Gradienten-Verfahren grad.m. (sehr langsame Konvergenz!).


Dr. Stefan Ulbrich | 18.07.02
   Zugriffstatistik