Optimisation, M1 MAS

Calendrier, enseignants et modalités

Cours, TD et TP : 24h de CM + 18h de TD en deux groupes + 18h de TP en trois groupes.
Les CM sont assurés par Filippo Santambrogio, les TD par Laurent Laflèche, les TP par Dominique Sandri.
Calendrier des CM : le lundi 9h45-13h, salle Themis 69, du lundi 23/1 au lundi 3/4, sauf les lundis 13/2 (vacances), 20/2 (absence), 27/2 (partiel), 13/3 (absence) + une séance le mercredi 1er février 14h-17h15 en amphi 6 Marie Curie.
Pour le calendrier précis des TD/TP selons les groupes, voir ADE ou contacter les enseignants.
Modalité d'examen : CC+CT. La note de CC (50%) se base sur les compte-rendus de TP (30%) et le partie (20%). Celle de CT (50%) sur une épreuve finale de 3h.

Programme du cours

On traitera :
  • 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

    • Le programme est plus ou moins le suivant:

  • Lundi 23/1 Introduction à l'optimisation. Existence des optimiseurs, semicontinuité, conditions d'optimalité d'ordre 1 et 2 sans contraintes.
  • Lundi 30/1 Problèmes avec contraintes d'égalité ou inégalités ; multiplicateurs de Lagrange ; conditions d'ordre deux ; exemple des fonctions quadratiques sur la sphère.
  • Mercredi 1/2 Converge des suites itérées par le théorème des contractions. Méthodes de Newton pour F=0, convergence locale mais quadratique. Introduction aux fonctions convexes et à leur minimisation. Quelques algorithmes d'optimisation.
  • Lundi 6/2 Inégalités caractérisant les fonctions convexes et elliptiques. Convergence des algorithmes du gradient à pas fixe et à pas optimal, et de Newton à pas optimal.
  • Lundi 6/3 Minimisation quadratique et systèmes linéaires. algorithme du gradient conjugué. Résolution de Ax=b avec norme minimale.
  • Lundi 20/3 Conditions d'optimalité dans la minimisation convexe sous contraintes ; projection sur un convexe fermé ; algorithe du gradient projeté. Méthode de pénalisation.
  • Lundi 27/3 Analyse convexe, dualité et algorithmes basés sur la dualité
  • Lundi 3/4 Programmation linéaire. Algorithme du simplexe.

    • 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 les cours des 23/1 et 30/1 vous pouvez voir ce poly de calcul différentiel et en particulier les pages 93-99 (23/1) et 100-106 (30/1).
    Pour le cours du 1/2, cet autre poly peut être utile.
    Pour le cours du 6/2, voir le livre de Ciarlet ainsi que ces notes.
    Pour le cours du 6/3, à nouveau le livre de Ciarlet.

    Documents et exercices

    Première feuille de TD
    Sujet du partiel avec corrigé: ici.