Dabeen Lee
Fall 2023

IE 539: Convex Optimization

MW 4:00 - 5:30 pm, E2-2 B105

Big data has introduced many opportunities to make better decision-making based on a data-driven approach, and many of the relevant decision-making problems can be posed as optimization models that have special properties such as convexity and smoothness. From this course, a graduate-level student will learn fundamental and comprehensive convex optimization knowledge in theory (convex analysis, optimality conditions, duality) and algorithms (gradient descent and variants, Frank-Wolfe, and proximal methods). We will also cover some application areas including statistical estimation, finance (e.g., portfolio optimization), machine learning, and data science.

Lecture notes

  1. Mon 8/28: introduction (slides), linear algebra review (note)
  2. Wed 8/30: matrix calculus review, convex sets (note)
  3. Mon 9/04: convex functions, first-order and second-order characterizations of convex functions (note)
  4. Wed 9/06: operations preserving convexity, convex optimization problems I (Portfolio optimization, Uncertainty quantification) (note)
  5. Mon 9/11: convex optimization problems II (SVM, LASSO, Facility location), classes of convex programming I (LP) (note)
  6. Wed 9/13: classes of convex programming II (QP, SDP, Conic programming) (note)
  7. Mon 9/18: conic duality, SOCP and applications (note)
  8. Wed 9/20: optimality conditions, introduction to gradient descent (note)
  9. Mon 9/25: convergence of gradient descent (note)
  10. Wed 9/27: subgradient method, gradient descent for smooth functions (note)
  11. Thu 10/05: convergence of gradient descent for functions that are smooth and strongly convex (note)
  12. Wed 10/11: projected gradient descent, Nesterov's acceleration, oracle complexity lower bounds (note)
  13. Mon 10/23: Frank-Wolfe algorithm, introduction to online convex optimization (note)
  14. Wed 10/25: online and stochastic gradient descent algorithms (note)
  15. Mon 10/30: convergence of stochastic gradient descent, proximal gradient descent (note)
  16. Wed 11/01: convergence of proximal gradient descent, proximal point algorithm (note)
  17. Mon 11/06: KKT conditions, Lagrangian duality (note)
  18. Wed 11/08: saddle point problem, Fenchel conjugate (note)
  19. Mon 11/13: Fenchel duality (note)
  20. Wed 11/15: dual gradient method, Moreau-Yosida smoothing (note)
  21. Mon 11/20: augmented Lagrangian method, alternating direction method of multipliers (ADMM) (note)
  22. Wed 11/22: Newton's method (note)
  23. Mon 11/27: quasi-Newton methods (note)
  24. Mon 12/04: barrier method (note)
  25. Wed 12/06: primal-dual interior point method (note)

Assignments

  1. Assignment 1 (pdf)
  2. Assignment 2 (pdf)
  3. Assignment 3 (pdf)
  4. Assignment 4 (pdf)
  5. Assignment 5 (pdf)

Final exam

(file)