Liens transverses ENS de Lyon

INFO4105 : Optimisation et Approximation

Optimization and approximation

Niveau M1+M2

Discipline(s) Informatique

ECTS 6.00

Période 1e semestre

Localisation Site Monod

Année 2021-2022

 Public externe (ouverts aux auditeurs de cours)
 

Horaires du cours
TD: Wednesday 10h15-12h15 

Cours: Thursday 10h15-12h15 
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 

  • Numerical Optimization, Nocedal and Wright (2006)
Modifié le :
05/07/2021 11:08:00