Optimierung 1 Vorlesung MAT.255

Sommersemester 2019

Bettina Klinz

  Termine der Lehrveranstaltung

  Betreuung

  Anmeldung

  Begleitlehrveranstaltungen

  Inhalt und Ziel der Lehrveranstaltung

  Literatur und On-Line Materialien

  Ergänzungsmaterialien

  Prüfung/Zeugnisse

Termine der Vorlesung

Betreuung

Sprechstunden

Anmeldung

Begleitlehrveranstaltungen

Inhalt und Ziel der Lehrveranstaltung

Grobe Gliederung (Stichwörter)

• (1) Grundlagen der linearen Optimierung: Einführende Beispiele (Modellierung), Simplexverfahren (primal, dual, revidiert, numerische Umsetzung, Laufzeit) Dualitätstheorie, innere Punkteverfahren.

• (2) Grundlagen der nichtlinearen Optimierung ohne Nebenbedingungen (unrestringierter Fall): Optimalitätsbedingungen, Abstiegsverfahren, Line search, Konvergenzraten, Gradientenverfahren und CG-Verfahren, Newton- und Quasi-Newton Verfahren.

Literatur und Online-Materialien

Hauptquellen lineare Optimierung

• R.E. Burkard und U. Zimmermann, Einführung in die Mathematische Optimierung,
  Springer Spektrum, Springer, Berlin, Heidelberg, 2012, ISBN 978-3-642-28673-5.
  
  Sehr ausführlich im Bereich der linearen Optimierung, enthält aber auch Kapitel zu Themen der nichtlinearen, besonders konvexen Optimierung. Das Lehrbuch ist als ebook innerhalb des TU-Netzes verfügbar.

• R.J. Vanderbei, Linear Programming: Foundations and Extensions,
  Springer, New York, 4th ed. 2014, ISBN 978-1-4614-7629-0.
  
  Ein englisches Lehrbuch zur linearen Optimierung von einem Experten auf dem Gebiet der inneren Punkte Methoden (interior point methods). Das Buch ist insbesondere für deren Darstellung empfehlenswert. Ferner stellt die oben verlinkte Webseite des Autors eine Reihe zusätzlicher Ressourcen (Beispiele, Pivottools, etc.) zur Verfügung. Springer bietet eine ebook Version an - diese ist aber nicht an der TU Graz verfügbar.
  

• S.J. Wright, Primal-Dual Interior Point Methods,
  SIAM, 1997, ISBN 978-0-89871-382-4.
  
  Gute Quelle für Details zu primal-dualen Pfadverfolgungsmethoden (inklusive Beweise der Konvergenz- und Laufzeitaussagen).

• altes Skriptum von Rainer Burkard zur alten Vorlesung Mathematische Optimierung
  
  Die Kapitel zur linearen Optimierung können als Zusatzlektüre für die Vorlesung benutzt werden. Es werden jedoch einige Abschnitte in der Optimierung 1 Vorlesung nicht behandelt oder in anderer Weise behandelt.
  

• M.C. Ferris, O.L. Mangasarian and S.J. Wright, Linear programming with MATLAB,
  SIAM, 2007, ISBN 978-0-89871-643-6.
  
  Das Buch führt in Themen der linearen Optimierung ein und illustriert die behandelten Algorithmen an Hand von Matlab Codes (siehe auch die Webseite der Autoren).

Literatur zum Modellierungssystem AMPL

• R. Fourer, D.M. Gay, B. Kernighan, AMPL: A Modeling Language for Mathematical Programming,
  2-nd edition, ISBN 0-0-534-38809-4.
  
  Online frei verfügbar.

Hauptquelle nichtlineare Optimierung

• C. Geiger und C. Kanzow, Numerische Verfahren zur Lösung unrestringierter Optimierungsaufgaben,
  Springer Lehrbuch, Springer, Berlin, Heidelberg, New York, 1999, ISBN 978-3-540-66220-4.
  
  Springer bietet eine ebook Version an, die aber nicht im Netz der TU Graz verfügbar ist.

• P. Gritzmann, Grundlagen der Mathematischen Optimierung,
  Springer Fachmedien, Wiesbaden, 2013, ISBN 978-3-528-07290-2.
  
  Teilweise untypischer, geometrie-orientierter Zugang, lesenswert insbesondere für jene, die Interesse an einer alternativen Darstellung zur linearen Optimierung haben. Das Lehrbuch ist innerhalb des TU-Netzes als ebook verfügbar.

• G.B. Dantzig, M.N. Thapa, Linear Programming 1: Introduction,
  Springer, New York, 1997, ISBN 978-1-4757-8112-0.
  
  Zweiteiliges Buch (hier Teil 1) vom Vater des Simplexverfahrens (Dantzig). Springer bietet eine e-book Version an. Diese ist aber nicht an der TU Graz verfügbar.

