Convex optimization 1000-2M22OW

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.