Optimisation convexe, M2 MathSV et MathAléa

Ce cours constitue 1/3 d'un cours qui s'appelle Bayesien, MCMC, Optimisation du M2 Mathématiques de l'Aléatoire (MathAléa) ainsi qu'1/3 d'un cours qui s"appelle Optimisation et Simulation Numérique du M2 Mathématiques du Vivant (MathSV). La valeur en ECTS et les modalités d'examen changent entre les deux masters.

Calendrier, planning et modalités

3 séances, le 1, 8 et 15 obtobre. 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 ; de plus, pour les étudiants de MathSV il y aura aussi un projet informatique à faire par binômes (un seul projet pour les parties optimisation déterministe + optimisation stochastique, à confirmer).
Date de l'examen : jeudi 5 novembre 2015, 10h-12h, salle 117-119.

Programme du cours et références

  • 1) (séance du 1/10) 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 8/10) Algorithmes de gradient.
    (tout d'abord on terminera la preuve de la dualité laissée en suspens la première fois).
    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 (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 15/10) Sujets plus avancés
    Algorithme d'Uzawa (dualité pour la minimisation convexe sous contraintes d'inégalités ; conditions d'optimalité de Kuhn-Tucker).
    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 ; FISTA = voir l'article original de Beck et Teboulle.

  • Exercices

    Vous pouvez voir le sujet du devoir maison donné en 2014 : sujet.
    Regarder également ces exercices supplémentaires Avec solutions (3 exos corrigés sur 6) et (2 corrigés sur 4).