Professur Numerische Mathematik
(Partielle Differentialgleichungen)

Optimierung für Nichtmathematiker (2V, 2Ü)

Diese Vorlesung richtet sich an Studierende der Ingenieur- und Wirtschaftswissenschaften im Masterstudium sowie alle Interessierten. Empfehlenswert für die Teilnahme sind Grundkenntnisse in der linearen Algebra (Matrizen, Vektoren) sowie in der Differentialrechnung für Funktionen mehrerer Variabler (partielle Ableitung, Gradient). Bei der Auffrischung können Sie zum Beispiel auf die hier genannte Literatur zurückgreifen.

Inhalt

Die mathematische Optimierung beschäftigt sich mit der Aufgabe, eine Zielfunktion unter Einhaltung von Beschränkungen zu minimieren oder zu maximieren.

Einordnung von Optimierungsproblemen
Optimalitätsbedingungen für freie und beschränkte Optimierungsaufgaben
Newton-, Line-Search-, Trust-Region-Verfahren
Lineare Optimierung: Dualität, Simplex- und Innere-Punkteverfahren
Ganzzahlige Optimierung und Heuristiken
ableitungsfreie Optimierung

Weitere Informationen zu dieser Lehrveranstaltung finden Sie

Ziele der Lehrveranstaltung

Ziele der Lehrveranstaltung sind

selbstständige Modellierung und Formulierung von Optimierungsaufgaben
Einordnung von Optimierungsaufgaben (siehe auch NEOS Optimization Tree)
Auswahl geeigneter Lösungsverfahren (siehe auch NEOS Optimization Software Guide)
Erfahrungen in der Anwendung von Optimierungssoftware
eigenständige algorithmische Umsetzung einfacher Verfahren

Aktuelles

09.03.2011	Als weiterer Prüfungstermin wird der 08.04.11 angeboten.
20.10.2010	Es wurde begonnen, eine Liste mit typischen Prüfungsfragen zu erstellen.
20.10.2010	Die Vorlesung vom 03.11.2010 wird auf einen späteren Termin verschoben.
15.10.2010	Es wurde eine zweite Übungseinheit eingerichtet.
14.10.2010	Die Vorlesung wird ab sofort verlegt in Raum 2/HS3.
22.09.2010	Die Vorlesung beginnt am Mittwoch, den 13.10.2010.
22.09.2010	Die Übung beginnt ebenfalls am Mittwoch, den 13.10.2010.
28.07.2010	Die Vorlesung und Übung entfällt am Mittwoch, den 17.11.2010 wegen des Buß- und Bettages.

Termine

Vorlesung	Mittwoch	15:30 - 17:00 (5. LE)	2/HS3	Roland Herzog	Sprechzeit: Mittwoch, 13:00 - 14:00 und nach Vereinbarung
Übung	Mittwoch	11:30 - 13:00 (3. LE)	2/39/738	Frank Schmidt	Sprechzeit: Mittwoch, 09:15 - 10:45 und nach Vereinbarung
Übung	Mittwoch	13:45 - 15:15 (4. LE)	2/39/738	Frank Schmidt	Sprechzeit: Mittwoch, 09:15 - 10:45 und nach Vereinbarung

Vorlesung

Material zur Vorlesung

Folien zur Vorlesung 1 (13.10.2010)
- Problemstellung und Grundbegriffe
Beiblatt Einführende Beispiele
Notizen zur Vorlesung 1
Folien zur Vorlesung 2 (20.10.2010), nachträglich leicht gekürzt
- Klassifikation von Optimierungsaufgaben
- Einführung in die freie Optimierung
- Orakel und Modellfunktionen
Folien zur Vorlesung 3 (27.10.2010)
- Optimalitätsbedingungen der freien Optimierung
- Das Newton-Verfahren in der freien Optimierung
Folien zur Vorlesung 4 (10.11.2010)
- Line-Search-Verfahren
- Gradienten-Verfahren und Skalierung
- Quasi-Newton-Verfahren
Folien zur Vorlesung 5 (24.11.2010)
- Trust-Region-Verfahren
- CG-Verfahren
- Inexakte Newton-Verfahren
Folien zur Vorlesung 6 (01.12.2010)
- Nichtlineare kleinste Quadrate
- Gauß-Newton-Verfahren
- Numerisches Differenzieren
Folien zur Vorlesung 7 (08.12.2010)
- Algorithmisches Differenzieren (siehe auch www.autodiff.org sowie die Webseiten der Tools Tapenade und ADOL-C)
- Ableitungsfreie Verfahren / Direkte Suchverfahren
- Das Simplex-Verfahren von Nelder und Mead
- Das Kriging-Verfahren (wurde nicht besprochen)
Folien zur Vorlesung 8 (15.12.2010)
- Aufgabenstellung der restringierten Optimierung
- Tangentialkegel
- Notwendige Optimalitätsbedingungen
- KKT-Bedingungen
Folien zur Vorlesung 9 (05.01.2011)
- Strafverfahren
- Barriere-Verfahren
- SQP-Verfahren (wird am 12.01.2011 zu Ende besprochen)
Folien zur Vorlesung 10 (12.01.2011)
- Anwendung der restringierten Optimierung: Optimale Steuerung
Folien zur Vorlesung 11 (19.01.2011)
- Lineare Optimierung
- Der Simplex-Algorithmus (wird am 26.01.2011 zu Ende besprochen)
- Das Heiratsproblem (wird am 26.01.2011 zu Ende besprochen)
Folien zur Vorlesung 12 (26.01.2011)
- Ganzzahligkeit von Polyedern
- Netzwerkflüsse (wird am 02.02. zu Ende besprochen)
Folien zur Vorlesung 13 (02.02.2011)
- Mehrgüterflüsse

