CSE 599: Interplay between Convex Optimization and Geometry

In this course, we cover several frameworks for convex optimization, including, first-order methods, cutting plane methods and interior point methods. Besides covering some basic algorithms in those frameworks, we explain the geometry picture behind many of these algorithms.

Administrative Information:

  • Instructor: Yin Tat Lee
  • Office Hours: By appointment, email me at yintat@ignoreme-uw.edu
  • Lectures: Wed, Fri 3:00-4:20 at EEB 037

Schedule:

  • Jan 03: Introduction. Note

Cutting Plane Methods

  • Jan 05: Ellipsoid Method and Reductions Between Convex Oracles. Note
  • Jan 10: Composite Problem via Duality. Note
  • Jan 12: Marginal of Convex Set. Note
  • Jan 17: John Ellipsoid. Note
  • Jan 19: Geometric Descent. Note

First Order Methods

  • Jan 24: Discussion on First Order Methods. Note
  • Jan 26: Gradient Mapping and First Order Methods. Note
  • Jan 31: Stochastic Methods. Note
  • Feb 02: Case Study – Maximum Flow Problem. Note

Algorithms for Linear Systems

  • Feb 07: Overview & Leverage Score. Note
  • Feb 09: There is a mistake in this lecture. I will fix it by submitting a paper.
  • Feb 14: Cholesky Decomposition: How does MATLAB solve Ax=b for sparse symmetric A? Slide, Note, Survey
  • Feb 16: Sparse Cholesky Decomposition. Note

Interior Point Methods

  • Feb 21: How to solve Linear Program in both theory and practice? Note, Code
  • Feb 23: Newton Method & Self-Concordant Barrier. Note
  • Feb 28: Entropic Barrier. Note
  • Mar 02: Lee-Sidford Barrier. Note

Other Methods

  • Mar 07: How to solve ODE? Note
  • Mar 09: The Exponentially Convergent Trapezoidal Rule. Note, Survey