## INFO4105 : Optimisation et Approximation

### Optimization and approximation

Responsable(s) : Daniel Hirschkoff

Niveau
M1+M2
Discipline
Informatique
ECTS
6.00
Période
1e semestre
Localisation
Site Monod
Année
2021

Public externe (ouverts aux auditeurs de cours)
Objectif du cours

Contents of the course.

1. Introduction to optimization

• Nonlinear Programming

1. Prerequisites for nonlinear optimization (gradient, Hessian, descent directions, rate of convergence)

2. Gradient method (quadratic and nonlinear functions)

3. Newton method and introduction to linesearch

4. Least-squares and Gauss Newton

5. Constrained optimization and KKT conditions

6. Optimization for machine learning: subsampled methods and stochastic methods

• Linear Programming

1. Geometry of Linear Programming, Polytopes

2. Polyhedra

3. Simplex algorithm

4. Duality

5. Integer Linear Programming (ILP): TU, integer polytopes, examples on graphs, maximum flow

6. ILP: Integrality gap and Erdos-Posa property

7. LP rounding

Methods studied in the first part of the course will be implemented in a programming language (typically python or Matlab) and applied to solve some practical problems.

Students should know the basics from Calculus and Linear Algebra and have knowledge of a programming language (Matlab or Python for instance). Here some detailed prerequisite and some references. All these topics will be briefly rediscussed at the beginning of the course and can also be found in appendix A of the book "Numerical Optimization", by Nocedal and Wright, which will be the reference book for the first part of the course.

-Taylor's theorem: http://www.supermath.info/TaylorPolynomialApproximation.pdf
-Elements of analysis and topology: limits, continuity of functions, derivatives mean value theorem: http://tomlr.free.fr/Math%E9matiques/Math%20Complete/Analysis/Basic%20Elements%20of%20Real%20Analysis%20-%20M.%20Protter.pdf (chapters 2 and 4)

-Elements of linear algebra: vector and matrices, eigenvalues, eigenvectors, singular value decomposition: http://web.stanford.edu/class/cme001/handouts/linalg-a.pdf

-Floating point arithmetic: https://doc.lagout.org/science/0_Computer%20Science/3_Theory/Handbook%20of%20Floating%20Point%20Arithmetic.pdf

The first part of the course will be taught by Elisa Riccietti, the second part by Stephan Thomassé.

50% of the final mark will be determined by the final written exam and the other 50% by a midterm written exam that will be held in the week of 25 October. The second session will be an oral exam.

Amphi B

TD: Wednesday 10h15-12h15

Cours: Thursday 10h15-12h15

Horaires
Horaires du cours
TD: Wednesday 10h15-12h15

Cours: Thursday 10h15-12h15
Modifié le :
2021-07-05 11:08:00 Europe/Berlin