Lehre

Die lineare Optimierung beschäftigt sich mit der Optimierung linearer Funktionen auf Mengen, die durch lineare Ungleichungen beschrieben werden, und ist eines der ältesten Teilgebiete der mathematischen Optimierung. Viele Probleme der Praxis, beispielsweise in der Planung von Vekehrs- oder Kommunikationsnetzen, der Produktionsplanung oder im Gütertransport, lassen sich als sogenannte lineare Programme formulieren. Aufgrund ihrer langen Geschichte hat die lineare Optimierung den Grundstein für verschiedene zentrale Konzepte in der mathematischen Optimierung gelegt. Dazu zählen Dualität und die Bedeutung von Konvexität.

Die Vorlesung Lineare Optimierung bietet dadurch einen sinnvollen Einstieg in das Gebiet der mathematischen Optimierung. Gelehrt werden u. a.:

• Grundlagen der Polyedertheorie (Darstellungen von Polyedern, Satz von Weyl, Satz von Minkowski, Seiten, Charakterisierung von Ecken u. a.),
• theoretische Grundlagen der linearen Optimierung (Standardformen linearer Programme, Existenz von Lösungen, Annahme der Lösung in Ecken des zulässigen Bereiches, kanonische Formen u. a.),
• primaler und dualer Simplexalgorithmus,
• Dualität (duales lineares Programm, starker und schwacher Dualitätssatz, Farkas-Lemma, Satz vom komplementären Schlupf),
• Umgang mit Optimierungssoftware,
• Anwendungen der lineare Optimierung.

Empfohlene Literatur:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Dantzig, G. B., Thapa, M. N.: Linear Programming 1 - Introduction. Springer Series in Operations Research. Springer-Verlag, New York, 1997, pp. xxxviii+435.
• Dantzig, G. B., Thapa, M. N.: Linear Programming 2 - Theory and Extensions. Springer Series in Operations Research. Springer-Verlag, New York, 2003, pp. xxvi+448.
• Lauritzen, N.: Undergraduate Convexity - From Fourier and Motzkin to Kuhn and Tucker. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2013, pp. xiv+283.
• Padberg, M.: Linear Optimization and Extensions. Second Edition. Vol. 12. Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999, pp. xxii+501.
• Luenberger, D. G., Ye, Y.: Linear and Nonlinear Programming. Fourth Edition. Vol. 228. International Series in Operations Research & Management Science. Springer, Cham, 2016, pp. xiv+546.

Die Vorlesung knüpft an die Lineare Optimierung an. Lineare Optimierungsprobleme werden in dem Sinne verallgemeinert, dass die Zielfunktion und die Restriktionen nicht mehr linear sein müssen. Die Klasse der nichtlinearen Optimierungsprobleme ist allerdings viel zu groß um dafür noch effiziente Lösungsverfahren bereitstellen zu können. Deshalb werden zusätzliche Voraussetzungen gestellt. Behandelt werden speziell strukturierte konvexe Optimierungsprobleme, die effizient lösbar und anwendungsrelevant sind.

Im ersten Abschnitt der Vorlesung werden Innere-Punkte-Verfahren - das sind Lösungsmethoden aus der nichtlinearen Optimierung - für lineare Optimierungsprobleme eingeführt. Im zweiten Abschnitt werden verschiedene Klassen von speziell strukturierten konvexen Optimierungsproblemen und deren Beziehung untereinander behandelt. Im dritten Abschnitt geht es um Anwendungen und um Modellierungsfragen. Im letzten Abschnitt wird die Globale Optimierung - das sind Aufgaben, die nicht mehr effizient gelöst werden können - in den Grundzügen vorgestellt.

Es handelt sich um eine Einführung mit dem Ziel einen Überblick über wichtige Themen und Konzepte der kontinuierlichen Optimierung zu erlangen. Zur Vertiefung bietet sich die Vorlesung Kontinuierliche Optimierung an, die jeweils im Folgesemester angeboten wird.

