Professur Numerische Mathematik
(Partielle Differentialgleichungen)

Grundlagen der Optimierung (Optimierung I) (4V, 2Ü)

Aufbauend auf dieser Vorlesung findet im SS2010 ein Seminar Optimierung statt. Vorbesprechung und Themenvergabe direkt im Anschluss (ca. 16:30 Uhr) an o.g. Konsultation.

Inhalt

In dieser Veranstaltung werden die Grundlagen der mathematischen Optimierung dargestellt. Insbesondere werden Optimalitätsbedingungen für wichtige Problemklassen besprochen und erste Algorithmen zu deren Lösung angegeben.

Formulierung und Klassifikation beschränkter und unbeschränkter Optimierungsaufgaben
unbeschränkte Optimierungsaufgaben
konvexe Optimierungsaufgaben
lineare Optimierungsaufgaben
glatte nichtlineare Optimierungsaufgaben

Im kommentierten Vorlesungsverzeichnis finden sich noch weitere Informationen.

Vorkenntnisse

Laut Modulbeschreibung werden Kenntnisse in Analysis und linearer Algebra vorausgesetzt. Diese umfassen insbesondere: Umgebung eines Punktes im Rⁿ, offene, abgeschlossene und kompakte Mengen im Rⁿ, Supremum und Infimum einer Menge, Konvergenz und Häufungspunkte von Folgen und Teilfolgen im Rⁿ, Stetigkeit, Lipschitz-Stetigkeit und Ableitungen von Funktionen f:Rⁿ→R (Richtungsableitung, Gradient, Hessematrix), Satz von Taylor für Funktionen f:Rⁿ→R, Stetigkeit, Lipschitz-Stetigkeit und Ableitung von Funktionen f:Rⁿ→R^m (Jacobimatrix), Kettenregel, Hauptsatz der Differential- und Integralrechnung, Satz über implizite Funktionen, Skalarprodukt, Hyperebene, Cauchy-Schwarz-Ungleichung, Dreiecksungleichung, Vektornormen, Matrixnormen, lineare Gleichungssysteme, Rechnen mit Matrizen und Vektoren, Rang und Invertierbarkeit (Regularität) einer Matrix, Eigenwerte, positive Definitheit

Termine

Konsultation	Donnerstag, 18.02.10	15:30 - 17:00	2/B202	Frank Schmidt
Konsultation	Freitag, 19.02.10	13:45 - 15:15	2/B202	Gerd Wachsmuth

Vorlesung	Mittwoch	11:15 - 12:45	2/B201	Roland Herzog	Sprechzeit: Dienstag 12:30 - 13:30 Uhr und nach Vereinbarung
Vorlesung	Freitag	13:45 - 15:15	2/N001	Roland Herzog
Übung	Dienstag	15:30 - 17:00	2/SR100D	Frank Schmidt	Sprechzeit: Dienstag 09:15 - 10:45 Uhr und nach Vereinbarung
Übung	Mittwoch	15:30 - 17:00	2/N001	Gerd Wachsmuth	Sprechzeit: Donnerstag 9:15 - 10:45 Uhr und nach Vereinbarung

Material zur Vorlesung

Beiblatt: Einführende Beispiele (Beispiele 1.2-1.5) (14.10.2009)
Beiblatt: Konvergenzverhalten des Gradientenverfahrens (Satz 6.4) (28.10.2009)
Beiblatt: Globalisiertes Newtonverfahren in der Optimierung (Algorithmus 7.10-Bemerkung 7.14) (06.11.2009)
Beiblatt: Mozartproblem (Beispiel 8.1) (06.11.2009)
Beiblatt: Simplex-Algorithmus (Algorithmus 9.6) (25.11.2009)
Beiblatt: Barriere-Problem (Gleichung (12.5)) (04.12.2009)
Beiblatt: Innere-Punkte-Verfahren (Algorithmus 12.9) (09.12.2009)
Beiblatt: Subgradientenverfahren (§18) (20.01.2010)

Übungen

Die Hausaufgaben sind in 2-3er-Gruppen zu bearbeiten. Die Abgabe erfolgt jeweils am Freitag zu Beginn der Vorlesung.

