Optimisation et simulation numérique, M2 MathSV

Partie sur l'optimisation déterministe. Pour la partie d'optimisation stochastique, donnée par S. Allassonnière, voir sa page web.

Calendrier et modalités

3 séances, le 25/9, 29/9 et 2/10. Chaque séance fait 3h + pause
Modalité d'examen : 1 devoir maison + 1 projet à faire par binômes (un seul projet pour optimisation déterministe + optimisation stochastique).

Programme du cours et références

  • 1) (séance du 25/9) Introduction à l'optimisation et à l'analyse convexe.
    Rappels sur l'existence des minima, semicontinuité, conditions d'optimalité d'ordre 1 et 2, multiplicateurs de Lagrange.
    Définitions équivalentes de fonctions convexes, sous-différentiel, conditions suffisantes d'optimalité, transformée de Legendre-Flenchel, théorème de dualité.
    Références : essentiellement le livre de R. T. Rockafellar Convex Analysis.

  • 2) (séance du 29/9) Algorithmes de gradient.
    Algo de gradient à pas fixe et lien avex le théorème des contractions (point fixe), variantes: pas ariable, pas optimal ; l'exemple de la minimisation quadratique ; algo de sous-gradient et preuve de convergence avec un pas bien choisi.
    Condition d'optimalité dans les problèmes convexes avec contraintes, conditions de Kuhn-Tucker ; projection sur un convexe ; algos de gradient et sous-gradient projetés ; exemples de projection.
    Références : essentiellement le livre de Ph. Ciarlet Introduction à l'analyse numérique matricielle et à l'optimisation, chapitre 8.

  • 3) (séance du26/10) Sujets plus avancés
    Algorithme d'Uzawa (dualité pour la minimisation convexe sous contraintes).
    Programmation linéaire : généralités, qqs mots sur l'algo du simplexe, dualité, l'eemple du transport optimal.
    Algorithme FISTA pour la minimisation de f(x)+g(x) avec f lisse et g non. Description de la méthode ISTA pour g(x)=║x║1 ; lien avec les algos proximaux et le gradient à pas fixe ; ordre de convergence du gradient à pas fixe sans ellipticité ; idée et détails de la méthode FISTA.
    Références : Uzawa = Ciarlet, chapitre 9 ; programmation linéaire = Ciarlet, chapitre 10 ; FISTA = voir l'article original de Beck et Teboulle.

    • Devoir Maison

    Voici le sujet du devoir maison, à rendre pour le 23/10: sujet.