Pokročilé metody optimalizace / Kónická optimalizace

Garant předmětu:

Jakub Mareček

Přednášející:

Jakub Mareček

Cvičící:

Jakub Mareček

Předmět zajišťuje:

katedra počítačů

Anotace:

Kurz představuje kónickou optimalizaci jako sjednocující rámec pro studium řady optimalizačních problémů.

Požadavky:

Úvodní kurz lineární algebry.

Osnova přednášek:

1.Motivační příklady, algebraické modelovací jazyky.

2.Kónická optimalizace: konvexní kužely, dualita, spectrahedra, LMI, spektrahedrální stíny.

3.Dualita v případě SDP, numerické řešiče pro SDP.

4.Přesné řešiče pro SDP a související algebraická geometrie.

5.Konečně-dimenzionální polynomiální optimalizace: přehled.

6.Míra a její momenty, momentový problém, Rieszův funkcionál.

7.Lasserrova hierarchie pro komutativní polynomiální optimalizaci. Momentové a lokalizační matice.

8.NPA hierarchie pro nekomutativní polynomiální optimalizaci. Momentové a lokalizační matice.

9.Extrakce optimálního řešení.

10.Nekonečně-dimenzionální polynomiální optimalizace.

11.Optimální řízení.

12.Rozšíření na problémy s koeficienty proměnnými v čase.

13.Revize motivačních příkladů.

Osnova cvičení:

Cvičení jsou zaměřena na související softwarové balíky:

1.Cvxpy a motivační příklady

2.Yalmip a motivační příklady

3.Yalmip a dualita

4.Ncpol2sdpa

5.Ncpol2sdpa

6.TSSOS

7.TSSOS

8.NCTSSOS.o0 pp on pp

9.momgraph

10.POCP

11.Konzultace k semestrálnímu projektu

12.Konzultace k semestrálnímu projektu

13.Konzultace k semestrálnímu projektu po pp

Cíle studia:

Cílem je porozumět možnostem a omezením metod běžících v polynomiálním čase v optimalizaci, zejména pak v semidefinitním programování a polynomiální optimalizaci.

Studijní materiály:

Anjos, Miguel F., and Jean B. Lasserre, eds. Handbook on semidefinite, conic and polynomial optimization. Vol. 166. Springer Science & Business Media, 2011.

Burgdorf, Sabine, Igor Klep, and Janez Povh. Optimization of polynomials in non-commuting variables. Vol. 2. Berlin: Springer, 2016.

Poznámka:

Předmět je určen pro studenty programu QNI (Kvantová informatika, FIT), P_QTN (Kvantové technologie, FJFI), při nenaplněné kapacitě mohou předmět absolvovat studeni MPOI (MP44, Otevřená informatika, FEL) a doktorského studia (DCINF Informatika, DEINF Computer Science).

Další informace:

https://cw.fel.cvut.cz/b251/courses/bqm36pmo/start

Rozvrh na zimní semestr 2025/2026:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St	místnost KN:A-311 Mareček J. 09:15–10:45 (přednášková par. 1) Karlovo nám. Posluchárna KA311místnost KN:A-311 Mareček J. 11:00–12:30 (přednášková par. 1 paralelka 101) Karlovo nám. Posluchárna KA311
Čt
Pá

Rozvrh na letní semestr 2025/2026:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů: