Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Hauptseminar (SS'07)

Algorithmische Aspekte nichtlinearer Optimierung

• Leitung:
  Dmytro Chibisov
  Stefan Eckhardt
  
  
• Bereich:
  2 SWS Hauptseminar im Bereich Informatik III (Theoretische Informatik)
  

• Zeit und Ort:
  Donnerstag, 14:15 - 15:45, MI 03.11.018
  

• Schein:
  Einen Seminarschein erhält, wer einen Vortrag gehalten hat und regelmäßig am Seminar teilgenommen hat.

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik

• Voraussetzungen: 
  
  Voraussetzung für die Teilnahme am Hauptseminar sind neben Interesse an Algorithmen, Komplexität und mathematischen Fragestellungen auch Englischkenntnisse, die ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sein sollen.

• Zusammenfassung:
  
  Zahlreiche Anwendungen aus der Wissenschaft und Industrie lassen sich als Optimierungsprobleme auffassen, deren Lösungen effiziente und stabile numerische Algorithmen erfordern. Im Gegensatz zur klassischen numerischen Analysis, bei der die Komplexität der einzelnen Algorithmen betrachtet wird, werden wir uns im Hauptseminar in erster Linie mit der Frage der algorithmischen Komplexität verschiedener Klassen von Optimierungsproblemen beschäftigen, und zwar unabhänging von der konkreten Lösungsmethode. D.h. es wird die Frage nach unteren Schranken für alle Methoden, welche Probleme aus der Klasse mit einer bestimmten Genauigkeit lösen, im Mittelpunkt stehen. Diese Betrachtungsweise, die ursprüglich aus der diskreten Komplexitätstheorie stammt, erlaubt einerseits die Analyse und die Verbesserung der Optimierungsalgorithmen für einzelne Problemklassen. Andererseits bedarf es jedoch einigen Spezialisierungen, da man Optimierung über reelen Zahlen betrachtet und somit das diskrete Modell zu Gunsten eines kontinuierlichen anpasst.
  
  Da es noch kein umfassendes Buch zu diesem Thema gibt, basieren die meisten Themen in der Regel auf aktuellen Forschungsarbeiten. Wegen der interessanten Kombination aus Theorie und Praxis bieten sich bei einigen Themen auch Anknüpfungspunkt für Bachelor- oder Diplomarbeiten an.
  
  
• Vorträge:
  
  Do., 21. Juni
  
  

  14:00-15:00	Vivija Ceprkalo "Simplex Algorithm and its Complexity"
  15:15-16:15	Johannes Mittmann "Polynomial Time Algorithms for Linear Programming"

  
  
  
• Inhalt:
  
  
  I. Introducation
  
  1. Computational Models, Complexity, Oracles  and Numerical Computation ([1] Chapters 1,2; [2] Chapter 1, 2)
  
  II. Basic Algorithms and Complexity
  
  2. Simplex Algorithm and its Complexity ([22] Chapters 2.1-2.7; [19]; [8]; [11]; [21] Chapter 15)
  
  3. Polynomial Time Algorithms for Linear Programming ([1] Chapters 3,4; [22] Chapters 2.8-2.9; [9]; [10])
  
  4. Nonlinear Global Optimization in the Black-Box Model and Intractability ([15]; [20]; [23]; [3] Chapter 1; [18])
  
  III. Nonlinear Optimization
  
  5. Complexity of Newton Method ([4], [5], [6])
  
  6. Minimization of Polynomial Time Computable Real Functions and P?=NP ([2] Chapters 3; [16])
  
  7. Computational Complexity of Roots of Real Functions ([2] Chapter 4; [17])
  
  8. Quadratic Programming is NP-complete ([13]; [25])
  
  9. Polynomial Approximations for Quadratic Programming ([24], [14])
  
  10. Optimal Control is NP-complete ([2] Chapter 9; [7])
  
  IV. Combinatorial Optimization
  
  11.  Polynomial Time Combinatorial Optimization using Ellipsoid Method and Basis Reduction
  
  
  

• Literatur:
  
  [1] M. Groetschel, L. Lovasz, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1998
  [2] K. Ko: Complexity Theory of Real Functions, Birkhaeuser, 1991
  [3] A. S. Nemirovsky, D. B. Yudin: Problem Complexity and Method Efficiency in Optimization, John Wiley & Sons, 1983
  [4] H. T. Kung: The Complexity of Obtaining Starting Points for Solving Operator Equations by Newton's Method, in Analytic Computational Complexity, J. F. Traub, ed., Academic Press, New York, 1976, pp. 35–57.
  [5] C. A. Micchelli, W.L. Miranker: High Order Search Methods for Finding Roots, J. ACM 22, 1975, pp. 51-60
  [6] J. Hackl, H. J. Wacker, W. Zulehner: An efficient step size control for continuation methods, BIT Numerical Mathematics, 2005, pp. 475-485
  [7] C. H. Papadimitriou, J. Tsitsiklis: Intractable problems in control theory, SIAM J. Contr. Optim., 24, pp. 639-654
  [8] D. A. Spielman, S.-H. Teng: Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time, in STOC'01, 2001, pp. 296-305
  [9] L.G. Khachiyan: A polynomial time algorithm in linear programming, in Doklady Akademiya Nauk SSSR,  1979, pp. 1093-1069
  [10] N. Karmarkar: A new polynomial time algorithm for linear programming, Combinatorica 1984, pp. 373-395
  [11] S. Smale: On the average number of steps in the simplex method of linear programming. Mathematical Programming, 1983, pp. 241-262
  [12] L. Jaulin, M. Kieffer, O. Didrit, E. Walter: Applied Iterval Analysis, Springer-Verlag, 2001
  [13] S. A. Vavasis: Quadratic Programming is in NP. Info. Proc. Lett, 1990, pp. 73-77
  [14] S. A. Vavasis: Polynomial Time Weak Approximation Algorithms for Quadratic Programming, preprint, 1992
  [15] R. Horst, H. Tuy: Global Optmization: Determinisic Approaches, Springer-Verlag, 1990
  [16] K. Ko: Continuous optimization problems and a polynomial hierarchy of real functions, J. Complexity (1), 1985, pp. 221-232
  [17] K. Ko: Computational complexity of roots of real functions, in Proc. 30th IEEE Symposium on Foundations of Computer Science, pp. 204-209
  [18] V. Ivanov: Optimal Algorithms of Minimization of Certain Classes of Functions, Kibirnetica, 1972, pp. 81-94
  [19] J. H. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method University of Colorado at Denver, 1997
  [20] W. D. Smith: Complexity of Optimization, 2000 (http://citeseer.ist.psu.edu/smith00complexity.html)
  [21] L. Blum, F. Cucker, M. Shub, S. Smale: Complexity and Real Computation, Springer-Verlag, 1998
  [22] G. L. Nemhauser, A. H. G. Rinnoy Kan, M. J. Todd: Optimization, Vol. 1, North-Holland, 1989
  [23] A. Neumaier: Complete Search in Continuous Global Optimization and Constraint Satisfaction, 2004, Acta Numerica, Cambridge University Press
  [24] S. Vavasis: Approximation Algorithms for Indefinite Quadratic Programming, 1992, Mathemacial Programming, pp. 279 - 311
  [25] S. Vavasis: Nonlinear Optimization. Complexity Issues, 1991, Oxford Science Publications

• Ablauf der Vorbereitung:
  

  Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

  bis 5 Wochen vor dem Vortrag		erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
  bis 3 Wochen vor dem Vortrag		Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
  bis 1 Woche vor dem Vortrag		Probevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
  bis 2 Wochen nach dem Vortrag		fertige Ausarbeitung abgeben.

• Hinweise zur Anfertigung einer Seminararbeit:
  

  	Die Seminararbeiten werden nach der letzten Seminarveranstaltung online zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  	Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden. Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden. Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden) Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
  	Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
  	LaTeX Kochbuch RBG-Seite zu LaTeX
  	Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
  	Informationen zur Installation von LaTeX unter Windows finden Sie hier.

• Hinweise zur Gestaltung der Vorträge:
  

  	Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)