Die Folien zur Vorlesung wurden ursprünglich im WS2009/10 von Prof. Dr. Christoph Helmberg ausgearbeitet und werden im Rahmen dieser Lehrveranstaltung überarbeitet.

Ergänzende 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:

Stephen Boyd and Lieven Vandenberghe: Convex Optimization, Cambridge 2004, reprinted 2007, ISBN 0521833787
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

Verfahren der konjugierten Gradienten (CG-Verfahren):

An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (J. Shewchuk)

Übung

Übungen

Die Übungen finden in Gruppenarbeit am Rechner statt. Für die Übungen benötigen Sie zusätzlich zum URZ-Login ein Login vom mathematischen Rechenzentrum (MRZ). Schreiben Sie zum Erhalt eines Logins bitte eine E-Mail an mrz@mathematik.tu-chemnitz.de mit Angabe von Name, Vorname, Ihrem URZ-Login und Verweis auf diese Veranstaltung.

Material zur Übung

Übung	Material zur Übung
1. Übungsblatt	Aufgabe 1: commands1.m Aufgabe 2: commands2.m Aufgabe 3: potmat.m matmult.m binomialkoeff.m
2. Übungsblatt	Aufgabe 6: mypoly.m solution_A6.m Aufgabe 7: solution_A7.m
3. Übungsblatt	Aufgabe 8: rosenbrock.m plot_rosenbrock.m
4. Übungsblatt	Aufgabe 13: least_squares.m Aufgabe 14: himmelblau.m mycos.m newton.m solution_A14.m
5. Übungsblatt	Aufgabe 17: rosenbrockn.m solution_A17.m
6. Übungsblatt	Aufgabe 19: solution_A19.m
7. Übungsblatt	Aufgabe 20: solution_A20.m
8. Übungsblatt	Aufgabe 21: Beispiel_AD.c Beispiel_AD_Aufgabe_b.c readme Aufgabe 22: solution_A22.m Aufgabe 23: solution_A23.m outfun.m myinterp2.m pert_himmelblau.m
9. Übungsblatt	Aufgabe 24: solution_A24.m constraints.m f.m Aufgabe 25: solution_A25.m A247_f.m constraints1.m constraints2.m constraints3.m
10. Übungsblatt
11. Übungsblatt	Aufgabe 28: simplex_phaseI.m simplex.m
12. Übungsblatt	Aufgabe 29: solution_A29.m Aufgabe 30: solution_A30.m

Matlab-Einführungen

Es wird empfohlen, dass Sie sich mit den Grundlagen von Matlab vertraut machen (nicht nur für diese Lehrveranstaltung). Material dazu finden Sie hier.

Prüfung

Zum Abschluss dieser Lehrveranstaltung findet eine 30minütige mündliche Prüfung über den Inhalt von Vorlesung und Übung statt. Bei der Vorbereitung kann Ihnen eine Liste typischer Prüfungsfragen helfen, die während der Vorlesung ständig ergänzt wird.

Als Prüfungstage sind 09.02.11, 17.02.11, 08.03.11 und 09.03.11 vorgesehen. Termine werden ab sofort über das Sekretariat (Anne-Kristin Glanzberg, Reichenhainer Str. 41, Zimmer 615) vergeben.

Als weiterer Prüfungstermin (hauptsächlich für Wiederholer) wird der 08.04.11 angeboten. Termine werden wieder über das Sekretariat (Anne-Kristin Glanzberg, Reichenhainer Str. 41, Zimmer 615) vergeben.