Mathematical optimization.
Credits
6 ECTS, C. 36h
Instructor
Anatoli Iouditski
Syllabus
This course deals with
-
Topic 1: convex analysis
-
Topic 2: convex programming
-
Basic notions: vector space, affine space, metric, topology, symmetry groups, linear and affine hulls, interior and closure, boundary, relative interior
-
Convex sets: definition, invariance properties, polyhedral sets and polytopes, simplices, convex hull, inner and outer description, algebraic properties, separation, supporting hyperplanes, extreme and exposed points, recession cone, Carathéodory number, convex cones, conic hull
-
Convex functions: level sets, support functions, sub-gradients, quasi-convex functions, self-concordant functions
-
Duality: dual vector space, conic duality, polar set, Legendre transform
-
Optimization problems: classification, convex programs, constraints, objective, feasibility, optimality, boundedness, duality
-
Linear programming: Farkas lemma, alternative, duality, simplex method
-
Algorithms: 1-dimensional minimization, Ellipsoid method, gradient descent methods, 2nd order methods
-
Conic programming: barriers, Hessian metric, duality, interior-point methods, universal barriers, homogeneous cones, symmetric cones, semi-definite programming
-
Relaxations: rank 1 relaxations for quadratically constrained quadratic programs, Nesterovs π/2 theorem, S-lemma, Dines theorem Polynomial optimization: matrix-valued polynomials in one variable, Toeplitz and Hankel matrices, moments, SOS relaxations
Assessment
A two-hours written exam (E1) in December. For those who do not pass there will be another two-hours exam (E2) in session 2 in spring.