Advanced Optimization Methods / Conic Optimization

Course guarantor:

Jakub Mareček

Lecturer:

Allen Robert Gehret, Jakub Mareček

Tutor:

Shenyuan Ma, Jakub Mareček

Supervisor:

Department of Computer Science

Synopsis:

The course introduces conic optimization as a unifying framework for the study of a wide range of optimization problems.

Requirements:

Some introduction to linear algebra.

Syllabus of lectures:

1.Motivating examples. Algebraic modelling languages.

2.Conic optimization: Convex cones, Primal and dual conic problems, Spectrahedra and LMIs, Spectrahedral shadows.

3.SDP duality, Numerical SDP solvers.

4.Exact SDP solvers and associated algebraic geometry.

5.Finite-dimensional polynomial optimization: an overview.

6.Measures and moments, Riesz functional.

7.Commutative POP: moment and localizing matrices, Lasserres hierarchy.

8.Non-commutative POP: moment and localizing matrices, NPA hierarchy.

9.Global optimum recovery.

10.Infinite-dimensional polynomial optimization.

11.Optimal control.

12.Extensions to time-varying coefficients.

13.The motivating examples revisited.

Syllabus of tutorials:

The labs cover some of the popular packages:

1.Cvxpyy

2.Yalmip

3.Yalmip

4.Ncpol2sdpa

5.Ncpol2sdpa

6.TSSOS

7.TSSOS

8.NCTSSOS

9.momgraph

10.POCP

Study Objective:

The goal is to understand the opportunities and challenges in applying methods with polynomial runtime in solving conic optimization problems, esp. semidefinite programming and polynomial optimization.

Study materials:

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.

Note:

The course is primarily intended for students of QNI (Quantum Computer Science, Kvantová informatika, FIT), but open also to MPOI (Otevřená informatika, FEL) and PhD students (DCINF Informatika, DEINF Computer Science).

Further information:

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

Time-table for winter semester 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
Mon
Tue
Wed	roomKN:A-311 Mareček J. Gehret A. 09:15–10:45 (lecture parallel1) Karlovo nám. roomKN:A-311 Mareček J. Ma S. 11:00–12:30 (lecture parallel1 parallel nr.101) Karlovo nám. roomKN:A-404 Mareček J. Gehret A. 09:15–10:45 (lecture parallel1) Karlovo nám. roomKN:A-404 Mareček J. Ma S. 11:00–12:30 (lecture parallel1 parallel nr.101) Karlovo nám.
Thu
Fri

Time-table for summer semester 2025/2026:

Time-table is not available yet

The course is a part of the following study plans: