Convex optimization

elective monographs

There are no formal requirements but we assume that students have basic knowledge of linear algebra and mathematical analysis of many variables, and know the basics of programming in python.

This is an introduction to convex optimization, giving an overview of the landscape of convex optimization problems, and covering the most important convex optimization algorithms and lower bounds, as well as convex modelling techniques. The lab sessions cover convex modelling using modern software and implementation of selected convex optimization algorithms.

Many problems in Machine Learning can be formulated as optimizing a function in R^n under a number of constraints, formulated as inequalities. While this model is general enough to include provably hard problems, it becomes provably tractable under certain assumptions. Perhaps the most important examples are convex problems, i.e., problems which can be modeled as optimizing a convex function under a set of constraints that describes a convex set. The course has three main parts:

Part 1. Basic properties of convex sets, functions, and problems, including duality.

This part develops notions and tools used throughout the course.

Part 2. Classification of convex problems.

We will discuss unconstrained problems, equality constrained problems, linear problems, SOCP problems, SDP problems, etc.; We will understand the classes of constrained problems as cone problems. Finally, we will learn how to model a given problem in an appropriate class.

Part 3. Algorithms for convex optimization.

Will cover the most important algorithms for convex problems including gradient descent, subgradient method, barrier method, Newton’s method or ellipsoid algorithm. We will see proofs of running-time and solution quality guarantees for those problems. As a result, the students will understand theoretical and practical limitations of solving problems in the classes mentioned in Part 2.

If time permits, we will also cover a related and practically relevant concept of integer programming, i.e., (non-convex) problems obtained from convex problems by adding integrality constraints.

In the lab sessions, students learn to model a number of problems either directly using the interface of a given solver or using a general convex modelling language. Most likely we will use Python interface to Gurobi (commercial, with academic licence) and CBC (open source) solvers; and cvxpy and PuLP modelling packages (both open source). The lab sessions also include implementation of selected convex optimization algorithms.

1. S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press

2. S. Bubeck, Convex Optimization: Algorithms and Complexity

3. N.K. Vishnoy, Algorithms for Convex Optimization, Cambridge University Press

There will be 4-5 home assignments and a written exam. The final grade will depend on performance on both.