Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

Lecture 1 (Jan 11): introduction [pdf] [one]
  • course information and overview
  • convex sets
Lecture 2 (Jan 13): convex functions [pdf] [one]
  • first and second order conditions
  • examples, inequalities
Lecture 3 (Jan 18): dual sets and functions [pdf] [one]
  • separating hyperplane theorems
  • polar sets, dual norms, conjugate functions
Lecture 4-5 (Jan 20, 25): dual programs [pdf] [one]
  • convex programs, dual programs
  • strong duality, optimality conditions
Lecture 6 (Jan 27): John ellipsoid [pdf] [one]
  • maximum inscribed ellipsoid, Dikin ellipsoid
Lecture 7 (Feb 1): gradient descent [pdf] [one]
  • smoothness, strong convexity, convergence
Lecture 8 (Feb 3): minimum cut [pdf] [one]
  • gradient descent with projection constraints
Lecture 9 (Feb 8): multiplicative weight update method [pdf] [one]
  • online expert model, solving linear program
Lecture 10 (Feb 10): mirror descent [pdf] [one]
  • projected gradient descent, Bregman divergence
  • mirror descent, multiplicative update
Lecture 11 (Feb 15): approximate Caratheodory theorem [pdf] [one]
  • optimization proof using mirror descent
Lecture 12 (Feb 17): interior point method [pdf] [one]
  • Newton method, barrier method, maximum flow
Lecture 13 (Mar 1): linear programming [pdf] [one]
  • analysis of interior point method
Lecture 14 (Mar 3): self-concordant barrier [pdf] [one]
  • self-concordance, beyond log-barrier
Lecture 15 (Mar 8): cutting plane methods [pdf] [one]
  • center of gravity, ellipsoid, polytope
Lecture 16 (Mar 10): polytope intersection [pdf] [one]
  • reduction to cutting plane, combinatorial applications
Lecture 17 (Mar 15): geometric decent [pdf] [one]
  • accelerated gradient descent
Lecture 18 (Mar 17): introduction to convex geometry [pdf] [one]
  • overview, Gaussian, volumes
  • Brunn-Minkowski inequality, isoperimetric inequality
Lecture 19 (Mar 22): Brunn-Minkowski inequality [pdf] [one]
  • Prepoka-Leindler inequality, Grumbaum's theorem
Lecture 20 (Mar 24): measure concentration [pdf] [one]
  • approximate isoperimetric inequality: sphere, Gaussian
Lecture 21 (Mar 29): log-concavity [pdf] [one]
  • examples, operations, inequalities
Lecture 22 (Mar 31): optimization applications [pdf] [one]
  • partial integral point, discrepancy minimization
  • isotropy, convex programs by random walks
Lecture 23 (Apr 5): random sampling in convex body [pdf] [one]
  • random walks, ball walk
  • conductance, approximating volume
Lecture 24 (Apr 7): expansion in convex body [pdf] [one]
  • localization lemma, isoperimetric inequality
  • discussion, further references