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:

- Assignments will be submitted via Canvas.
- Assignment 1 is due on Jan 31.

### Announcements

- 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.

- 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

#### Other Methods

- Mar 07: Quasi-Newton Method
- Mar 09: ???