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.
- 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
- 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.
Remark: Some lecture notes are updated after the class.
- 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: Gradient Descent, Mirror Descent, and Accelerated Gradient Descent
- Jan 26: Coordinate Descent and Stochastic Descent
- Jan 31: Preconditioning
- Feb 02: Example: Maximum Flow Problem
Algorithms for Linear Systems
- Feb 07: Leverage Score & Uniform Sampling Method
- Feb 09: Lewis Weight
- Feb 14: How does MATLAB solve Ax=b?
- Feb 16: Sparse Cholesky Decomposition
Interior Point Methods
- Feb 21: Homotopy Method
- Feb 23: Newton Method & Self-Concordant Barrier
- Feb 28: Entropic Barrier
- Mar 02: Lee-Sidford Barrier
- Mar 07: Quasi-Newton Method
- Mar 09: ???