Convexity and Optimization 2020

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 DescentLecture 7
min-cut using GDLecture 8
min-cut using GD (continued)Lecture 9
multiplicative weights update (MWU) and how to solve LPs using itLecture 10
Mirror DescentLecture 11
Approximate Caratheodory’s theorem using Mirror DescentLecture 12
Interior point methodLecture 13
Solving LPs using the Interior point methodLecture 14
Self concordant barriersLecture 15
Cutting plane methodsLecture 16
(Fast) polytope intersectionLecture 17
Brunn-Minkowsi’s inequality and Grünbaum’s theoremLecture 18
(February 16 and 18)
Isoperimetric inequalitiesLecture 19
(March 2)
Gaussian correlation inequalitiesLecture 20
(March 9)

Textbooks and additional references: