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

Calendrier et modalités

Cours et TD : 24h de CM + 9h de TD, le jeudi 15h45-17h15, salle 443 bât 450, et le vendredi 13h30-16h30, salle B14 bât 460 ; l'alternance entre cours et TD (assurés par Alpár Mészáros) est indiquée dans le programme ci-dessous, mais sera confirmée au fur et à mesure.
TP : 6 séances de 2h le vendredi 10h-12h (un seul groupe) ;
Attention : les TP commencent le 6/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 22/1 Introduction à l'optimisation, existence des optima, semicontinuité
  • Vendredi 23/1 Conditions d'optimalité, multiplicateurs de Lagrange, exemples, introduction à la méthode de Newton.
  • Jeudi 29/1 Méthodes de Newton et théorème des contractions ; optimisation en dimension 1 (Newton, dichotomie, section dorée).
  • Vendredi 30/1 Introduction à la minimisation des fonctions convexes, fonctions convexes, strictement convexes et elliptiques. Algorithme du gradient à pas fixe, à pas variable et à pas optimal ; applications aux fonctions quadratiques et aux systèmes linéaires.
  • Jeudi 5/2 -- TD.
  • Vendredi 6/2Minimisation quadratique et systèmes linéaires; algorithme du gradient conjugué. Conditions d'optimalité dans la minimisation sous contraintes ; projection sur un convexe fermé ; algorithe du gradient projeté.
  • Jeudi 12/2 Exemples de projections. Méthode de pénalisation.
  • Vendredi 13/2 Examples: minimisation quadratique sous contraintes de positivité ; lien entre pénalisation et multiplicateur de Lagrange. Dualité et algorithme d'Uzawa. Exemples, résumé des différents algorithmes pour les cas libre, quadratique et avec contraintes.
    • Attention : pas de cours le 19/2.
  • Vendredi 20/2 -- TD
    • Attention : vacances scolaires, pas de cours les 26/2 et 27/2.
  • Jeudi 5/3 -- TD
  • Vendredi 6/3 Programmation linéaire : différentes formes du problème ; exemple du problème de Monge-Kantorovich (avec dualité et application aux mariages stables) ; algorithme du simplexe.
  • Jeudi 12/3 Calcul des variations
  • Vendredi 13/3 -- TD
    • Attention : pas de cours le 19/3.
  • Vendredi 20/3 Programmation dynamique en horizon fini et infini, exercices et exemples

    • Travaux Pratiques

    Les TP sont assurés par Jean-Baptiste Apoung-Kamga. Les TP débuteront le vendredi 6/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 22/1 vous pouvez voir ce poly de calcul différentiel et en particulier les pages 93 et suivantes.
    Pour le cours du 23/1 vous pouvez voir le livre de Ciarlet, chapitre 7.2. et/ou le poly précédent, chapitre 9.
    Pour le cours du 29/1, Ciarlet, pages 158-166 (mais on n'a pas tout fait).
    Pour le cours du 30/1 Ciarlet, Chap. 8.4 (sauf relaxation).
    Pour le cours du 6/2, Ciarlet Chap. 8.5 (grad. conjugué) et 8.6 (grad. projeté).
    Pour le cours du 12/2 Ciarlet 8.6 (pénalisation).
    Pour le cours du 13/2 Ciarlet chapître 9 (en particulier 9.3 et 9.4).
    Pour le cours du 6/3, Ciarlet, 10.2 et 10.3
    Pour les cours du 13/3 et le TD suivant, voir le chapitre 4 (calcul des variations) de ce poly de Guillaume Carlier sur l'optimisation dynamique.
    Pour le cours du 20/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.

    Devoir maison pour le 19 mars 2014.
    Sujet de l'examen du 25 mars 2014.
    Sujet du rattrapage du 24 juin 2014.

    Devoir maison pour le 17 mars 2015.