Optimisation Convexe: Algorithmes et Applications en Appréntissage

Calendrier, planning et modalités

6 séances de cours-TD, les 16, 20 et 30 septembre, 7 et 14 octobre, 4 novembre, pour un total de 12hCM+6hTD. Chaque séance a lieu de 14h à 17h15 (sauf le 20/9, où ce sera 9h45-13h ; voir ADE pour les salles précises à chaque fois).

4 séances de TP par groupe.
Les TP sont assurés par Roland Denis et Frédéric Lagoutière.

Programme du cours

  • 1) (séance du 16/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 20/9)
    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 30/9)
    Analyse convexe et dualité convexe
    Définition de la transformée de Fenchel-Legendre. f**=f. Lien avec le sous-différentiel et l'opérateur proximal. Dualité.
    TD
    Exos 1-3 de la feuille de TD.
  • 4) (séance du 7/10)
    Encoure dualité et algorithmes basés sur la dualité
    Uzawa pour les contraintes d'égalités linéaires, inégalités linéaires, inégalités convexes. Lagrangien augmenté. Convergence d'Uzawa avec contraintes déinégalités linéaires.
    TD
  • 5) (séance du 14/10)
    Algorithme de gradient stochastique
    TD
  • 6) (séance du 4/11)
    Compléments
    TD


    • Exercices et Annales

    Feuille de TD: ici.

    Annales d'examen:
    2022;
    2023 (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).