Requirements- Analyse S1, Optimisation L3
Program requirementsCC+examen
TeacherMaxime Laborde
Weekly hours 2 h CM , 2.5 h TD
Years M1 mathématiques (MFA) M1 Mathématiques et Informatique

Syllabus

  • Faire de l’analyse non-lisse. Les problèmes faisant intervenir des fonctions non différentiables, voire non définies partout, apparaissent naturellement dans les applications. Nous introduirons des outils permettant de gérer ce type de problèmes, tels que :

    • la notion de sous-différentielle, qui permet de donner un sens au gradient d'une fonction convexe non différentiable;
    • la notion de cône normal, qui permet de « dériver » un ensemble de contraintes;
    • la notion de conjuguée, qui permet de transformer un problème d'optimisation en un autre, possiblement plus simple. Un des objectifs principaux du cours est de savoir faire du calcul, c'est-à-dire être capable de calculer ces objets pour des problèmes simples.

  • Savoir implémenter un algorithme. L'objectif est que les étudiantes soient capables de résoudre la plupart des problèmes liés à l'optimisation convexe à la fin de ce cours. Cela passe par une étape de modélisation (savoir transformer un problème donné en problème d'optimisation), une étape de standardisation (savoir transformer un problème d'optimisation sous une forme équivalente mais standardisée) et une étape de mise en oeuvre d'un algorithme (savoir calculer les étapes de l'algorithme, et les paramètres le régissant). En particulier le cours se focalisera sur les méthodes d'éclatement, qui permettent de résoudre les problèmes faisant intervenir des sommes de fonctions lisses et/ou non lisses, éventuellement composées avec des opérateurs linéaires, et éventuellement sous contraintes. L'outil technique central sera l'opérateur proximal, qu'il faudra savoir calculer pour des fonctions simples.

Ce cours prépare à des domaines variés :

  • Traitement du signal et de l'image
  • Informatique théorique (programmation linéaire, complexité)
  • Économie mathématique
  • Statistique et Machine Learning
  • Mathématiques appliquées au sens large: contrôle optimal, calcul variationnel

Contents

  • Ensembles convexes

    • Convexité

      • Définitions et calcul. Polyèdres.
      • Projection sur un convexe.

    • Approximation d'un convexe

      • Cônes.
      • Cône polaire et calcul. Théorème du cône bipolaire.
      • Cônes tangent et normal à un convexe.

  • Analyse convexe non lisse

    • Fonctions convexes semi-continues

      • Fonctions à valeurs réelles étendues.
      • Fonctions semi-continues inférieurement.
      • Théorèmes d'existence des minimiseurs.
      • Fonctions convexes et fortement convexes.

    • Sous-différentiel d'une fonction convexe.

      • Sous-différentiel
      • Calcul sous-différentiel
      • Conditions d'optimalité: Théorèmes de Fermat, Lagrange, KKT

    • Conjuguée de Fenchel

      • Définition et calcul de la conjuguée.
      • Propriétés duales de la conjuguée: Théorème de Fenchel-Young, Formule de Legendre-Fenchel.
      • Dualité de Fenchel-Rockafellar. Théorème de représentation primale-duale.

  • Algorithmes pour l'optimisation convexe

    • Algorithmes élémentaires

      • Algorithme du gradient
      • Algorithme proximal
      • Calcul proximal

    • Algorithmes d'éclatement

      • Eclatement simple: Algorithme du Gradient Proximal.
      • Eclatement total: Algorithme de Davis-Yin
      • Eclatement composite total: Algorithme de Yan

Bibliography

  • Notes de cours (disponibles ici)
  • Peypouquet, J. (2015). Convex optimization in normed spaces: theory, methods and examples. Springer.
  • Hiriart-Urruty, J. B. (2009). Optimisation et analyse convexe : Exercices et problèmes corrigés avec rappels de cours. EDP Sciences, Ulis.
  • Hiriart-Urruty, J. B., & Lemaréchal, C. (1996). Convex analysis and minimization algorithms I: Fundamentals (Vol. 305). Springer science & business media.
  • S. Boyd and L. Vandenberghe (2004). Convex Optimization. Cambridge university press.