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
Exos 4-6 de la feuille de
TD.
5) (séance du 14/10)
Algorithme de gradient stochastique
Principe et preuve de convergence
de l'algorithme de gradient stochastique pour une fonction convexe ou elliptique. Exemples d'applications. quelques mots sur
l'importance sampling.
TD
Exos 7, 8, 10, 11 de la feuille de
TD.
6) (séance du 4/11)
Compléments
Exemples de problèmes d'optimisation convexe en apprentissage:
séparation linéaire de nuages de points;
résolution sparse d'un système linéaire par
minimisation de la norme 1.
TD
Exos 12, 14 de la feuille de
TD.
Exercices, Annales, et Examen
Feuille de TD: ici.
Annales d'examen:
2022;
2023 (ici une version avec corrigé).
Examen du 9 décembre 2024: sujet (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).