Konvexe Optimierung (WS 2020/21)

Lecturer
Prof. Dr. Frank Vallentin

Coordination of the Exercise Sessions
Dr. Marc Zimmermann, Greta Fischer

Sprache/Language
Übungsaufgaben und die Abschlussklausur können wahlweise in Englisch oder in Deutsch bearbeitet werden.
The course will be organized in English. Exercises and the final exam can be submitted either in German or in English.

Contents
In modern „Convex Optimization“ the theory of semidefinite optimization plays a central role. Semidefinite optimization is a generalization of linear optimization, where one wants to optimize linear functions over positive semidefinite matrices restricted by linear constraints. A wide class of convex optimization problems can be modeled using semidefinite optimization. On the one hand, there are algorithms to solve semidefinite optimization problems, which are efficient in theory and practice. On the other hand, semidefinite optimization is a tool of particular usefulness and elegance.

The aim of this course is to provide an introduction to the theory of semidefinite optimization, to algorithmic techniques, and to mathematical applications in combinatorics, geometry and algebra.

Literature / Extended lecture notes
Monique Laurent, Frank Vallentin -  A Course on Semidefinite Optimization (updated: January 4, 2021)

Week plan

  1. Week (3.11.): Introduction and convexity recap (Appendix A)
  2. Week (10.11.): Conic optimization (Chapter 2)
  3. Week (17.11.): The cone of positive semidefinite matrices (Appendix B)
  4. Week (24.11.): No lecture (due to move of the group)
  5. Week (1.12.): Eigenvalue optimization and convex spectral functions (Chapter 1.2, Chapter 1.3, Chapter 7.1)
  6. Week (8.12.): Optimization with ellipsoids (Chapter 7.2, Chapter 7.3)
  7. Week (15.12.): The ellipsoid method (Chapter 3)
  8. Week (12.1): Approximating MAXCUT (Chapter 5.1, Chapter 5.2, Chapter 5.3.1, Chapter 5.3.2)
  9. Week (19.1.): Grothendieck inequalities (Chapter 5.3.5, Chapter 6.2)
  10. Week (26.1.): Graph coloring and independent sets (Chapter 4.1.1, Chapter 4.3.1, Chapter 4.4.1, Chapter 4.6)
  11. Week (2.2.): Packings on the sphere (Chapter 10.1, Chapter 10.2, Chapter 10.3, Chapter 10.5, Chapter 10.6)
  12. Week (9.2.): Examination week

Lectures
Tuesday 8.15-9.45 (zoom)
Friday 8.15-9.45 (zoom)

Exercise Sessions
Monday 8.00-9.30 (zoom) or 14.00-15.30 (zoom)

Exercises

Sheet 1Sheet 2 Sheet 3
Sheet 4Sheet 5Sheet 6 (Abgabe: 8.1.2021)
Sheet 7Sheet 8Sheet 9
Sheet 10

Forum
speakup

Fragenliste zur Vorbereitung auf die mündliche Prüfung