Optimisation Convexe: Algorithmes et Applications en Appréntissage

Calendrier, planning et modalités

6 séances de cours-TD, les 15 et 29 septembre, 6 et 13 octobre, 3 et 17 novembre, pour un total de 12hCM+6hTD. Chaque séance a lieu de 14h à 17h15 et toujours en salle 5 du déambulatoire, sauf le 6/10 en salle 3 (voir ADE).

4 séances de TP par groupe.
Les TP sont assurés par Roland Denis et Frédéric Lagoutière.
L'examen écrit (50% de la note) est prévu le 8 décembre. Le reste de la note est basé sur un TP noté.

Programme du cours

  • 1) (séance du 15/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 29/9)
    Gradient et gradient accéléré pour l'optimisation lisse.
    Optimisation non-lisse.
  • 3) (séance du 6/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 13/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, Annales, et Examen

    Feuille de TD: ici.

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

    Références

    Un poly informel sur le contenu du cours: voir ici (en anglais ; version revisée le 13/10).
    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).