• 
• 

Grundlagen der Optimierung (4V, 2Ü) Prof. Herzog, WS2012/13

Inhalt

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

Nr.	Veranstaltung	Art	LVS	Lehrkraft	Tag	Woche	Zeit	Raum
220000-370	Grundlagen der Optimierung obl : B_MaFM3, B_MaIn3, B_MaMa3, B_MaTM3, B_MaWM3, M_FiMR1 wo : M_FiUF3, M_FiMR3, M_FiIF3, M_FiFK3, M_FiBB3, M_FiAV3, B_InMa3, M_FiUF1, M_FiIF1, M_FiFK1, M_FiBB1, M_FiAV1, B_Ph2_5, B_Ph1_5	V	2	Prof. Roland Herzog	Donnerstag	wö	13:45 - 15:15	2/N001
220000-370A	Grundlagen der Optimierung obl : B_MaFM3, B_MaIn3, B_MaMa3, B_MaTM3, B_MaWM3, M_FiMR1 wo : M_FiUF3, M_FiMR3, M_FiIF3, M_FiFK3, M_FiBB3, M_FiAV3, B_InMa3, M_FiUF1, M_FiIF1, M_FiFK1, M_FiBB1, M_FiAV1, B_Ph2_5, B_Ph1_5	V	2	Prof. Roland Herzog	Freitag	wö	07:30 - 09:00	2/N001
220000-371	Grundlagen der Optimierung obl : B_MaFM3, B_MaIn3, B_MaMa3, B_MaTM3, B_MaWM3		2	Frank Schmidt	Mittwoch	wö	09:15 - 10:45	2/N102
220000-372	Grundlagen der Optimierung obl : M_FiMR1 wo : M_FiUF3, M_FiMR3, M_FiIF3, M_FiFK3, M_FiBB3, M_FiAV3, B_InMa3, M_FiUF1, M_FiIF1, M_FiFK1, M_FiBB1, M_FiAV1, B_Ph2_5, B_Ph1_5		2	Tommy Etling	Mittwoch	wö	17:15 - 18:45	2/N105

Aktuelles

Material zur Vorlesung

• Beiblatt: Einführende Beispiele (Beispiele 1.2-1.5) (11.10.2012)
• Beiblatt: Konvergenzverhalten des Gradientenverfahrens (Satz 4.10) (19.10.2012)
• Beiblatt: Globalisiertes Newtonverfahren in der Optimierung (Abschnitt 5.4) (26.10.2012)
• Beiblatt: Mozartproblem (Beispiel 6.1) (01.11.2012)
• Beiblatt: Simplex-Algorithmus (Algorithmus 7.6) (09.11.2012)
• Beiblatt: Barriere-Problem (22.11.2012)
• Beiblatt: Lagrange-duale Aufgaben (25.01.2013)
• Beiblatt: Aufgabe mit Dualitätslücke (Beispiel 19.7) (31.01.2013)

Übungen

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

Übung	Material zur Übung
exercise01.pdf	Aufgabe 2: Plot_Himmelblau.m
exercise02.pdf	Aufgabe 5: engine.mod engine1.dat engine2.dat engine3.dat engine.cmd Aufgabe 6: table.mod table.dat table.cmd Aufgabe 7: competition.mod competition.dat competition.cmd Aufgabe 11: cargo.mod cargo1.cmd cargo2.cmd
exercise03.pdf	Hausaufgabe 1: plot_quadratic_functions.m rosenbrock.m plot_rosenbrock.m
exercise04.pdf	Hausaufgabe 7: knapsack.cmd knapsack.mod knapsack.dat Hausaufgabe 8: ls_armijo.m ls_testfun.m solution_HA08.m
exercise05.pdf	Hausaufgabe 11: aufgabe187v1.m steepest_descent_armijo.m himmelblau.m cosine.m general_quadratic_function.m myplot.m
exercise06.pdf	Hausaufgabe 13: newton_method.m solution_HA13.m
exercise07.pdf
exercise08.pdf	Hausaufgabe 22: simplex.m solution_HA22.m
exercise09.pdf	Aufgabe 28: klee_minty_func.m
exercise10.pdf
exercise11.pdf
exercise12.pdf (Aufgabe 37 am 20.12.2012 geändert)
exercise13.pdf
exercise14.pdf
exercise15.pdf

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.) Prüfungstermine sind an folgenden Tagen möglich:

• Freitag, 08.02.2013
• Donnerstag, 14.02.2013
• Mittwoch, 13.03.2013
• Dienstag, 19.03.2013

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")
  im Semesterapparat
• Geiger, Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben, Springer
  (zu Kapitel 2 "Lineare Optimierung" und 4 "Nichtlineare Optimierung")
  im Semesterapparat
• Nocedal, Wright: Numerical Optimization, Springer
  (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
  (zu Kapitel 3 "Konvexe Optimierung")
  im Semesterapparat

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.

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.

Roland Herzog
29. Januar 2013

• 
• 
• 
• 
• 

TU Chemnitz, Fakultät für Mathematik, 09107 Chemnitz

• Impressum
• - Copyright © 2013 by TU Chemnitz. Alle Rechte vorbehalten.