## 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

### 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