CS 591 E1: Advanced Optimization Algorithms

Course Description

This is a graduate-level course on optimization algorithms. The course covers continuous and discrete optimization through the lens of convex optimization. Convex optimization has had a profound impact on many areas of computer science and engineering, including algorithms and theoretical computer science, machine learning, data mining, finance, and operations research. The first part of the course covers the theory of convex optimization and its applications. The second part covers discrete optimization techniques that build on the machinery covered in the first part. For more information, see the syllabus.


Collaboration and Honesty Policy


Gradescope for submitting homeworks. Sign up using the entry code MV54N6.

Grading Instructions

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Wednesdays 4:30pm - 6pm or by appointment (please email to make an appointment), in MCS 291.


Tues/Thurs 3:30 - 4:45pm, in MCS B25

The schedule is tentative and subject to change (e.g., snow days).

Lecture Topic Reading
Mathematical background and introduction to optimization
Lecture 1 (9/4/18) Course overview and introduction. Linear classification and the Perceptron algorithm Slides
Lecture 2 (9/6/18) Review of concepts from linear algebra Slides
Lecture 3 (9/11/18)
Review of concepts from multivariate calculus
Lecture 4 (9/13/18)
Convex functions and sets
Lectures 5, 6 (9/18/18, 9/20/18)
Introduction to optimization. Examples of discrete and continuous optimization problems: classification and learning problems (least squares, LASSO, SVM), maximum flows and minimum cuts, maximum cut, minimum independent set
Continuous Optimization
Lectures 7, 8 (9/25/18, 9/27/18)
Optimality conditions for general and convex problems
Lectures 9, 10 (10/2/18, 10/4/18)
Oracle models, iterative methods, and gradient descent
Lecture 11 (10/9/18)
No Class (Monday schedule)
Lecture 12 (10/11/18)
Gradient descent for smooth and strongly convex functions
Lectures 13, 14 (10/16/10, 10/18/18,)
Prediction using expert advice: majority algorithms, multiplicative weights update algorithm
Lecture 15 (10/23/18)
Applications of multiplicative weights update framework, online optimization and learning
Lecture 16 (10/25/18)
Midterm review
Lecture 17 (10/30/18)
In-class midterm exam
Lecture 18 (11/1/18)
Introduction to linear programming, modeling using LPs
Lecture 19 (11/6/18)
LP duality
Lectures 20, 21, 22 (11/8/18, 11/13/18, 11/15/18)
Applications of duality: maxflow-mincut theorem, minimax theorem in game theory, learning and boosting
Discrete Optimization
Lecture 23 (11/20/18)
Introduction to discrete optimization
Lecture 24 (11/27/18)
Submodular functions and optimization
Lecture 25 (11/29/18)
Maximum flows and minimum cuts in networks (guest lecture by Adrian Vladu)
Lecture 26 (12/4/18)
Submodular optimization continued
Lecture 27 (12/6/18)
Final exam review
Lecture 28 (12/11/18)
Course recap

Acknowledgments: Many pictures used in the lecture slides are courtesy of Google Images and their respective authors. I am indebted to my colleagues at other institutions for some of the material in the lectures. In particular, Amir Ali Ahmadi's course at Princeton has been a great source of inspiration and material.


Homeworks are released on Thursdays before class, and are due in one week on Thursdays at midnight. The hw schedule is as follows (see Piazza for the pdf/tex):