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
- Assignments will be submitted via Canvas.
- Assignment 1 is due on Jan 31.
- Assignment 2 is due on Mar 2.
- 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.
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: 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
- Mar 07: ???
- Mar 09: ???