UE Efficient methods in optimization

Diplômes intégrant cet élément pédagogique :

Descriptif

The subject of this half-semester course are more advanced methods in convex optimization. It consists of 6 lectures, 2 x 1,5 hours each, and can be seen as continuation of the course “Non-smooth methods in convex optimization”.

This course deals with:

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.

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

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

Pré-requis recommandés

Linear algebra: matrices, vector spaces, linear functions

Analysis: differentiability, gradients, convergence, continuity

Compétences visées

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.

Bibliographie

S. Boyd, L. Vandenberghe. Convex Optimization. Cambridge University Press. 2004. http://stanford.edu/~boyd/cvxbook/

A. Ben-Tal, A. Nemirovski. Lectures on modern convex optimization. SIAM, Philadelphia, 2001.

R.T. Rockafellar. Convex analysis. Princeton University Press, Princeton, 1970

J.-B. Lasserre. An Introduction to Polynomial Optimization. Cambridge University Press, Cambridge, 2015

Informations complémentaires

Méthode d'enseignement : En présence
Lieu(x) : Grenoble
Langue(s) : Anglais

Catalogue des formations