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: 3 homework
- 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.
- Assignment 3 is due on Mar 12.
- 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 (Note)
- Mar 02: Lee-Sidford Barrier (Note)
- Mar 07: How to solve ODE? (Note)
- Mar 09: The Exponentially Convergent Trapezoidal Rule (Note) (Survey)