Empfohlene Literatur:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Lauritzen, N.: Undergraduate Convexity - From Fourier and Motzkin to Kuhn and Tucker. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2013, pp. xiv+283.
• Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, 2004, pp. xiv+716.
• Anjos, M. F., Lasserre J. B. (eds.): Handbook on semidefinite, conic and polynomial optimization. Vol. 166. International Series in Operations Research & Management Science. Springer, New York, 2012, pp. xii+960.

Optimierungsprobleme werden häufig als entweder kontinuierlich oder diskret klassifiziert. In der Kontinunierlichen Optimierung wird eine Zielfunktion über einem Kontinuum optimiert. In dieser Vorlesung wird diese Menge eine konvexe oder auch nicht konvexe Teilmenge des Rⁿ sein.
Für kontinuierliche Optimierungsprobleme werden Optimalitätsbedingungen, Dualitätstheorie und numerische Verfahren diskutiert. Insbesondere werden verallgemeinerte Konzepte von Differenzierbarkeit (Subdifferentiale) behandelt. Kontinuierliche Optimierung spielt eine wichtige Rolle in zahlreichen Anwendungen der Natur- und Sozialwissenschaften sowie im Ingenieur- und Finanzwesen.

Die Vorlesung knüpft an die Einführung in die Kontinuierliche Optimierung an, kann mit etwas zusätzlichem Aufwand aber auch ohne diese gehört werden. Als Grundlage wird die Lineare Optimierung empfohlen.

Empfohlene Literatur:

• Rockafellar, R. T.: Convex Analysis. No. 28. Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1970, pp. xviii+451.
• Borwein, J. M., Lewis, A. S.: Convex analysis and nonlinear optimization - Theory and examples. Vol. 3. CMS Books in Mathematics. Springer-Verlag, New York, 2000, pp. x+273.

 Die Vorlesung vermittelt Grundlagen und zentrale Konzepte und Algorithmen der diskreten Optimierung. Die Themen des Kurses umfassen grundlegende Probleme wie:

• kürzeste Wege
• maximale Flüsse in Netzwerken
• Minimalkostenflussproblem
• das Problem des Handlungsreisenden (Traveling Salesman Problem)
• ganzzahlige lineare Optimierung
• Optimierung auf Matroiden und der Greedy-Algorithmus

Besonderes Augenmerk liegt auf der Modellierung praktischer Anwendungen.

Als weiterführenden Kurs zu diesem Themenkomplex wird die Vorlesung 'Grundlagen der Algorithmik (Algorithmics)' von Professor Komusiewicz en empfohlen. Beide Veranstaltungen bauen nicht aufeinader auf.

Im Bachelorseminar Optimierung lernen die Studierenden sich selbständig in ein definiertes Thema der mathematischen Optimierung einzuarbeiten, dieses aufzubereiten und zu präsentieren. Empfohlen ist daher mindestens eine Lehrveranstaltung der mathematischen Optimierung, z. B. Lineare Optimierung, Einführung in die kontinuierliche Optimierung, Einführung in die diskrete Optimierung oder Praktische Mathematik und Modellierung: Optimierung, bereits absolviert zu haben. Während der Vorbereitung auf die Präsentation besteht die Möglichkeit individuelle Konsultationen wahrzunehmen um offene Fragen zu klären und Hilfestellungen zu erhalten. Eine schriftliche Ausarbeitung des eigenen Vortragsthemas zum Semesterende bietet die Möglichkeit das Verfassen wissenschaftlicher Texte nach wissenschaftlichten Standards zu üben. Somit ist das Bachelorseminar Optimierung eine ideale Vorbereitung auf das Schreiben einer Bachelorarbeit.

Die Vorlesung Praktische Optimierung ist eine anwendungsorientierte Ergänzung zu ersten Vorkenntnissen auf dem Gebiet der mathematischen Optimierung, die z. B. in einer der Vorlesungen Lineare Optimierung, Einführung in die kontinuierliche Optimierung oder Einführung in die diskrete Optimierung erlangt wurden. Ausgewählte Themen werden von den Studierenden erarbeitet und in der Vorlesung präsentiert. In Vorbereitung darauf besteht regelmäßig die Möglichkeit individuelle Konsultationen wahrzunehmen, jedoch liegt der Fokus auf der Selbständigkeit und Eigenverantwortlichkeit der Studierenden. Eine schriftliche Ausarbeitung des eigenen Vortragsthemas zum Semesterende bietet die Möglichkeit das Verfassen wissenschaftlicher Texte nach wissenschaftlichten Standards (z. B. in Vorbereitung auf das Schreiben einer Bachelorarbeit) zu üben.

