Optimisation Convexe: Algorithmes et Applications en Appréntissage

Calendrier, planning et modalités

6 séances de cours-TD, les 14 septembre, 5, 12 et 19 octobre, 2 et 9 novembre, pour un total de 12hCM+6hTD. Chaque séance a lieu de 14h à 17h15 et toujours en salle 116 du quai 43.

4 séances de TP par groupe.
Les TP sont assurés par Roland Denis et Carlo Marcati.
L'examen écrit (50% de la note) est prévu le 16 novembre. Le reste de la note est basé sur un TP noté.

Programme du cours

  • 1) (séance du 14/9)
    Introduction à l'optimisation et à ses applications en apprentissage.
    Exemples de problèmes d'optimisation. Rappels sur l'existence des minimiseurs et leur unicité.
    Algorithmes de gradient dans le cas lisse et uniformément convexe.
    Algorithme de gradient à pas fixe pour la minimisation sans contraintes. Minimisation convexe sous contraintes, projection. Gradient projeté.
  • 2) (séance du 5/10)
    Gradient et gradient accéléré pour l'optimisation lisse.
    Ordre de convergence 1/k; ordre 1/k2 pour le gradient accéléré de Nesterov.
    Optimisation non-lisse.
    Sous-différentiel et algorithme du sous-gradient.
    Opérateur proximal. Algorithme du gradient proximal pour min f+g, dans le cas f elliptique ou juste lisse. Méthodes ISTA et FISTA.
  • 3) (séance du 12/10)
    Analyse convexe et dualité convexe
    Définition de la transformée de Fenchel-Legendre. f**=f. Lien avec le sous-différentiel. Dualité.
    TD
    Exos 1-3 de la feuille de TD.
  • 4) (séance du 19/10)
    Encoure dualité et algorithmes basés sur la dualité
    TD
  • 5) (séance du 2/11)
    Algorithme de gradient stochastique
    TD
  • 6) (séance du 9/11)
    Compléments
    TD


    • Exercices, Annales, et Examen

    Feuille de TD: ici.

    Annales d'examen:
    2022;
    2023 (ici une version avec corrigé).
    2024 (ici une version avec corrigé).
    2025 (ici une version avec corrigé).

    Références

    Un poly informel sur le contenu du cours: voir ici (en anglais).
    Sinon vous pouvez consulter le livre de Ph. Ciarlet Introduction à l'analyse numérique matricielle et à l'optimisation, chapitre 8 et l'article original de Beck et Teboulle sur la méthode FISTA; le livre récent de G. Carlier Classical and Modern Optimization (en général pour l'optimisation, y compris les bases de calcul différentiel mais également les applications en sciences de données au chapitre When optimization and data meet).