Optymalizacja wypukła

informatyka

monograficzne

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.

w sali

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 common approaches to solving convex problems in practice.

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 problems which can be modeled as optimizing a convex function under a set of constraints that describes a convex set. The course will cover the most important algorithms for such convex optimization problems including gradient descent, subgradient method, barrier method or Newton’s method. It will also include algorithms and properties of an especially well understood special case of convex optimization, namely linear programming. As an important side topic, we will also discuss discrete problems that arise from convex problems by adding the integrality constraints (e.g. integer linear programming).

After the course, the students should be able to recognize which problems can be formulated as convex problems and understand that the efficiency of algorithms for solving these problems is influenced by the class of constraints used. We will see a hierarchy of these classes (convex programming, semidefinite programming, second-order cone programming, quadratic programming, linear programming). We will practice modeling problems using constraints from these classes, as well as applying available solvers (open source or commercial with free academic license).

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