Efficient methods in optimization
Credits
6 ECTS, C. 36h
Instructor
Roland Hildebrand, Franck Iutzeler
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, subgradients, quasiconvex functions, selfconcordant 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: 1dimensional minimization, Ellipsoid method, gradient descent methods, 2nd order methods

Conic programming: barriers, Hessian metric, duality, interiorpoint methods, universal barriers, homogeneous cones, symmetric cones, semidefinite programming

Relaxations: rank 1 relaxations for quadratically constrained quadratic programs, Nesterovs π/2 theorem, Slemma, Dines theorem Polynomial optimization: matrixvalued polynomials in one variable, Toeplitz and Hankel matrices, moments, SOS relaxations
Assessment
A twohours written exam (E1) in December. For those who do not pass there will be another twohours exam (E2) in session 2 in spring.