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 at uw dot edu.
    • Lectures: WF 3:00-4:20 at EEB 037

Schedule:

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)

Other Methods

  • Mar 07: How to solve ODE? (Note)
  • Mar 09: The Exponentially Convergent Trapezoidal Rule (Note) (Survey)

Related CS Theory Courses: