-
Zeit
und Ort
Vorlesungstermine
Übungstermine
-
Beginn:
Vorlesung: Mo., 6. März, 14:00-15:55, HS BE01, Steyrergasse 30, Erdgeschoß
Übung: Do., 9. März, 12:15-14:00, HS BE01 / SR AE06, Steyrergasse 30, Erdgeschoß
-
Anmeldung
für Vorlesung und Übung via TUGonline bis 17.03.2017
-
Inhalt
Diese Lehrveranstaltung befasst sich mit grundlegenden Konzepten und Problemen der Mathematischen
Optimierung, insbesondere mit (kontinuierlichen) linearen Optimierungsproblemen und unrestringierten nichtlinearen Optimierungsproblemen (d.h. mit nichtlinearen Optimierungsproblemen ohne Nebenbedingungen).
Im ersten Teil der Vorlesung werden Grundlagen der Linearen Optimierung besprochen: das Simplexverfahren (primal, dual, revidiert, numerische Umsetzung, Laufzeit), Dualitästheorie, innere Punkteverfahren.
Im zweiten Teil der Vorlesung werden Grundlagen der Nichtlinearen Optimierung ohne Nebenbedingungen besprochen: Optimalitätsbedingungen, Abstiegsverfahren, Line Search, Konvergenzraten, Gradientenverfahren und CG-Verfahren, Newton- und Quasi-Newton Verfahren.
Einige Kapitelüberschriften und Stichwörter sind:
Teil I: Lineare Optimierung
- Einführende Optimierungsmodelle
- Hauptsatz der linearen Optimierung
- Das Simplexverfahren: Ausgangslösung, Spaltenauswahl, Kreisen des Verfahrens, Behandlung von Gleichungen, beschränkten Variablen und Variablen mit beliebigen Vorzeichen, Simplexinterpretation, das revidierte Simplexverfahren, das Simplexverfahren mit LU-Zerlegung. Dualitätstheorie: Dualitätssätze, das duale Simplexverfahren.
- Innere Punkteverfahren: der zentraler Pfad, Pfad-verfolgende Methoden.
Teil II: Unrestringierte nichtlineare Optimierung
- Allgemeine Theorie und Optimalitätsbedingungen
- Abstiegsverfahren
- Konvergenzgeschwindigkeit
- Gradientenverfahren und CG-Verfahren
- Newton Verfahren
- Quasi-Newton Verfahren
-
Literatur
Je nach Thema und Kapitel dienen folgende Bücher als Ausarbeitungsgrundlage für diese Vorlesung:
-
R.E.Burkard und U.T. Zimmermann,
Einführung in die Mathematische Optimierung,
Springer Lehrbuch, 2012.
Das ist die Hauptreferenz für die meisten Kapitel über die lineare Optimierung und ist auch als ebook im TUCampus vorhanden.
-
R. Vanderbei, Linear Programming: Foundations and Extentions , Springer US, 2010.
Sehr gutes Buch zu den Innerepunkteverfahren in der linearen Optimierung. Zugang zu zusätzlichen Ressourcen über die Webseite des Autors.
- M.C. Ferris, O.L. Mangasarian and S.J. Wright,
Linear programming with MATLAB,
SIAM, 2007.
- C. Geiger und C. Kanzow, Numerische Verfahren zur Lösung unrestringierter Optimierungsaufgaben,
Springer Lehrbuch, Springer, Berlin, Heidelberg, New York, 1999.
- D.G. Luenberger und Y. Ye,
Linear and Nonlinear Programming (International Series in Operations Research & Management Science) , Springer US, 2008.
- S.J. Wright, Primal-Dual Interior Point Methods,
SIAM, 1997.
Zusätzliche Literatur:
- M.S. Bazaraa, H.D. Sherali und C.M. Shetty, Nonlinear Programming: Theory and Algorithms, Wiley, 2006.
-
G.B. Dantzig und M.N. Thapa Linear Programming: 1: Introduction, Springer Series in Operations Research and Financial Engineering, 1998.
-
G.B. Dantzig und M.N. Thapa Linear Programming: 2: Theory and Extentions, Springer Series in Operations Research and Financial Engineering, 2010.
- P. Gritzmann, Grundlagen der Mathematischen Optimierung,
Springer Fachmedien, Wiesbaden, 2013.
- J. Nocedal, S. Wright, Numerical Optimization,
Springer, New York, 2-nd ed., 2006.
Weitere Literaturhinweise und Unterlagen, die von Zeit zu Zeit in der Lehrveranstaltung erwähnt/besprochen werden, werden hier verlinkt.
-
Prüfungsmodus Vorlesung
Die Vorlesung wird anhand einer schriftlichen und einer mündlichen Prüfung benotet.
Für die schriftliche Prüfung werden Sammeltermine angeboten.
Erster Termin: Montag 3.7.2017, Zeitrahmen 8:00-12:00, der Raum und die genaue Beginnzeit werden rechtzeitig bekanntgegeben.
Weitere Termine werden noch festgelegt. Ein Termin in den Sommerferien ist bei Bedarf möglich. Ein weiterer Termin wird am Beginn des Wintersemesters 2017/18 stattfinden. Die mündlichen Prüfungstermine werden individuell mit der Vortragenden vereinbart.
Die Anmeldung zur schriftlichen Prüfung erfolgt ausschließlich via TUGonline.
-
Prüfungsmodus Übung
Die zweistündige Übung hat einen immanenten Charakter und wird anhand von zwei Klausuren und der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe
eines Punktesystems benotet.
Klausuren
- Termine:
1. Übungsklausur: Fr., 5.5., 15:00-17:00. (Der Raum wird noch bekanntgegeben)
2. Übungsklausur: Fr., 30.6., 15:00-17:00. (Der Raum wird noch bekanntgegeben)
- Punkte:
Bei jeder Klausur können maximal 16 Punkte erworben werden.
Für ein positives Übungszeugnis müssen bei den Klausuren in Summe mindestens 14 Punkte
erreicht werden.
- Anmeldung:
Die Klausurtermine werden (rechtzeitig) im Prüfungssystem des TUGonline erfasst;
Die Anmeldung zu den Klausuren erfolgt ausschließlich via TUGonline.
- Nachklausur
Aufgrund des immanenten Charakters der Lehrveranstaltung gibt es genau eine Nachklausur.
Diese wird voraussichtlich in der letzten Woche der Sommerferien stattfinden.
Der genaue Termin wird rechtzeitig bekanntgegeben.
Beim Antreten zur Nachklausur ist zu entscheiden,
ob die erste oder die zweite Klausur wiederholt werden soll. Durch den Antritt werden die Punkte aus der wiederholten Klausur gelöscht.
Die Anmeldung zur Nachklausur erfolgt ausschließlich via TUGonline.
Bei den Übungsklausuren sind alle schriftlichen Unterlagen sowie Taschenrechner mit einer Ausgabezeile erlaubt.
Dennoch sind alle
Zwischenschritte anzugeben.
Die Verwendung von internetfähigen Geräten wie Notebooks, PDAs, Handhelds, Handys etc. ist nicht gestattet.
Mitarbeit
Die Mitarbeit wird mit Hilfe folgender Leistungen erfasst:
- Ausarbeitung der Übungsbeispiele und Präsentation der Lösungen an der Tafel
Rechtzeitig vor jeder Übungseinheit wird auf der LV-Homepage bekanntgegeben welche Übungsaufgaben für die kommende Übungseinheit vorbereitet werden sollten. Es werden in der Regel mehr Übungsaufgaben veröffentlicht als in den übungseinheiten besprochen werden, die zusätzlichen Aufgaben dienen zum Selbststudium.
Jeder Studierender kann vor der Übungseinheit bekannt geben welche Beispiele sie/er ausgearbeitet hat. Dazu
werden jeden Mittwoch mittag (vor einer Übungseinheit) Listen zum Ankreuzen der gerechneten Übungsbeispiele am Anschlagbrett rechts vom Büro C207 (Büro von Eranda Dragoti-Çela, Steyrergasse 20, 2. Obergeschoß) ausgehängt. Die Eintragungen haben bis 15 Minuten vor Beginn der Übungen (also bis 12:00, donnerstags) zu erfolgen. Wenn Sie Zweifel an der prinzipiellen Korrektheit eines Lösungsansatzes haben, bitte statt eines Kreuzes ein Fragezeichen als Markierung verwenden. (Im Zweifelsfall wird Studierenden mit Kreuzmarkierung der Vorrang gegeben. Bitte das System nicht missbrauchen - im starken Zweifelsfall Fragezeichen statt Kreuz verwenden.)
Unter allen Kandidaten, die ein bestimmtes Beispiel angekreuzt haben, wählt der Übungsleiter/die Übungsleiterin einen Studierenden aus, der dann die Aufgabe an der Tafel vorzuführen hat. Diese Auswahl erfolgt unter Berücksichtigung der Anzahl der bereits getätigten Tafelmeldungen (Vorrang haben jene mit weniger Meldungen).
Für ein positives Übungszeugnis muss jeder Studierender
mindestens zwei Mal an der Tafel vorrechnen. Jede Tafelmeldung ist maximal 2 Punkte Wert. Falsche Lösungsansätze werden mit 0 Punkten bewertet.
Bei der Bewertung der
Tafelmeldungen wird neben der mathematischen Korrektheit auch auf die
Qualität der Präsentation Wert gelegt. Ziel ist es, die Aufgaben so zu präsentieren, dass der Lösungsweg auch für jene verständlich wird, die die Aufgabe nicht selbst gelöst haben.
Wenn sich für ein Beispiel niemand meldet, der noch eine Pflicht-Tafelmeldung benötigt, dann können zusätzliche Tafelmeldungen von Studierenden, die ihre Pflichttafelmeldungen bereits getätigt haben, bewertet werden, (maximal 1 Punkt pro zusätzliche Tafelmeldung, siehe Details über Punktesystem.)
- Programmieraufgaben
Unter den Übungsaufgaben werden sich auch einige Programmieraufgaben befinden. Die Aufgaben sind in Matlab oder Octave zu lösen und die Codes sind per e-mail mindestens 2 Stunden vor Beginn der Übungseinheit an den Übungsleiter/die Übungsleiterin zu schicken.
Unter allen Studierenden, die eine bestimmte Programmieraufgabe gelöst und den Code an den Übungsleiter/die Übungsleiterin geschickt haben, wählt der Übungsleiter/die Übungsleiterin einen Studierenden aus, der dann den Code mittels Beamerpräsentation zu erläutern hat. Wer eine Programmieraufgabe abgibt, muß auch bei Vorliegen von 2 Tafelmeldungen damit rechnen zur Präsentation des abgegebenen Codes herangezogen zu werden. Die Präsentationen von Codes werden - ähnlich wie Tafelmeldungen zu "klassischen" Aufgaben - mit maximal 2 Punkten bewertet.
Es sind mindestens 2 Programmieraufgaben abzugeben, um einen positiven Übungsabschluss zu erreichen.
Für diese Pflichtabgaben werden keine Punkte vergeben. Für über das Mindestkontingent hinausgehend abgegebene Aufgaben gibt es Bonuspunkte ( siehe Details über Punktesystem ).
- Modellierungsprojekt
Das Modellierungsprojekt wird in Gruppen bearbeitet. Jede Gruppe besteht im Regelfall aus 5 Personen (müssen nicht dieselbe Übungsgruppe besuchen) und erhält eine eigene Aufgabe, die die Modellierung und Lösung eines realitätsnahen Optimierungsproblems umfasst (eine Liste wird im Laufe des Semesters auf dieser Seite zur Verfügung gestellt).
Das Modell soll mit Hilfe der algebraischen Modellierungssprache AMPL formuliert und mit einem der durch AMPL unterstützten Solver gelöst werden. Eine kurze Einführung in AMPL wird im Rahmen der Vorlesung gegeben. Sinn und Zweck des Modellierungsprojekts ist jedoch auch die individuelle und selbstständige Auseinandersetzung der Studierenden mit AMPL und den jeweiligen Solvern. Die Gruppeneinteilung und die Aufgabenzuordnung werden im Laufe des Semesters erfolgen, nachdem die theoretischen Grundlagen für die Bearbeitung der Modellierungsprojekte vorhanden sind.
Das Modellierungsprojekt wird mit maximal 4 Punkten bewertet.
Konkrete Details über die Ausarbeitung und die Abgabe der Miniprojekte werden zu einem späteren Zeitpunkt hier erläutert.
Bewertungsschema
- Punktesystem
- Klausuren: maximal 32 Punkte (je 16)
- Tafelmedungen: maximal 4 Punkte aus 2 Pflichttafelmeldungen (je 2)
- Modellierungsprojekt: maximal 4 Punkte
- Bonus: maximal 6 Punkte mit 2 Punkten aus Zusatztafelmeldungen, 3 Punkten aus über das Mindestkontingent hinausgehend abgegebenen Programmieraufgaben, 1 Punkt für etwaige Sonderleistungen (liegt im Ermessen des LV-Leiters/der LV-Leiterin und stellt einen Sonderfall dar).
- Abzug: 2 Punkte Abzug, wenn jemand zur Behandlung einer abgegebenen Programmieraufgabe ausgewählt wird und den Code nicht erklären kann.
- Minimalvoraussetzungen für ein positives Übungszeugnis
- Mindestens 14 Punkte in Summe aus den 2 Übungsklausuren.
- Mindestens 2 Tafelmeldungen (0 Punkte Meldungen werden nicht berücksichtigt).
- Mindestens 2 Punkte aus dem Modellierungsprojekt.
- Mindestens 2 abgebenene Programmieraufgaben (lauffähig).
- Mindestens 22 Punkte in Summe
- Notenschlüssel :
|
0 <= P < 22 | Nicht genügend |
|
22 <= P <= 28 | Genügend |
|
28 < P <= 34 | Befriedigend |
|
34 < P <= 39.5 | Gut |
|
39.5 < P | Sehr Gut.
|
-
Übungsaufgaben
(pdf)
- Teil 1
Ankreuzbar für die 1. Übungseinheit am 7.3.: Beispiele 1 bis 9.
- Teil 2
Ankreuzbar für die 2. Übungseinheit am 16.3.: Beispiele 7, 8, 9, 10, 11, 12, 14, 15, 16
- Teil 3
Ankreuzbar für die 3. Übungseinheit am 23.3.: Beispiele 15, 16, 17, 18, 19, 20, 22, 23, 24
- Teil 4
Ankreuzbar für die 4. Übungseinheit am 30.3.: Beispiele 23, 24, 25, 26, 27, 28, 29, 30, 31
- Teil 5
Ankreuzbar für die 5. Übungseinheit am 6.4.: Beispiele 28, 29, 30, 31, 33, 34, 37, 38,
- Teil 6
Ankreuzbar für die 6. Übungseinheit am 27.4.: Beispiele 37, 38, 39, 40, 41, 42, 43, 44
- Teil 7
Ankreuzbar für die 7. Übungseinheit am 4.5.: Beispiele 47, 48, 49, 51, 52, 53, 44, 45
- Teil 8
Ankreuzbar für die 8. Übungseinheit am 11.5.: Beispiele 52, 44, 45, 55, 56, 57, 58, 59, 60
- Teil 9
Ankreuzbar für die 9. Übungseinheit am 18.5.: Beispiele 57, 58, 59, 60, 61, 62, 63, 64
- Teil 10
Ankreuzbar für die 10. Übungseinheit am 1.6.: Beispiele 63, 64, 65, 66, 68, 69, 71, 72, 73
- Teil 11
Ankreuzbar für die 11. Übungseinheit am 8.6.: Beispiele 71, 72, 73, 74, 76, 78, 79, 80, 81, 82
- Teil 12
Ankreuzbar für die 12. Übungseinheit am 22.6.: Beispiele 78, 80, 81, 82, 83, 84, 85, 87, 88, 90
cela@opt.math.tu-graz.ac.at.