Optimisation convexe, M2 MathSV

Ce cours constitue 1/3 d'un cours qui s'appelle Optimisation et Simulation Numérique du M2 Mathématiques du Vivant (MathSV).

Calendrier, planning et modalités

3 séances, le 29 septembre, le 6 et le 13 octobre. Chaque séance a lieu de 9h30 à 12h30 en salle 117-119, bât 425.

Modalité d'examen : il y aura un examen sur table (2/3 de la note) sur cette partie et la suivante (E. Kuhn) ; la dernière partie du cours (S. Faure) donnera lieu à une évaluation par projet informatique / compte-rendu de TP (1/3 de la note).
Date de l'examen : lundi 13 décembre 2016, 14h-17h, places 597 626 dans la salle 2 du bât 337.

Programme du cours et références

  • 1) (séance du 29/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.
    Références : pour la première partie du cours vous pouvez voir ce poly de calcul différentiel et en particulier les pages 93 et suivantes ; pour la suite essentiellement le livre de R. T. Rockafellar Convex Analysis.

  • 2) (séance du 6/10) Dualité ; Algorithmes de gradient.
    Dualité en optimisation convexe, points-selle et applications.
    Algo de gradient à pas fixe et lien avex le théorème des contractions (point fixe) ; algo de sous-gradient (sans preuves).
    Condition d'optimalité dans les problèmes convexes avec contraintes ; 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 du 13/10) Sujets plus avancés
    Algorithme d'Uzawa (dualité pour la minimisation convexe sous contraintes d'inégalités). Variante du Lagrangien Augmenté.
    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 l'algo de 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 ; FISTA = voir l'article original de Beck et Teboulle.

  • Exercices

    Vous pouvez voir le sujet du devoir maison donné en 2014 : sujet (version avec la solution de 3 exos sur 6 : ici).
    Regarder également ces exercices supplémentaires (avec la solution de 2 exos sur 4 : ici).
    Sujets d'examen de 2015/16 (attention, le format était différent, il y avait un écrit de 2h pour cette partie uniquement) : 1ère session, 2ème session. Corrigé de certains exercices de première session : ici (scanné).