Optimisation Numérique, M1 Ingénierie Mathématique

Calendrier et modalités

Cours : 30h de CM, le jeudi 15h45-17h15, salle 443/445 bât 450, et le vendredi 13h30-16h30, salle B14 bât 460 ;
TP : 4 séances de 2h le jeudis 13h30-15h30 (option modélisation) et le vendredi 10h-12h (option stat) ;
Attention : le cours du jeudi 23/1 est avancé à 13h45, les cours des 30/1 et 31/1 n'existent pas, le 13/3 TP et cours sont interchangés, le jeudi20/3 le cours sera anulé ; les TP commencent le 13/2.
Modalité d'examen : 1 écrit (75%) + 1 devoir maison de TP (25%).

Programme du cours

On traitera dans l'ordre :
  • les généralités sur les problèmes d'optimisation (existence, conditions d'optimalité...)
  • des algorithmes pour chercher les minimiseurs (en particulier pour les fonctions convexes), qu'on implementera lors des TP
  • des sujets complémentaires et plus avancés, qu'on ne traitera pas en TP

    • Le programme est plus ou moins le suivant:

  • Jeudi 23/1 Introduction à l'optimisation, existence des optima, semicontinuité
  • Vendredi 24/1 Conditions d'optimalité, multiplicateurs de Lagrange, exemples et exercices
  • Jeudi 6/2 Méthodes de Newton, théorème des contractions.
  • Vendredi 7/2 Optimisation en dimension 1 (Newton, dychotomie, section dorée) ; introduction à la minimisation des fonctions convexes, fonctions convexes, strictement convexes et elliptiques. Algorithme du gradient à pas fixe e à pas variable.
  • Jeudi 13/2 Algorithmes de gradient à pas optimal, applications aux fonctions quadratiques et aux systèmes linéaires, exercices.
  • Vendredi 14/2 Algorithme du gradient conjugué pour les fonctions quadratiques ; algoritme du gradient projeté pour la minimisation sous contrainte.
  • Jeudi 20/2 Méthode de pénalisation pour la minimisation sous contrainte et TD sur projection et minimisation sous contrainte.
  • Vendredi 21/2 Dualité et méthode d'Uzawa pour la minimisatin sous contrainte ; TD sur projection et minimisation sous contrainte ; sous-différentiel et algorithme de sous-gradient.
    • Attention : vacances scolaires, pas de cours les 27/2 et 28/2.
  • Jeudi 6/3 Programmation linéaire : exemple du problème de transport optimal, généralités sur les polyhèdres convexes.
  • Vendredi 7/3 Programmation linéaire : preuve que le minimum est atteint en un sommet, quelques mots sur l'algorithme du simplexe. Calcul des variations : équations d'Euler-Lagrange et conditions au bord, rôle de la convexité, exemples.
  • Jeudi 13/3 Calcul des variations : exercices, exemples, exemple de non-existence, discrétisation.
  • Vendredi 14/3 Programmation dynamique en temps discret et horizon fini et infini, croissance optimale à un secteur économique, exemples et exercices.
    • Attention : pas de cours le 20/3.
  • Vendredi 21/3 TD et correction annales.

    • Travaux Pratiques

    Les TP sont assurés par Monsieur le Professeur Frédéric Lagoutière, grand chef de notre M1. Les TP débuteront le jeudi 13/2. (attention !!)

    Bibliographie

    Une bonne partie du cours (les multiplicateurs de Lagrange, tous les algorithmes de gradient, le symplexe...) se trouve sur le livre de Ph. Ciarlet Introduction à l'analyse numérique matricielle et à l'optimisation.

    Pour le cours du 23/1 vous pouvez voir ce poly de calcul différentiel et en particulier les pages 93 et suivantes.
    Pour le cours du 24/1 vous pouvez voir le livre de Ciarlet, chapitre 7.2. et/ou le poly précédent, chapitre 9.
    Pour le cours du 6/2, Ciarlet, pages 158-166 (mais on n'a pas tout fait).
    Pour les cours du 7/2 Ciarlet, Chap. 8.4 (sauf relaxation).
    Pour le cours du 13/2 et 14/2, Ciarlet 8.4 (pas optimal), 8.5 (grad. conjugué), 8.6 (grad. projeté).
    Pour le cours du 20/2 Ciarlet 8.6 (pénalisation).
    Pour le cours du 21/2 Ciarlet chapître 9 (en particulier 9.3 et 9.4).
    Pour le cours du 6/3 (et début du cours du 7/3), Ciarlet, 10.2 et 10.3
    Pour les cours des 7/3 et 13/3, voir le chapitre 4 (calcul des variations) de ce poly de Guillaume Carlier sur l'optimisation dynamique.
    Pour le cours d du 14/3, voir les chapitres 1, 2 et 3 du poly d'optimisation dynamique de Carlier.

    Annales et exercices

    Sujet du dévoir maison donné en cours en 2011, avec l'examen de l'année précédente (attention : ne pas trop se fier au style de l'examen de 2010, c'était un autre prof).

    Corrigé du DM de 2011.
    Sujet et corrigé de l'examen du 24/3/2011.

    Devoir maison du 15 mars 2012 avec corrigé.
    Sujet de l'examen du 29 mars 2012.
    Sujet du rattrapage du 2 juillet 2012.

    Devoir maison pour le 15 mars 2013, avec correction partielle (ce qui n'avait pas été fait en classe).
    Sujet de l'examen du 28 mars 2013.
    Sujet du rattrapage du 27 juin 2013.