• G.B. Dantzig, M.N. Thapa, Linear Programming 2: Theory and Extensions,
  Springer, New York, 2003, ISBN 978-1-4419-3140-5.
  
  Zweiteiliges Buch (hier Teil 2) vom Vater des Simplexverfahrens (Dantzig). Springer bietet eine e-book Version an. Diese ist aber nicht an der TU Graz verfügbar.

• R. Saigal, Linear Programming: A Modern Integrated Analysis,
  Springer, New York, 1995, ISBN 978-0-7923-9622-2.
  
  Springer bietet eine e-book Version an. Diese ist aber nicht an der TU Graz verfügbar.

• D.G. Luenberger und Y. Ye, Linear and Nonlinear Programming,
  Springer, New York, 3rd edition, 2008, ISBN 978-1-4419-4504-4. Springer bietet eine ebook Version an - diese ist aber nicht an der TU Graz verfügbar. (Alternativen vorhanden. Details auf Nachfrage.)
  
  Das ursprüngliche Buch von Luenberger ist ein Klassiker und wurde in der 3. Auflage um einen Abschnitt zu inneren Punktemethoden (von Ye) erweitert. Für die inneren Punktemethoden bevorzuge ich den Zugang von Vanderbei und für die restlichen Kapitel zur linearen Optimierung das Buch von Burkard und Zimmermann. Das Buch von Luenberger und Ye ist auf jeden Fall eine gute englischsprachige Referenz für den 2. Teil der Vorlesung.

• M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming: Theory and Algorithms,
  John Wiley & Sons, 3-rd edition, 2008, ISBN: 978-0-471-48600-8.
  
  Empfehlenswertes umfassendes Buch zur nichtlinearen Optimierung mit einer eher theoretischen Ausrichtung. Im TU Netz als e-book verfügbar.
  

• J. Nocedal, S. Wright, Numerical Optimization,
  Springer, New York, 2-nd ed., 2006, ISBN 978-0-387-30303-1.
  
  Empfehlenswertes Buch, das eine ausgewogene Mischung aus Theorie und Algorithmen anbietet. Das Buch behandelt auch die lineare Optimierung. Die Stärken liegen aber im nichtlinearen Bereich. Springer bietet eine e-book Version an, die aber nicht im TU-Netz verfügbar ist.

• I. Griga, S.G. Nash and A. Sofer, Linear and Nonlinear Programming,
  SIAM, 2-nd edition, 2009, ISBN: 978-0-898716-61-0, (first edition 1996 from McGraw).

• A. Beck, Introduction to Nonlinear Optimization: Theory, Algorithms and Applications with MATLAB SIAM, 2014, ISBN: 978-1-611973-64-8.
  Einfürung in Themen der nichtlinearen Optimierung mit und ohne Nebenbedingungen. Das Buch enth&auuml;t eine Reihe von Matlab Codes und viele anschauliche Beispiele und Illustrationen.

• C.T. Kelley, Iterative Methods for Optimization,
  Frontiers in Applied Mathematics 18, SIAM, 1999, ISBN: 978-0-89871-433-3.
  MATLAB Codes siehe hier. Buch ist online frei verfügbar.

Liste mit Links zu weiteren Ressourcen

• Linkliste zum Thema "Mathematische Optimierung" (in Englisch, im Aufbau).

Ergänzungsmaterialien

Diet problem (Stigler)

• Informationen und Tools zum Diet Problem am NEOS Server (beinhaltet u.a. historische Informationen und ein Tool zur Bestimmung eines kostengünstigsten Ernährungsplans)
  
  
• Artikel von Dantzig über seinen Bezug zum Diet Problem
  
  
• Wikipedia Beitrag zu Stiglers Modell
  

Zu inneren Punkteverfahren

• M.H. Wright, The interior-point revolution in optimization: History, recent developments, and lasting consequences,
  Bull. Amer. Math. Soc. 42 (2005), 39-56.
  
  Der Artikel ist online gratis verfügbar.
  
  
• D. Shanno, Who invented the interior point method,
  in: Documenta Mathematica, Extra Volume ISMP (2012), 55-64.
  
  Interessante Details zur Entwicklung von inneren Punkteverfahren. Der Artikel ist frei verfügbar.
  
  

Prüfung

Anmerkungen zur schriftlichen Prüfung

• Erster Termin: Wird am Semesterende stattfinden. genauer Termin wird noch bekanntgegeben.
  Ein Termin in den Sommerferien ist bei Bedarf möglich. Ein weiterer Termin wird am Beginn des Wintersemesters stattfinden.

Anmerkungen zur mündlichen Prüfung