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 at uw dot edu.
  • Lectures: WF 3:00-4:20 at EEB 037
  • Course evaluation: 2 homework (50%), final project (50%)
  • Mailing list: https://mailman1.u.washington.edu/mailman/listinfo/cse599s_wi18

Assignments:

Announcements

  • Jan 21: Assignment 1 is posted.
  • Jan 15: Assignment 1 is posted.
  • Jan 3: I corrected the statement of the open problem in the lecture note 1.
  • Jan 1: The schedule is updated. Due to time constraints, the sampling part is removed and replaced by an optional reading. Feel free to ask me any question on the survey.

Tentative Schedule:

Remark: Some lecture notes are updated after the class.

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) (Somehow that day I used One Note instead of latex.)
  • 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: Lewis Weight and Inverse Maintenance (Note)
  • 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
  • Mar 02: Lee-Sidford Barrier

Other Methods

  • Mar 07: ???
  • Mar 09: ???

Related CS Theory Courses: