TU Darmstadt
| Home      | FB 4      | TU Darmstadt 
Research
Staff members
Projects
Jobs and Scholarships
Events
Previous Seminars
Publications
Contact
How to find us
Imprint
Vorlesung "Innere-Punkte-Verfahren der konvexen Optimierung" (Prof. Dr. Stefan Ulbrich)

Vorlesung

Innere-Punkte-Verfahren der konvexen Optimierung

Prof. Dr. Stefan Ulbrich

Sommersemester 2006



Vorlesungstermin:

Donnerstag,  16:15 - 17:55 Uhr (ab 20.4.)   in   S103/107 


Übungstermin:

Mittwoch,  16:15 - 17:55 Uhr (14tägl. ab 26.4.)   in   S103/111 


Skriptum:

    Stand 20.7.2006: PDF,   PS


Übung:

    Blatt 1: PDF,   PS    Lösungsvorschlag: PDF   PS

    Blatt 2: PDF,   PS    Lösungsvorschlag: PDF   PS

    Blatt 3: PDF,   PS    Lösungsvorschlag: PDF   PS

    Blatt 4: PDF,   PS    Lösungsvorschlag: PDF   PS

    Blatt 5: PDF,   PS    Lösungsvorschlag: PDF   PS

    Blatt 6: PDF,   PS


Inhalt der Vorlesung:

Die Vorlesung soll eine allgemeinverständliche Einführung in moderne Innere-Punkt-Verfahren der konvexen Optimierung geben. Die konvexe Optimierung bildet eine wichtige Teildisziplin der nichtlinearen Optimierung und hat eine Vielzahl wichtiger Anwendungen (robuste lineare Optimierung, robuste Tragwerkoptimierung, Filterdesign, Portfoliooptimierung, Greifkraftoptimierung bei Robotern,...). In den letzten 15 Jahren wurde die konvexe Optimierung durch die Entwicklung neuartiger Innere-Punkt-Methoden revolutioniert, die eine effiziente Lösung sehr großer konvexer Optimierungsprobleme erlauben. Beginnend mit Innere-Punkt Methoden für lineare Optimierung stellt diese Vorlesung moderne Innere-Punkt-Verfahren für konvexe Optimierungsprobleme vor. Neben der Behandlung allgemeiner konvexer Optimierungsprobleme gehen wir auf die effiziente algorithmische Lösung wichtiger Teilklassen der konvexen Optimierung ein (Second-Order Cone Programming, semidefinite Optimierung) und diskutieren Anwendungsbeispiele. Numerische Aspekte bei der Implementierung von Innere-Punkt Methoden werden ebenfalls angesprochen.

Themen der Vorlesung:

  • Innere-Punkt-Methoden für lineare Optimierung
    (u.a. primal-duale Pfadverfolgungsmethoden, Komplexität, superlineare Konvergenz)
  • Erweiterung auf konvexe quadratische Optimierungsprobleme
  • Innere-Punkt Methoden für allgemeine konvexe Optimierungsprobleme
    (Selbstkonkordanz und das Newton-Verfahren, Barrierefunktionen, Pfadverfolgungsmethoden)
  • Second-Order Cone Programming und Anwendungen
  • Semidefinite Programmierung und Anwendungen

Literatur:

  • S.J. Wright: Primal-Dual Interior Point Methods; SIAM, Philadelphia, 1997.
  • Y. Nesterov, A. Nemirovski: Interior-Point Polynomial Algorithms in Convex Programming; SIAM, Philadelphia, 1994.
  • J. Renegar: A Mathematical View of Interior-Point Methods in Convex Optimization; SIAM, Philadelphia, 2001.
  • Y. Ye: Interior Point Algorithms: Theory and Analysis; Wiley-Interscience, New York, 1997.


Bedingung zur Vergabe eines Übungsscheines:

    40 % der Hausaufgabenpunkte.

Modulprüfung für Masterstudiengang:

    Mündliche Prüfung.


Vorlesungsbegleitende Software, aktuelle Software und Literatur zu Innere-Punkt-Verfahren:

    MATLAB-Routinen und Beispiele zur Vorlesung werden im Laufe der Vorlesung zur Verfügung stehen.
  • Decision Tree for Optimization Software (insbesondere LP-, QP-, SDP/SOCP- bzw. NLP-Löser) von H.D. Mittelmann und P. Spellucci
    Eine nützliche Sammlung verfügbarer Löser unter anderem für Lineare, Quadratische, Semidefinite und Second-Order Cone sowie konvexe Nichtlineare Programmierung mit Links zur Homepage der jeweiligen Software.
    Die Sammlung enthält eine Reihe von Innere-Punkt-basierten Lösern, unter anderem in MATLAB, C/C++ bzw. F77, oder auch als Binärversion für einige Unix-Varianten und Win9x.   

  • Interior-Point Methods Online
    Archiv aktueller Arbeiten zu Innere-Punkt-Methoden, Links zu Innere-Punkt-Software.