Convex Optimization (NMMB409) - Winter term 2024/25

Lecture: Thursday 12:20 - 13:50, K7; Friday 12:20 - 13:50, K8
Practicals: Wednesday 12:20 - 13:50, K8; run by Alexey Barsukov.

Literature: The lecture follows mainly the book and slides on Convex Optimization by Boyd and Vandenberghe [BV], which are freely available online on Boyd's website. If alternative material is used, it will be shared here. Practicals and homework assignments will also be published here. 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 the credit in order to take the exam.

Consulation: If you have any questions, do not hesitate to ask! Best in my office hours, Fr: 11:00-12:20.

Overview:

Date Topics Reference Homework
2.10 Pr.: Introduction to Python and the CVXPY package Pr0, Pr1
3.10 Optimization problems
Convex problems can be solved efficiently (e.g. linear programming, least-squares)
BV 1
4.10 Convex sets: Important examples (affine spaces, halfspaces, balls, cones,...)
closedness under intersection and affine/perspective functions
BV 2.1-2.3
9.10 Pr.: Examples of LPs and least-squares problems Pr2
10.10 Separating hyperplane theorem
convex/concave function: important examples, first and second order criteria
BV 2.5, 3.1
11.10 the epigraph,
operations that preserve convexity (weighted sums, suprema, infima, composition)
BV 3.1., 3.2
16.10 Pr.: Convex sets and functions, the perspective of a function Pr3 [HW1] - 30.10
17.10 Quasiconvex functions; Important definition for general optimization problems
Convex OPs: local optima are optima; optimality criterion in differentiable case
BV 3.4, 4.1,
4.2
18.10 LP, QP, QCQP, SOCP; Examples (Chebyshev center, distance of polyhedra, robust LP...)
Transforming Optimization Problems
BV 4.3, 4.4,
4.2
23.10 Pr.:Transforming Optimization Problems, standard form of LP Pr4
24.10 Geometric programming, linear-fractional programs
bisection method for quasiconvex problems, proper cones
BV 4.5, 4.3.2
4.2,5, 2.4
25.10 Generalized inequality constraints (conic problems), SDPs
the SDP-relaxation of Max-Cut, LP relaxations
BV 4.6
Notes
30.10 Pr.: Examples of SDPs, reduction of LP, QCQP, SOCP to SDPs Pr5
31.10 Multiobjective optimization problems, finding Pareto optima via scalarization;
scalarization for general K via dual cones K*
BV 4.7, 2.6
1.11 Duality: Lagrangian, dual function, dual problem, weak duality
Slater's condition for strong duality
BV 5.1, 5.2
6.11 Pr.: Duality Pr6 [HW2] - 20.11
7.11 Different interpretations of duality (geometrical, saddle point interpretation)
Examples, randomized strategies for randomized matrix games
BV 5.3, 5.7
5.2.5
8.11 Farkas lemma, strong duality for LPs BV 5.8, Notes
13.11 Pr.: Duality, Slater's condition Pr7
14.11 KKT conditions, perturbation analysis BV 5.5, 5.6
15.11 Duality for generalized inequalities
Norm and penality function approximation
BV 5.9, 6.1
20.11 Pr.: KKT conditions, perturbation analysis; log barrier penalty function Pr8 [HW3] - 4.12
21.11 Comparisons of different penalty functions, Huber penalty for robust approximation
least-norm problems, regularization problems and applications in signal processing
BV 6
22.11 maximimum likelihood estimates and examples:
linear measurement models, Poisson distributon, logistic regression, covariance matrix
BV 7.1
27.11 Pr.:Function fitting Pr9
28.11 Function fitting (discussion practicals Pr9), MAP estimates
Binary hypothesis testing
BV 7.1, 7.3
29.11 Binary hypothesis testing, Optimal experiment design BV 7.3, 7.5
4.12 Pr.:statistical estimation Pr10 [HW4] - 22.12
5.12 Geometric problems: distance between convex sets,
outer and inner Loewner-John ellipsoids, centering
BV 8.1,8.2,
8.4,8.5
6.12 Linear discriminators, support vector machines
Newton's method to approximate roots of a real-valued function
BV 8.6,
[wiki]
11.12 Pr.:
12.12
13.12
18.12 Pr.: [HW5] - 8.1
19.12
20.12
8.1 Pr.:
9.1
10.1