This page is outdated.

Grundlagen der Optimierung (4V, 2Ü)

Prof. HerzogWS2014/15

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.

Zur Wiederholung und Vertiefung dieser Begriffe (insbesondere für Studierende des Studienganges Master Finance) bietet es sich an, gezielt nachzuschlagen, zum Beispiel in folgenden Büchern:

Arens, Hettlich, Karpfinger, Kockelkorn, Lichtenegger, Stachel: Mathematik, Springer, ISBN 978-3-8274-2347-4 (mit Übungsaufgaben, deren Lösungen online bereit stehen (unter Zusatzmaterialien zu den einzelnen Kapiteln))
Luderer, Würker: Einstieg in die Wirtschaftsmathematik, Vieweg+Teubner, 2015, ISBN 978-3-658-05936-1 (mit einigen Übungsaufgaben ohne Lösungen)

Die Seiten der Wikipedia, von denen einige brauchbare oben verlinkt sind, lassen sich dabei in der Regel nur mit Vorwissen nutzen.

Termine

4 Veranstaltungen aus dem Archiv des Vorlesungsverzeichnisses (Wintersemester 2014/15)
Nummer	Name	Gruppen	Dozenten	Zeit	Raum
220000-370 [WS2014/15]	Grundlagen der Optimierung [Vorlesung]	obl: B_MaIn3, M_FiMR1, B_MaFM3, B_MaWM3, B_MaTM3, B_MaMa3 wo: B_InMa3, M_FiAV3, M_FiAV1, M_FiBB1, M_FiBB3, M_FiFK1, M_FiFK3, M_FiIF1, M_FiIF3, M_FiMR3, M_FiUF1, M_FiUF3, B_Ph__5, B_Ph__6, B_MaFM5, B_MaWM5, B_MaMa5	Prof. Roland Herzog (225033)	Dienstag (wö.) 09:15-10:45	2/W015
220000-370A [WS2014/15]	Grundlagen der Optimierung [Vorlesung]	obl: B_MaIn3, M_FiMR1, B_MaFM3, B_MaWM3, B_MaTM3, B_MaMa3 wo: B_InMa3, M_FiAV3, M_FiAV1, M_FiBB1, M_FiBB3, M_FiFK1, M_FiFK3, M_FiIF1, M_FiIF3, M_FiMR3, M_FiUF1, M_FiUF3, B_Ph__5, B_Ph__6, B_MaFM5, B_MaWM5, B_MaMa5	Prof. Roland Herzog (225033)	Mittwoch (wö.) 15:30-17:00	2/W015
220000-371 [WS2014/15]	Grundlagen der Optimierung [Übung]	obl: B_MaIn3, B_MaFM3, B_MaWM3, B_MaTM3, B_MaMa3 wo: B_MaFM5, B_MaWM5, B_MaMa5	Ailyn Schäfer (225033)	Freitag (wö.) 13:45-15:15	2/N002
220000-372 [WS2014/15]	Grundlagen der Optimierung [Übung]	obl: M_FiMR1 wo: B_InMa3, M_FiAV3, M_FiAV1, M_FiBB1, M_FiBB3, M_FiFK1, M_FiFK3, M_FiIF1, M_FiIF3, M_FiMR3, M_FiUF1, M_FiUF3, B_Ph__5, B_Ph__6	Jan Blechschmidt (225033)	Freitag (wö.) 07:30-09:00	2/N105

Aktuelles

02.03.2015	Die Liste möglicher Prüfungsfragen wurde aktualisiert.
15.01.2015	Die Vorbereitungszeit für die Prüfung wurde auf 30 Minuten festgesetzt. Da die vereinbarte Zeit den tatsächliche Beginn der Prüfung darstellt, seien Sie bitte 35 Minuten vor Ihrem eigentlichen Prüfungstermin am Büro von Prof. Herzog (Reichenhainer Str. 41, Zimmer 604).
05.01.2015	Prüfungstermine werden ab sofort vergeben.
05.01.2015	Eine Liste möglicher Prüfungsfragen wurde online gestellt.
03.12.2014	Am Mittwoch, dem 03.12.2014 findet ab 14:30 Uhr das Hoffest der TU Chemnitz statt. Wenn jemand daran teilnehmen möchte, melde er sich bitte bei Prof. Herzog.
27.11.2014	Am 27. November 2014 finden aufgrund des Tages der Lehre ab der 4. Lehreinheit (13.00 Uhr) keine Lehrveranstaltungen statt.
30.10.2014	Jun.-Prof. Dr. Winnifried Wollner hält am Donnerstag, den 30.10.2014 (um 16:00 Uhr in Raum 2/B202, Reichenhainer Straße 70) einen Vortrag im Rahmen des Chemnitzer Mathematischen Colloquiums (CMC) mit dem Titel Regularisierung und A-Posteriori-Fehlerkontrolle für Optimierungsprobleme mit PDGen. Interessenten sind herzlich eingeladen.
30.10.2014	Am 30. Oktober 2014 findet um 7:30 Uhr im Raum 2/N101 eine Übung (3. Übungsblatt) für beide Übungsgruppen statt. Damit wird der Ausfall aufgrund des Feiertags am 31. Oktober 2014 kompensiert.
21.08.2014	Die Vorlesung und Übungen beginnen in der ersten Vorlesungswoche.
21.08.2014	Sprechzeit Roland Herzog: Tuesday 11:00 - 11:45 and by appointment. It is advisable to make an appointment through Mrs. Glanzberg even during regular office hours. During the non-lecture period, meetings are by appointment only. Sprechzeit Jan Blechschmidt: any time when present Sprechzeit Ailyn Schäfer:

Material zur Vorlesung

Beiblatt: Einführende Beispiele (Beispiele 1.2-1.5) (14.10.2014)
Skript § 2: Notation und Wiederholung von Differenzierbarkeitsbegriffen (15.10.2014)
Beiblatt: Konvergenzverhalten des Gradientenverfahrens (Satz 4.10) (22.10.2014)
Beiblatt: Globalisiertes Newtonverfahren in der Optimierung (Abschnitt 5.4) (04.11.2014)
Beiblatt: Mozartproblem (Beispiel 6.1) (05.11.2014)
Skript_Vorlesung_10_20141112.pdf (12.11.2014)
Beiblatt: Simplex-Algorithmus (Algorithmus 7.6) (18.11.2014)
Skript § 10: Innere-Punkte-Verfahren (nicht besprochen, inhaltlich nach dem 26.11.2014)
Beiblatt: Barriere-Problem (nicht besprochen, inhaltlich nach dem 26.11.2014)
Skript_Vorlesung_18_20141216.pdf (16.12.2014)
Beiblatt: Lagrange-duale Aufgaben (Datum)
Beiblatt: Aufgabe mit Dualitätslücke (Beispiel 19.7) (Datum)

Übungen

Die Übungen finden als Präsenzübungen statt, in denen Sie unter Anleitung die Aufgaben des jeweiligen Übungsblattes bearbeiten, gerne auch in kleinen Gruppen. Einige Aufgaben werden auch vorgerechnet. Die Übungen dienen der Wiederholung und Anwendung des Vorlesungsstoffes.
Darüberhinaus werden Hausaufgaben angeboten, die Sie zur weiteren Vertiefung des Inhaltes der Vorlesung und Übung und zum selbstständigen Problemlösen anregen sollen. Die Hausaufgaben können Sie gerne auch in einer kleinen Gruppe bearbeiten. Für die Hausaufgaben wird es keine fertigen Lösungen geben. Sie können jedoch Ihre Lösungsansätze und Ergebnisse überprüfen lassen, indem Sie Ihre Hausaufgaben bei Ihrem Übungsleiter oder in der Vorlesung abgeben (Sie erhalten dann eine korrigierte Version zurück) und/oder mit Ihrem Übungsleiter in seiner/ihrer Sprechstunde durchsprechen.

Übung	Material zur Übung
exercise01.pdf	Aufgabe 1: engine.mod engine1.dat engine2.dat engine3.dat engine.cmd Aufgabe 2: table.mod table.dat table.cmd
exercise02.pdf	Aufgabe 6: Plot_Himmelblau.m Hausaufgabe 9: knapsack.cmd knapsack.mod knapsack.dat
exercise03.pdf	Aufgabe 10: rosenbrock.m ls_armijo.m ls_testfun.m solution_A10.m Hausaufgabe 10: himmelblau.m Hausaufgabe 11: plot_quadratic_functions.m rosenbrock.m plot_rosenbrock.m Hausaufgabe 12: aufgabe187v1.m steepest_descent_armijo.m himmelblau.m cosine.m general_quadratic_function.m myplot.m
exercise04.pdf
exercise05.pdf
exercise06.pdf
exercise07.pdf	Aufgabe 22: simplex.m (vollständig) solution_A22.m
exercise08.pdf	Aufgabe 24: klee_minty_func.m
exercise09.pdf
exercise10.pdf
exercise11.pdf
exercise12.pdf
exercise13.pdf
exercise14.pdf
exercise15.pdf

Prüfung

Über den Inhalt der Lehrveranstaltung findet im Anschluss eine 30-minütige mündliche Prüfung statt. Unmittelbar vor der Prüfung wird es eine 30-minütige Vorbereitungszeit geben, in der Sie zufällig einige Fragen ziehen und Ihre Antworten vorbereiten können. Der von Ihnen vereinbarte Prüfungstermin ist der Beginn der eigentlichen Prüfung. Finden Sie sich also bitte 35 Minuten vor Ihrem eigentlichen Prüfungstermin am Büro von Prof. Herzog (Reichenhainer Str. 41, Zimmer 604) ein. Durch einen Aushang an der Tür erfahren Sie, wo Sie Ihre Aufgaben erhalten und vorbereiten können.
Bitte beachten Sie, dass sich der Prüfungsstoff auf die Inhalte von Vorlesung, Übung und Hausaufgaben erstreckt. Auch ein Beweis kann gefragt sein. (Bei der Vorbereitung auf die Prüfung kann Ihnen eine Liste möglicher Prüfungsfragen helfen.) Prüfungstermine sind an folgenden Tagen möglich:

Freitag, 13.02.2015
Donnerstag, 19.02.2015
Donnerstag, 05.03.2015
Freitag, 06.03.2015
Donnerstag, 19.03.2015
Freitag, 20.03.2015
Mittwoch, 01.04.2015
Donnerstag, 02.04.2015

Termine werden ab sofort über das Sekretariat (Anne-Kristin Glanzberg, Reichenhainer Str. 41, Zimmer 615) vergeben.

Ergänzende Literatur

Ulbrich, Ulbrich: Nichtlineare Optimierung, Springer, 2012; is available online at TU Chemnitz
Geiger, Kanzow: Numerische Verfahren zur Lösung unrestringierter Optimierungsaufgaben, Springer, 1999
(zu Kapitel 1 "Freie Optimierung")
im Semesterapparat
Geiger, Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben, Springer, 2002
(zu Kapitel 2 "Lineare Optimierung" und 4 "Nichtlineare Optimierung")
im Semesterapparat
Nocedal, Wright: Numerical Optimization, Springer, 2006
(zu Kapitel 1 "Freie Optimierung", 2 "Lineare Optimierung" und 4 "Nichtlineare Optimierung"); ist an der TU Chemnitz hier online abrufbar
Alt: Numerische Verfahren der konvexen, nichtglatten Optimierung, Teubner, 2004
(zu Kapitel 3 "Konvexe Optimierung")
im Semesterapparat

Matlab-Einführungen und Optimierungssoftware für Matlab

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

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.