Seminar Mathematics and Computation: Convex Optimization (Summer 2025)

Type:	Seminar
Programs:	MSc CS, Math
Organizers:	Vladimir Lysikov, Michael Walter
Time and Place:	Mondays 16:00-18:00, MC 1.84
First meeting:	11.04.2025
Credits:	3-5 CP
Contact time:	2 SWS
Language:	English
Course number:	211136
Links:	Registration

This is a seminar series whose theme changes every term. It should be of particular interest to Master’s students of computer science and mathematics. We particularly recommend it as preparation for a thesis project.

This term, the topic will be Convex Optimization.

Themes of past semesters:

• Summer 2024: Tensor Ranks and Tensor Invariants

• Summer 2023: Algebra, Algorithms, Complexity

How can I join?

To apply for this seminar, please see the Moodle course of the faculty.

Required prior knowledge

The seminar requires a strong interest and background in theoretical computer science and mathematics.

Description

Many problems can be phrased as optimization problems, and hence optimization algorithms are employed widely in theory and practice, in all areas of science, technology, and economics. This seminar focuses on the theory of convex optimization, which is concerned with a class of particularly well-behaved optimization problems for which an exact solution can be found efficiently (a seminal result in theoretical computer science). We will discuss basic properties of convex functions, important algorithms and their convergence, and various applications of convex optimization, including some examples where the convexity of the problem is not obvious from its immediate description.

Topics

1. Basic notions of convexity: convex combinations, convex sets, convex and concave functions, uniqueness of extremal values

2. Oracles for convex constraints, Ellipsoid method and polynomial solvability of linear programming
   • A. Nemirovski. Introduction to Linear Optimization, §6.2-6.3
   • B. Aspvall, R. E. Stone. Khachiyan’s Linear Programming Algorithm
   • Additional materials:
     • A. Juditsky. Ellipsoid algorithm (Video)
     • R. O’Donell. The Ellipsoid Algorithm (Video)
3. Semidefinite programming
   • J. Watrous. Semidefinite Programming (theory) + Semidefinite programs for fidelity and optimal measurements (quantum information applications)
   • Additional materials:
     • L. Lovász. Semidefinite Programs and Combinatorial Optimization
     • P. Parillo. Semidefinite Programming. Chapter 2 of Semidefinite Optimization and Convex Algebraic Geometry
4. Matrix scaling, Sinkhorn’s algorithm
   • M. Idel. A review of matrix scaling, Sections 1-3 and 7.
   • N. Linial, A. Samorodnitsky, A. Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
   • Additional material:
     • A. Wigderson. Optimization, Complexity and Math (or, can we prove P != NP using Gradient Descent) (Video)
5. Interior point methods
   • N. Vishnoi. Algorithms for Convex Optimization, Chapters 9-11.
   • A. Nemirovski, M. J. Todd. Interior-point methods for optimization
   • Additional materials:
     • A. Nemirovski. Interior point polynomial methods in Convex Programming
6. Convex cones, conic programming, duality for conic programming
   • A. Ben-Tal, A. Nemirovski. Lectures on Modern Convex Optimization, Chapter 2.
   • G. Farina. Conic Optimization (lecture notes)
7. Sum of Squares (SOS) hierarchy for polynomial optimization
   • D. Kunisky. Lecture notes on Sum-of-Squares optimization, Chapters 1 and 3.
   • Additional materials:
     • P. Parillo. Polynomial Optimization, Sums of Squares, and Applications. Chapter 3 of Semidefinite Optimization and Convex Algebraic Geometry
     • M. Laurent. Sums of squares, moments and applications in polynomial optimization (Video)

← Back