Die Vortragsthemen variieren und umfassen die Modellierung von Anwendungsproblemen, das Lösen bestimmter Optimmierungsprobleme unter Verwendung von Software und die Implementierung von Optimierungsalgorithmen.

In der Vorlesung Praktische Mathematik und Modellierung: Optimierung werden Grundlagen verschiedener Bereiche der mathematischen Optimierung aus Anwendersicht erarbeitet. Viele Probleme der Logistik, Produktionsplanung und Finanzmathematik lassen sich als speziell strukturierte lineare oder konvexe Optimierungsprobleme formulieren. Die Studierenden lernen am Beispiel verschiedener Anwendungen die zugrundeliegenden Optimierungsprobleme und deren Eigenschaften kennen. Dabei werden die Inhalte weniger systematisch mathematisch präsentiert, sondern die Vorlesung hat das Ziel die Studierenden in der Modellierung von Optimierungsproblemen und der Anwendung von Optimierung zu schulen und ihnen einen möglichst breiten Überblick über Problemklassen und Verfahren zu geben. Vor diesem Hintergrund eignet sich die Veranstaltung auch für Interessenten ohne Vorkenntnisse in der mathematischen Optimierung. Gelehrt werden u. a.:

• Grundlagen der linearen Optimierung (Standardformen linearer Programme, Modellierungstechniken, Simplexalgorithmus, Dualität u. a.),
• Grundlagen allgemeiner Optimierungsprobleme (hinreichende und notwendige Optimalitätsbedingungen, KKT-Bedingungen, Lagrange-Dualität u. a.),
• Abstiegsverfahren,
• Klassen konvexer Optimierungsprobleme.

Empfohlene Literatur:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, 2004, pp. xiv+716.
• Jungnickel, D.: Optimierungsmethoden - Eine Einführung. Third Edition. Springer-Lehrbuch. Springer Berlin, Heidelberg, 2015, pp. xvi+279.
• Papageorgiou, M., Leibold, M., Buss, M.: Optimierung - Statische, dynamische, stochastische Verfahren für die Anwendung. Fourth Edition. Springer Berlin, Heidelberg, 2015, pp. xix+538.

Die Vorlesung Mathematische Modelle für Optimierungsprobleme beleuchtet Aspekte verschiedener Bereiche der mathematischen Optimierung aus Anwender- und Anwendungssicht heraus und eignet sich auch für Studierende ohne Vorkenntnisse auf dem Gebiet der mathematischen Optimierung. Der Fokus der Vorlesung liegt auf der Modellierung von Anwedungsproblemen als Optimierungsprobleme. Insbesondere sollen hierbei die Fähigkeiten vermittelt werden zu erkennen um welche Art von Optimierungsproblem es sich im konkreten Anwendungsfall handelt und welche Software zum Lösen infrage kommt. Die Inhalte der Vorlesung umfassen u. a.:

• Grundlagen der linearen Optimierung (Standardformen linearer Programme, Modellierungstechniken, Dualität u. a.),
• lineare Optimierung im Bereich der Graphentheorie (kürzeste Wege, Algorithmus von Ford, zulässige Potentiale, Maximalflussprobleme, Algorithmus von Ford und Fulkerson, Max-Flow-Min-Cut Dualität, Minimalkostenflussprobleme u. a.),
• Klassen konvexer Optimierungsprobleme.

Empfohlene Literatur:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Cook, W. J., Cunningham, W. H., Pulleyblanc, W. R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1998, pp. x+355.
• Ahuja, R. K., Magnanti, T. L., Orlin, J. B.: Network flows - Theory, algorithms and applications. Prentice Hall, Inc., Englewood Cliffs, NJ, 1993, pp. xvi+846.
• Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, 2004, pp. xiv+716.

Im Masterseminar Optimierung lernen die Studierenden sich selbständig in ein aktuelles Forschungsthema der mathematischen Optimierung einzuarbeiten, dieses aufzubereiten und zu präsentieren. Sie erhalten dafür zu Beginn des Semesters i. d. R. einen Artikel einer wissenschaftlichen Fachzeitschrift, mit dessen Inhalt sich auseinanderzusetzen ist. Empfohlen ist daher mindestens eine fortgeschrittene Lehrveranstaltung der mathematischen Optimierung, z. B. Vektoroptimierung oder Konvexe Analysis und nichtglatte Optimierung, bereits absolviert zu haben. Während der Vorbereitung auf die Präsentation besteht die Möglichkeit individuelle Konsultationen wahrzunehmen um offene Fragen zu klären und Hilfestellungen zu erhalten. Eine schriftliche Ausarbeitung des eigenen Vortragsthemas zum Semesterende bietet die Möglichkeit das Verfassen wissenschaftlicher Texte nach wissenschaftlichten Standards zu üben. Somit ist das Masterseminar Optimierung eine ideale Vorbereitung auf das Schreiben einer Masterarbeit.

Unterrichtssprache: Englisch

Konvexität ist eine grundlegende Eigenschaft in der Optimierung. Bei konvexen Optimierungsproblemen sind lokale und globale optimale Lösungen identisch, was diese Probleme besonders bedeutend macht. Darüber hinaus können viele spezifische Klassen von konvexen Optimierungsproblemen näherungsweise in polynomialer Zeit gelöst werden.

Dieser Kurs bietet ein systematisches Studium konvexer Mengen und konvexer Funktionen. Wir befassen uns mit konvexen Optimierungsproblemen und legen dabei einen besonderen Schwerpunkt auf die Entwicklung einer abstrakten Dualitätstheorie. Der Kurs setzt keine Differenzierbarkeit voraus; stattdessen arbeiten wir mit Subgradienten, die das Konzept der Ableitungen verallgemeinern.

Unterrichtssprache: Englisch

Empfohlene Litaratur:

• Bertsekas, D.: Convex Optimization Theory. Athena Scientific, 2009.
• Hiriart-Urruty, J.-B., & Lemaréchal, C.: Fundamentals of Convex Analysis. Springer-Verlag, 2001.
• Borwein, J. M.; Lewis, A. S.: Convex Analysis and Nonlinear Optimization. Springer-Verlag, 2006.
• Rockafellar, R. T.: Convex Analysis. Princeton University Press, 1970.

Die Vorlesung Semidefinite Optimierung und Approximation konvexer Mengen beschäftigt sich mit der Frage wie der Begriff der Konvergenz bzw. des Grenzwertes einer Folge reeller Zahlen auf Folgen von Mengen verallgemeinert werden kann. Dazu werden konkret Folgen abgeschlossener konvexer Mengen betrachtet und zwei Konvergenzbegriffe systematisch eingeführt. Für den Spezialfall beschränkter Folgen eignet sich der Hausdorff-Abstand, der gleichfalls eine Metrik auf dem Raum der nichtleeren kompakten Teilmengen des Rⁿ definiert, um Konvergenz von Mengenfolgen zu fassen. Bei nicht notwendigerweise beschränkten Folgen werden die Konvergenz bezüglich des Hausdorff-Abstandes auf die sog. Painlevé-Kuratowski-Konvergenz verallgemeinert und Zusammenhänge zwischen beiden Konzepten untersucht. Indem abgeschlossene konvexe Mengen im Rⁿ mit abgeschlossenen konvexen Kegeln im Rⁿ⁺¹ identifiziert werden, lässt sich der Raum der nichtleeren konvexen Teilmengen des Rⁿ sogar mit einer Metrik ausstatten.