Übung	Material zur Übung
Einführung in Matlab
0. Übungsblatt	Aufgabe 1: Plot_Himmelblau.m
1. Übungsblatt	Aufgabe 1: engine.mod engine1.dat engine2.dat engine3.dat engine.cmd Aufgabe 2: table.mod table.dat table.cmd Aufgabe 3: competition.mod competition.dat competition.cmd Aufgabe 7: cargo.mod cargo.cmd
2. Übungsblatt (letzte Änderung am 16.10.09, 13Uhr)
3. Übungsblatt (Hinweis: Der MINTO-Solver scheint derzeit nicht zu funktionieren)	Aufgabe 1: knapsack.cmd knapsack.mod knapsack.dat Aufgabe 7: rosenbrock.m uebung03.m ls_armijo.m ls_testfun.m myplot.m
4. Übungsblatt (Abgabe schon am Mittwoch (04.11.))	Aufgabe 4: uebung04.m steepest_descent.m cosinus.m himmelblau.m general_quadratic_function.m Aufgabe 5: sudoku.cmd sudoku.mod sudoku1.dat sudoku2.dat
5. Übungsblatt	Aufgabe 5: newton_method.m uebung05.m
6. Übungsblatt	Aufgabe 6: mat_mult.m
7. Übungsblatt	Aufgabe 2: simplex.m uebung07.m Aufgabe 4: currencies.m
8. Übungsblatt	Aufgabe 2: simplex_feasible_base.m uebung08.m Aufgabe 5: klee_minty.m
9. Übungsblatt
10. Übungsblatt	Aufgabe 1: uebung10.m innere_punkte.m klee_minty_func.m simplex_no_debug.m
11. Übungsblatt
12. Übungsblatt
13. Übungsblatt
14. Übungsblatt (letzte Änderung am 25.01.10, 12Uhr)	Aufgabe 1: wolfe.m subgradient.m uebung14.m
15. Übungsblatt

Prüfung

Über den Inhalt von Vorlesung und Übung kann im Anschluss an die Lehrveranstaltung eine mündliche Prüfung abgelegt werden. (Bei der Vorbereitung kann Ihnen eine Liste möglicher Prüfungsfragen helfen.) Alternativ kann ein Schein mit Note oder ein Schein ohne Note erworben werden.

Schein mit Note: mündliches Prüfungsgespräch (ohne Beweise), Hausaufgabenpunkte werden berücksichtigt

Schein ohne Note: Voraussetzung ist das Erreichen von 50% der Hausaufgabenpunkte

Als Prüfungszeitraum ist die Woche 22.-26.02.2010 vorgesehen. Termine werden ab sofort über das Sekretariat (Anne-Kristin Glanzberg, Reichenhainer Str. 41, Zimmer 615) vergeben.

Ergänzende Literatur

Geiger, Kanzow: Numerische Verfahren zur Lösung unrestringierter Optimierungsaufgaben, Springer
(zu Kapitel 1 "Freie Optimierung")
Geiger, Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben, Springer
(zu Kapitel 2 "Lineare Optimierung" und 4 "Nichtlineare Optimierung")
Nocedal, Wright: Numerical Optimization, Springer
(zu Kapitel 1 "Freie Optimierung", 2 "Lineare Optimierung" und 4 "Nichtlineare Optimierung")
Alt: Numerische Verfahren der konvexen, nichtglatten Optimierung, Teubner
(zu Kapitel 3 "Konvexe Optimierung")

Matlab-Einführungen

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

Matlab Tutorial (englisch)
Einführung in Matlab (und ein bisschen mehr aus Sicht eines Mathematikers) von G. Gramlich
Kurzeinführung von M. Pester
Links und Skripte rund um Matlab von R. Unger
Matlab: Eine freundliche Einführung von J. Behrens und A. Iske
Matlab: Eine Einführung von T. Schramm
Numerical Computing with MATLAB, Online-Buch von Cleve Moler (dem "Erfinder" von Matlab)
A Practical Introduction to Matlab von Mark S. Gockenbach
Matlab Primer von K. Sigmon

Informationen zu AMPL und zum 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-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.