Algorithmische und Diskrete Mathematik | Fakultät für Mathematik

Optimierung (für Nichtmathematiker)

Wintersemester 09/10

Vorlesung: C. Helmberg,
Übung: A. Lau

Vorlesung:	Mo 11:30 - 13:00, Raum 2/N102 Vorlesungsbeginn am 12.10.2009
Übung:	Mo 9:15 - 10:45, Raum 2/39/738 Übungsbeginn am 12.10.2009
Nächste Konsultation:	1.2.2010, 7.30 Uhr, Raum 2/39/733

Wichtig:

Für die Übungen benötigen Sie zusätzlich zum URZ-Login ein MRZ-Login. Schreiben Sie zum Erhalt eines Logins bitte eine eMail an
mrz@mathematik.tu-chemnitz.de
mit Angabe von Name, Vorname, URZ-Login und Verweis auf diese Veranstaltung.

Kurzbeschreibung

Inhalt:	Einordnung von Optimierungsproblemen; Optimalitätsbdingungen für freie und restringierte Optimierungsaufgaben; Newton-, Line-Search-, Trustregion-Verfahren; Lineare Optimierung: Dualität, Simplex- und Innere-Punkteverfahren; Ganzzahlige Optimierung und Heuristiken; Ableitungsfreie Optimierung
Zielgruppe:	Masterstudiengänge der Ingenieur- und Wirtschaftswissenschaften
Vorwissen:	Lineare Algebra, Differentialrechnung im R^n
Prüfung:	mündlich (Modulprüfung oder Schein mit Note)

Literatur

Optimierung allgemein:

Florian Jarre, Josef Stoer; Optimierung, Springer, 2004. ISBN 3-540-43575-1.
Carl Geiger, Christian Kanzow; Theorie und Numerik restringierter Optimierungsaufgaben, Springer, 2002. ISBN 3-540-42790-2.

Lineare Optimierung:

Robert J. Vanderbei; Linear Programming and Extensions, Kluwer Academic Publishers, Boston, 1996. ISBN 0-7923-9804-1.

Ganzzahlige Optimierung:

Alexander Schrijver; Theory of Linear and Integer Programming; Wiley 1986. ISBN 0-471-98232-6.

Konvexe Analysis und konvexe Optimierung:

Jean-Baptiste Hiriart-Urruty und Claude Lemaréchal; Convex Analysis and Minimization I, II; Springer, Berlin, 2. Auflage 1996. ISBN 3-540-56860-6 (Band I) und 3-540-56852-2 (Band II).

Nichtlineare Optimierung:

J. Nocedal, S.J. Wright; Numerical Optimization, Springer, 1999.
J. Frederic Bonnans, J. Charles Gilbert, Claude Lemarechal, Claudia A. Sagastizabal; Numerical Optimization, Springer, 2003. ISBN 3-540-00191-3.
Bazaraa, Sherali, Shetty; Nonlinear Programming: Theory and Algorithms, Wiley, 1993;
Luenberger; Linear and Nonlinear Programming, Addison-Wesley,1984.

Wiederholung: Zur Auffrischung des Grundlagenwissens ist beispielsweise

B. Luderer, U. Würker: Einstieg in die Wirtschaftsmathematik, 2003.

geeignet.

Vorlesungen

Das Gesamtdokument aller Präsentationen mit Seitennummern und Gliederung umfasst über 1000 Seiten und sollte daher nicht ausgedruckt werden.

Übungen

Übung 1, Dateien zur Übung: uebung1.zip
Übung 2, Dateien zur Übung: uebung2.zip, Lösung: sol_uebung2.zip
Übung 3, Dateien zur Übung: uebung3.zip, Simplex: Simplex
Übung 4, Rucksackproblem: rucksack_alles.m
Übung 5
Übung 6, Second-Order-Cone: secorder2.m, secorder3.m
Übung 7
Übung 8, quadplot.m, mynewton.m, myshowfun.m, funcos.m, rosenbrock.m, test_rosenbrock.m
Übung 9
Übung 10
Übung 11
Übung 12

Konsultationen

Simplex-Algorithmus: Vergleich

AMPL und NEOS Server

AMPL ist eine Modellierungssprache für Optimierungsprobleme. Eine Reihe von Lösern für Optimierungsprobleme besitzen Interfaces für in AMPL modellierte Aufgaben. Eine freie Studentenversion von AMPL steht zum kostenlosen Download bereit. Diese ist zum Bearbeiten der Aufgaben nicht notwendig.

AMPL-Beispielfiles Kurzdokumentation in Inhalt.txt
AMPL-Buch von R. Fourer, D. Gay und B. Kernighan
Kapitel 1 des AMPL-Buches zum freien Download
Introduction to AMPL (A Tutorial) von P. Kaminsky, erweitert von D. Rajan

Der NEOS-Server nimmt Optimierungsprobleme über das Internet (u.a. Web-Interface) entgegen, leitet diese an einen geeigneten Löser weiter und gibt deren Ausgabe zurück. Die Aufgabe muss dazu in einer für den ausgewählten Löser geeigneten Modellierungssprache formuliert sein, z.B. in AMPL.

Außerdem findet sich auf den NEOS-Seiten ein Auflistung verschiedenster Optimierungssoftware sowie eine Übersicht über verschiedene Typen von Optimierungsaufgaben.