Convex Optimization (NMMB409) - Winter term 2025/26

Lecture: Tuesday 17:20 - 18:50, K9. Wednesday 10:40 - 12:10, K7.
Practicals: Thursday 15:40 - 17:10, K9.

Literature:

• [BV] Boyd, Vandenberghe, Convex Optimization
  This is the main source for the course. Book and slides are freely available on Boyd's website.
• [MG] Matoušek, Gärtner, Understanding and Using Linear Programming
• Homeworks will include programming assignments that are based on using the Python package CVXPY (CVXPY).

Evaluation:
There will be 4 homework assignments, on each of which you need to score at least 60% to obtain the credit (zápočet) for the course. If this condition cannot be met (e.g. due to illness, or some other significant reasons), there is the possibility of solving an extra 5th homework assignment.
Exam: oral examination. It is necessary to have obtained the credit (zápočet) in order to take the exam.

Consulation: If you have any questions, do not hesitate to ask! Best in my office hours, Th: 17:10-18:00.

Overview:

Date	Topics	Reference	Homework
30.09	Optimization problems, Examples Convex optimization problems can be solved efficiently	BV1, MG2
1.10	Convex sets: definitions, important examples closure under intersections and affine functions	BV2.1-2.3
2.10	Pr.: Basic examples in CVXPY	Pr1 Sol1
7.10	Separating and supporting hyperplane theorem (+proof) Basic examples of convex functions	BV 2.5, 3.1
8.10	first and second order criterion for convexity, epigraph and sublevel sets	BV 3.1
9.10	Pr.: Convex sets and functions	Pr2
14.10	Operations that preserve convexity, important definitions for optimization problems	BV 3.2, 4.1
15.10	The first order criterion for convex optimization problems, locally optimal solutions are optimal	BV 4.1
16.10	Pr.: Operations that preserve convex functions, LP normal form	Pr3	HW1 - due 30.10
21.10	LPs, QPs, QCQPs. bounded polyhedra as convex hull of their vertices Motivational example for solving LPs	BV 4.3, 4.4 MG 4
22.10	the standard normal form for LPs, basic feasible solutions the simplex method, unboundedness and degeneracy	MG 4, 5
23.10	Pr.: Linear Programs	Pr4
28.10	Independence day
29.10	simplex method: finding basic feasible solutions; discussion different Pivot rules LP-relaxations (Example: vertex cover). linear-fractional problems reduce to LPs	MG 5, BV 4.3.2
30.10	Pr.: LPs, Norm approximation problems	Pr5	HW2 - due 13.11
4.11	Geometric programming (Example: bacteria population) quasiconvex problems and the bisection method	BV 4.5, BV 4.2.5.
5.11	generalized inequality constraints and Semidefinite Programming (SDP) The SDP relaxation of Max-CUT	BV 4.6, Notes
6.11	Pr.: QPs, QCQPs, SOCPs, SDPs	Pr6
11.11
12.11	Dean's sports day
13.11	Pr.:		HW3 - due 27.11
18.11
19.11
20.11	Pr.:
25.11
26.11
27.11	Pr.:		HW4 - due 11.12
2.12
3.12
4.12	Pr.:
9.12
10.12
11.12	Pr.:		HW5 - due 7.1
16.12
17.12
18.12	Pr.:
5.1
6.1
7.1	Pr.: