Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Optymalizacja wypukła

Informacje ogólne

Kod przedmiotu: 1000-2M22OW
Kod Erasmus / ISCED: 11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Optymalizacja wypukła
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obieralne dla informatyki
Przedmioty obieralne dla Machine Learning
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Założenia (opisowo):

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.

Skrócony opis:

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.

Pełny opis:

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.

Literatura:

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

Metody i kryteria oceniania:

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

Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)

Okres: 2024-02-19 - 2024-06-16
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Łukasz Kowalik, Marcin Mucha
Prowadzący grup: Jacek Cyranka, Łukasz Kowalik, Marcin Mucha
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)