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

Calendrier et modalités

Cours : 30h de CM, le jeudi 15h45-17h15, salle 427 bât 450, et le vendredi 13h30-16h30, salle B13 bât 460 (voir calendrier précis plus en bas) ;
TP : 4 séances de 2h le jeudis 13h30-15h30, salle 236 bât 440 (option modélisation) et le vendredi 1àh-12h, salle 242 bât 440 (option stat);
Modalité d'examen : 1 écrit (75%) + 1 devoir maison de TP (25%).

Séances

19/1 (1h30), 20/1 (3h),
27/1 (3h),
2/2 (1h30) et 3/2 (3h) + TP,
10/2 (3h),
16/2 (1h30) + TP,
semaine du 20-26 février : TP,
pas de cours pendant les vacances d'hiver
8/3 (1h30) et 9/3 (3h)
15/3 (1h30) et 16/3 (3h)
22/3 (1h30) et 23/3 (3h) + TP
Examen le 29/3

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 19/1 Introduction à l'optimisation, existence des optima, semicontinuité
  • Vendredi 20/1 Conditions d'optimalité, multiplicateurs de Lagrange, exemples et exercices
  • Vendredi 27/1 Méthodes de Newton, théorème des contractions, introduction à la minimisation des fonctions convexes, méthode de la section dorée en dim 1.
  • Jeudi 2/2 Fonctions convexes, strictement convexes et elliptiques. Algorithme du gradient à pas fixe.
  • Vendredi 3/2 Algorithme du gradient à pas variable, pas optimal, gradient conjugué, applications aux problèmes quadratiques et systèmes linéaires.
  • Vendredi 10/2 Minimisation convexe sous contrainte : conditions nécessaires et suffisantes d'optimalité, projection sur un convexe fermé, algorithme du gradient projeté, méthode de pénalisation. TD sur projection et optimisation sous contraintes.
  • Jeudi 16/2 Kuhn-Tucker, dualité et algorithme d'Uzawa.
  • Jeudi 8/3 TD sur Uzawa ; encore sur les fonctions convexes : transformé de Flenchel et sous-gradient ; algorithme du sous-gradient.
  • Vendredi 9/3 Calcul des variations : équations d'Euler-Lagrange et conditions de transversalité, convexité (conditions suffisantes et unicité du minimum), exemples de non-existence et exemples de calcul.
  • Jeudi 15/3 Encore des exemples sur le calcul des variations ; discétisation.
  • Vendredi 16/3 Programmation dynamique en horizon fini et infini, exemples.
  • Jeudi 22/3 TD sur la programmation dynamique en horizon fini et infini.
  • Vendredi 23/3 Programmation linéaire, exemple du problème du transport optimal, polyhèdres et sommets, algorithme du symplexe.


    • Travaux Pratiques

    Les TP sont assurés par Aude Roudneff-Chupin

    Feuille 1 de TP (optimisation en dim 1)
    Feuille 2 de TP (optimisation sans contrainte)
    Feuille 3 de TP (optimisation sous contrainte)

    Annales et exercices

    Sujet du dévoir maison donné en cours l'an dernier, 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.

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

    Devoir maison du 15 mars (à rendre pour le 22 mars), avec corrigé.

    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.

    L'introduction et les chapitres 1 et 2 du poly suivant
    Poly de Guillaume Carlier sur l'optimisation dynamique
    présentent ce qui sera traité sur la programmation dynamique ; le chapitre 3 contient pratiquement tout ce qu'on a fait sur le calcul des variations. Pour le cours du 19/1 vous pouvez voir ce poly de calcul différentiel et en particulier les pages 93 et suivantes.
    Pour le cours du 20/1 vous pouvez voir le livre de Ciarlet, chapitre 7.2. et/ou le poly précédent, chapitre 9.
    Pour le cours du 27/1, Ciarlet, pages 158-166 (mais on n'a pas tout fait).
    Pour les cours des 2 et 3 février, Ciarlet, Chap. 8.4 (sauf relaxation).
    Pour le cours du 10 février, Ciarlet page 166 + Chap. 8.5 et 8.6 (sauf relaxation).
    Pour le cours du 16 février, Ciarlet Chap. 9.2, 9.3 et 9.4 (attention, on a été un peu rapides, sans faire trop de preuves).
    Pour le cours du 8 mars on peut éventuellement regarder les pages 102-106 (transformés) et les pages 214-218 (sous-différentiel) du livre Convex Analysis de R. T. Rocckafellar, et la page 127 (méthode de sous-gradient) du livre Numerical Optimization de J.F. Bonnans, J.C. Gilbert, C. Lemaréchal et C.A. Sagastizábal.
    Pour les cours des 9 et 15 mars, voir le chapitre 3 du poly de Guillaume Carlier sur l'optimisation dynamique
    Pour les cours des 16 et 22 mars , voir l'intro, le chapitre 1 et les sections 3.3 et 3.5 du poly de Guillaume Carlier sur l'optimisation dynamique, ainsi que ses exercices.
    Pour le cours du 23 mars, page 237 et suivantes du Ciarlet.