Diese Konvergenzbegriffe werden verwendet um Algorithmen zu entwickeln, mit denen sich konvexe Mengen durch Polyeder approximieren lassen. Diese Algorithmen erfordern das Lösen spezieller konvexer Optimierungsprobleme. Damit sich diese noch praktisch lösen lassen, ist die Einschränkung auf bestimmte konvexe Mengen notwendig. Hier eignen sich sog. projizierte Spektraeder. Diese sind eng mit semidefiniter Optimierung verwandt, weshalb Grundlagen und Dualitätsaussagen derselben einer weitere zentrale Rolle in der Vorlesung einnehmen.

Es empfiehlt sich die Vorlesung im Anschluss an die Vorlesung Konvexe Analysis und nichtglatte Optimierung zu hören um bereits mit wichtigen Konzepten der konvexen Analysis vertraut zu sein. Dies ist aber keine Voraussetzung. Inhalte der Veranstaltung umfassen u. a.:

• Grundlagen der semidefiniten Optimierung (Standardformen semidefiniter Programme, schwache und starke Dualität, Anwendungen),
• Konvergenzbegriffe für Folgen abgeschlossener konvexer Mengen (Hausdorff-Konvergenz, Painlevé-Kuratowski-Konvergenz u.a.),
• Spektraeder und projizierte Spektraeder (Mengenkalkül für projizierte Spektraeder u. a.),
• Algorithmen zur polyedrischen Approximation projizierter Spektraeder.

Unterrichtssprache: Englisch

Empfohlene Literatur:

• Rockafellar, R. T., Wets, R. J.-B.: Variational analysis. Vol. 317. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1998, pp. xiv+733.
• Todd, M. J.: Semidefinite Optimization. Vol. 10. Acta Numerica. 2001, pp. 515-560.
• Rockafellar, R. T.: Convex Analysis. No. 28. Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1970, pp. xviii+451.
• Blekherman, G., Parrilo, P. A., Thomas, R. R. (eds.): Semidefinite optimization and convex algebraic geometry. Vol. 13. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013, pp. xx+476.

Lineare Vektoroptimierungsprobleme sind lineare Optimierungsprobleme mit einer vektorwertigen Zielfunktion. Solche Probleme kommen in Anwendungen vor bei denen mehrere Zielfunktionen simultan optimiert werden sollen. Solche Anwendungen gibt es vor allen in den Wirtschafts- und Ingenierwissenschaften. Es gibt weitere Anwendungen, die als solche weniger offensichtlich sind. Zum Beispiel in den Bereichen Algorithmische Geometrie bei der Brechnung von konvexen Polyedern, in der multivariaten Statistik bei der Berechnung von Quantilen, sowie zur Gewinnung bestimmter Ungleichungen in der Informationstheorie. Themen der Vorlesung umfassen:

• Problemformulierung und Lösungskonzepte
• Anwendungen
• Dualität
• Lösungsverfahren

Die Vorlesung knüpft an aktuelle Forschungsfragen an. Als Voraussetzung werden Kenntnisse in Linearer Optimierung empfohlen.

Unterrichtssprache: Englisch

Empfohlene Literatur:

• Ehrgott, M.: Multicriteria Optimization. Springer, 2005
• Luc, D.T.: Multiobjective Linear Programming. Springer, 2016
• Löhne, A.: Vector Optimization with Infimum and Supremum. Springer, 2011
• recent papers on the topic

 Mengenoptimierung erweitert die Vektoroptimierung durch die Einbeziehung einer mengenwertigen Zielfunktion. Speziell erweitert die polyedrische konvexe Mengenoptimierung die Lineare Vektoroptimierung. Mengenoptimierung ist ein relativ neues Feld, und dieser Kurs behandelt aktuelle Entwicklungen in diesem Bereich.

Die Vorlesung auf den Konzepten des Kurses Lineare Vektoroptimierung auf; daher wird empfohlen, diesen Kurs zuerst zu belegen. Die behandelten Themen umfassen:

• Problemstellung und Lösungskonzepte
• Anwendungen
• Lösungsmethode

Unterrichtssprache: Englisch

Empfohlene Literatur:

• Aktuelle Fachartikel zu diesem Thema