Optimierung 1
SS 2017, 4 VO/2 UE
(MAT.255 / MAT.256)

E. Dragoti-Çela (Vorlesung und Übung)

J. Baumhakel (Studienassistent, Leiter der 2. Übungsgruppe)

Institut für Diskrete Mathematik

• Zeit und Ort
Vorlesungstermine


Übungstermine



• Beginn:
  Vorlesung: Mo., 1. März, 14:15-16:00, online streaming und webex
  Übung: Mo., 8. März, 14:15-16:00, online streaming und webex
• Anmeldung
für Vorlesung und Übung via TUGonline bis 31.03.2021
• 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 und beschränkten Variablen sowie 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.
• 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: Freitag 2.7.2017, Zeitrahmen 14:00-18: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 2021/22 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: Do., 6.5., 15:00-17:00. (Der Raum wird noch bekanntgegeben)
2. Übungsklausur: Do., 1.7., 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 (online) Präsentation der Lösungen
Rechtzeitig vor jeder Übungseinheit wird in TechCenter (TC) ein neues Aufgabeblatt veröffentlicht. Weiters wird 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 soll vor der Übungseinheit via TeachCenter (TC) bekannt geben welche Beispiele sie/er ausgearbeitet hat. Die vorbereitetn Lösungen soll als Abgabe in TC hochgeladen werden. Die Frist dazu ist montags 12:00 (vor einer Übungseinheit)


Unter allen Kandidaten, die ein bestimmtes Beispiel 'angekreuzt' bzw. die Lösung eines Beispiels abgegeben haben, wählt der Übungsleiter/die Übungsleiterin einen Studierenden aus, der dann die Aufgabe vorzuführen hat. Diese Auswahl erfolgt unter Berücksichtigung der Anzahl der bereits getätigten Tafelmeldungen (Vorrang haben Studierende mit weniger Meldungen). Für ein positives Übungszeugnis muss jeder Studierender mindestens drei Mal an der Tafel vorrechnen. Jede Tafelmeldung ist maximal 2 Punkte Wert. Völlig falsche Lösungsansätze werden mit 0 Punkten bewertet. Rechenfehler oder Lösungsansätze, die eine brauchbare Idee enthalten, zählen nicht als völlig falsch, die Entscheidung liegt jedenfalls im Ermessen des Übunsleiters/ der Übungsleiterin.
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, Octave, Python, C oder C++ zu lösen und die Codes sind mindestens 4 Stunden vor Beginn der Übungseinheit in TC hochzuladen. Der eventueller Einsatz anderer Programmiersprachen ist nur nach Erlaubnis des Übungsleiters/der Übungsleiterin zulässig.
Unter allen Studierenden, die eine bestimmte Programmieraufgabe gelöst und den Code rechtzeitg in TC hochgeladen haben wählt der Übungsleiter/die Übungsleiterin einen Studierenden aus, der dann seinen Code erläutert und ausfürt. Wer eine Programmieraufgabe abgibt, muß auch bei Vorliegen von 3 Tafelmeldungen damit rechnen, zur Präsentation des abgegebenen Codes herangezogen zu werden. Die Präsentationen von Codes werden - ähnlich wie Präsentationen von "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 4-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 zur Verfügung gestellt).
Das Modell soll mit Hilfe der algebraischen Modellierungssprache AMPL formuliert und mit einem 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.


Bewertungsschema

• Punktesystem


• Klausuren: maximal 32 Punkte (je 16)


• Tafelmedungen: maximal 6 Punkte aus 3 Pflichttafelmeldungen (je 2)
• Modellierungsprojekt: maximal 4 Punkte
• Bonus: maximal 6 Punkte bestehend aus maximal 2 Punkten aus Zusatztafelmeldungen, 3 Punkten für über das Mindestkontingent hinausgehende abgegebene 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 3 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 <= 27	Genügend
27 < P <= 32	Befriedigend
32 < P <= 37	Gut
37 < P	Sehr Gut.







• Übungsaufgaben (pdf)

• Implementierungsgsaufgaben (pdf)

• Weitere Literatur und Unterlagen

Back to my homepage

März 2021