UE Efficient methods in optimization

User information

Please note that you are curently looking at the ongoing Academic Programs. Applications are now closed for this academic year (2020-2021) for licences, professional licences, masters, DUT and regulated health training. If you are interested for an application in 2021-2022, please click on this link for the appropriate Academic Programs.

Degrees incorporating this pedagocial element :

Description

Theoretical foundations of convex optimization.

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

The course is composed of 18 hours lectures.

Evaluation : 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.

Recommended prerequisite

Linear algebra: matrices, vector spaces, linear functions

Analysis: differentiability, gradients, convergence, continuity

Targeted skills

At the end of the course, the student will be able to convert optimization problems into a standard form amenable to a solution by a solver.