Description
The main goal of the study group is to understand how continuous optimization techniques can be used to tackle discrete combinatorial optimization problems. We will mostly follow Lap Chi Lau’s excellent course notes available here .
Schedule
- Tuesdays 1.15 pm – 2.45 pm (via Zoom)
- Thursdays 1.15 pm – 2.45 pm (via Zoom)
Recordings
Lecture videos can be found here.
Emailing list for announcements
To receive announcements related to this study group please subscribe to emailing list by sending an email to [email protected]
Detailed schedule
| convex sets and ellipsoids | Lecture 1 | |
| convex functions – first and second order conditions | Lecture 2 | |
| dual sets and dual norms and separating hyperplane theorems | Lecture 3 | |
| conjugate functions -dual programs and weak duality | Lecture 4 | |
| strong duality (assuming Slater’s condition) – complementary slackness and KKT conditions | Lecture 5 | |
| John’s Theorem – Dikin ellipsoid | Lecture 6 | |
| Gradient Descent | Lecture 7 | |
| min-cut using GD | Lecture 8 | |
| min-cut using GD (continued) | Lecture 9 | |
| multiplicative weights update (MWU) and how to solve LPs using it | Lecture 10 | |
| Mirror Descent | Lecture 11 | |
| Approximate Caratheodory’s theorem using Mirror Descent | Lecture 12 | |
| Interior point method | Lecture 13 | |
| Solving LPs using the Interior point method | Lecture 14 | |
| Self concordant barriers | Lecture 15 | |
| Cutting plane methods | Lecture 16 | |
| (Fast) polytope intersection | Lecture 17 | |
| Brunn-Minkowsi’s inequality and Grünbaum’s theorem | Lecture 18 (February 16 and 18) | |
| Isoperimetric inequalities | Lecture 19 (March 2 and 4) | |
| Gaussian correlation inequalities | Lecture 20 (March 9 and 11) |
Textbooks and additional references:
- Convex Optimization by Boyd and Vandenberghe
- Convex Optimization: Algorithms and Complexity by Sebastian Bubeck
- A similar course with excellent lecture notes given at TU Berlin