CPSC 536C: Algorithms for Convex Optimization

Course Description

We will cover the following fundamental algorithms used for provably efficient convex optimization with a focus on rigorous convergence analysis: (1) Ellipsoid method; (2) Gradient Descent; (3) Mirror Descent; and (4) Interior Point Methods. At the end of the course, you should have an understanding of why convex optimization algorithms work, and be able to effectively apply these tools to your own research. For the previous iteration of this course, along with notes, see here.

Lectures

MW 11am-12:30pm in DMP 201

Resources

• Syllabus
• Instructions for Student Lecture and Project
• Office Hours: TBD

Schedule

Date	Topic	Notes
Week 1	Introduction	-
Week 2-3	Convex sets and functions
Week 3	Cutting Plane Methods
Week 4	Convex Programming Duality and John's Ellipsoid
Week 5-6	Gradient Descent
Week 7	Reading Week	—
Week 8-9	Mirror Descent
Week 10-12	Interior Point Methods

Assignments

References

• Rockafellar — Convex Analysis
• Boyd & Vandenberghe — Convex Optimization
• Nesterov and Nemirovski— Interior Point Polynomial Methods in Convex Programming
• Nesterov — Introductory Lectures on Convex Optimization
• Bubeck - Convex Optimization
• Bubeck - Introduction to Online Optimization
• Lap Chi Lau - Convexity and Optimization
• Yao-Liang Yu - Optimization for Data Science