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@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. Here is this fix. I hope it is correct.
- 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