Institute for Web Science and Technologies · Universität Koblenz - Landau
Institute WeST

Proseminar "Optimierungsalgorithmen"

[zur Übersicht]

Sommersemester 2019

Überblick

Optimierungsprobleme sind eine häufig auftretende Problemklasse in vielen Anwendungsproblemen und viele klassische Probleme in der Informatik können als Optimierungsprobleme repräsentiert werden. In der klassischen (mathematischen) Optimierung geht es um die Maximierung oder Minimierung einer sogenannten Zielfunktion unter Berücksichtigung von Nebenbedingungen, die in Form von Gleichungen oder Ungleichungen über den beteiligten Variablen dargestellt werden. Diese allgemeine Form deckt viele wichtige Spezialfälle der Optimierung ab, wie etwas die lineare Optimierung, bei der alle Terme linear sein müssen, der kombinatorischen Optimierung, bei der alle Variablen einen diskreten Wertebereich haben, sowie der quadratischen Optimierung, der konvexen Optimierung und vielen mehr. In diesem Seminar werden grundlegende algorithmische Techniken diskutiert, um Optimierungsprobleme verschiedenster Formen zu lösen, angefangen vom Simplexverfahren zur Lösung linearer Optimierungsprobleme, bis zu evolutionären Algorithmen, die u. a. beliebige kombinatorische Probleme lösen können.

Seminarthemen

Jedes Seminarthema hat eine bestimmte Klassen von Algorithmen im Fokus.

  1. Einführung in Optimierungsprobleme [1, Kapitel 1], [11], [9, Kapitel 1-2]
  2. Das Simplexverfahren [2, Kapitel 29], [11, Kapitel 11], [10, Kapitel 10.10], [9, Kapitel 13]
  3. Das Newtonverfahren [9, Kapitel 3]
  4. Quasi-Newtonverfahren [9, Kapitel 3+8]
  5. Innere-Punkt-Verfahren [10, Kapitel 10.11], [9, Kapitel 14]
  6. Gradientenverfahren [3, 12], [9, Kapitel 5]
  7. Tabu-Suche [6]
  8. Simulierte Abkühlung [7], [10, Kapitel 10.12]
  9. Ameisenalgorithmen [4, 5]
  10. Evolutionäre Algorithmen [8]

Jedes Thema kann von 1-2 Studierenden bearbeitet werden. Die genannten Referenzen stellen nur Einstiegspunkte in eine Literaturrecherche dar, es wird erwartet, dass weitere Literatur zur Bearbeitung des Themas einbezogen wird (insbesondere wenn ein Thema von 2 Studierenden bearbeitet wird). In jedem Fall sollte jeder Seminarteilnehmer eine allgemeine Einführung zu Optimierung lesen (beispielsweise Kapitel 1-2 in [9]).

Literatur

  1. Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
  3. H.B. Curry. The method of steepest descent for nonlinear minimization problems. Quart. Appl. Math., 2:258-261, 1944.
  4. M. Dorigo, G. Di Caro, and L. M. Gambardella. Ant algorithms for discrete optimization. Artificial Life, 5(2):137-172, 1999.
  5. Marco Dorigo. Ant colony optimization: An introduction. Tutorial given at the Fifth International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 2006).
  6. F. Glover and M. Laguna. Tabu Search. Kluwer Academic Publishers, 1997.
  7. S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671-680, 1983.
  8. Volker Nissen. Einführung in Evolutionäre Algorithmen. Vieweg, 1997.
  9. Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer-Verlag, 1999.
  10. WH Press, SA Teukolsky, WT Vetterling, and BP Flannery. Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press, 2007.
  11. Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, 1998.
  12. Ya-xiang Yuan. Step-sizes for the gradient method. AMS/IP Studies in Advanced Mathematics, 42(2), 1999.

Termine

Vorbesprechung: 13.02.2019 10:15 (Raum B.013)

Proseminar: Dienstags 10:15-11:45 Uhr (Raum C.209), erste Veranstaltung am 09.04.2019

Teilnahme

Um an dem Proseminar teilzunehmen ist eine Teilnahme an der Vorbesprechung am 13.02.2019 10:15 (Raum B.013) erforderlich. Wenn Sie Interesse haben an dem Proseminar teilzunehmen, kündigen Sie dies bitte vorab in einer informellen E-Mail an PD Dr. Matthias Thimm an.

Von den Teilnehmern wird eine Präsentation (ca. 30 Minuten pro Studierender) über eines der oben genannten Themen erwartet. Im Anschluss an das Proseminar ist eine Ausarbeitung über das Seminarthema (ca. 12 Seiten pro Studierender) abzugeben.

Bitte beachten Sie bei der Erstellung der Präsentation und der Ausarbeitung folgende allgemeine Richtlinien (nur in Englisch verfügbar): pdf

Veranstaltung in KLIPS: Proseminar

Lehrende

  • thimm@uni-koblenz.de
  • Wissenschaftlicher Mitarbeiter
  • B 112
  • +49 261 287-2715