Méthodes du premier ordre pour l'optimisation non convexe et non lisse
M2, Sorbonne Université (5MM71-NCO)
Annonces
L'examen du 1er semestre aura lieu le mardi 9 janvier 2024 de 13h30 à 15h30.
Présentation générale
Ce cours abordera les aspects théorique et numérique des méthodes d'optimisation dites du premier ordre. On se placera dans un cas très général (c'est-à-dire sans nécessairement faire d'hypothèses sur la convexité du problème ou sa régularité). Une attention particulière sera accordée à l'étude des comportements des algorithmes les plus courants, en particulier quant à leur convergence.
Ce cours s'adresse à la fois aux futurs doctorants en optimisation continue et aux ingénieurs désireux d'appliquer des méthodes d'optimisation pour résoudre des problèmes concrets.
Il s'agit d'un cours mutualisé entre les M2 Mathématiques de la modélisation (MathMod) et Apprentissage et Algorithmes (M2A).
Plan détaillé du cours
Cours 1 : Révisions [TD 1]
Introduction à l'optimisation
Éléments de topologie [A1]
Calcul sous-différentiel - cas convexe [A2]
Cours 2 : Optimisation non lisse et non convexe du premier ordre [TD 2]
Calcul sous-différentiel - cas général [A2]
Méthodes d'optimisation du premier ordre [B1]
Propriété de Kurdyka-Łojasiewicz [A3]
Cours 3 : Optimisation lisse et méthode du gradient [TD 3]
Fonctions régulières [A4]
Méthodes de gradient explicite [B2]
Cours 4 : Opérateur proximal et algorithme du point proximal [TD 4]
Opérateur proximal [A5]
Algorithme du point proximal [B3]
Cours 5 : Stratégies d'éclatement [TD 5]
Éclatement primal d'opérateurs - Forward-Backward Splitting [B4]
Éclatement de variables - Principe [B6]
Cours 6 : Dualité de Lagrange [TD 6]
Dualité min-max. Dualité lagrangienne. [A6]
Éclatement primal-dual - Méthode des directions alternées [B5]
Cours 7 : Dualité de Fenchel [TD 7]
Dualité de Fenchel et conjuguée convexe [A7]
Éclatement primal d'opérateurs - Éclatement de type Dykstra [B4]
Éclatement primal-dual - Algorithme de Chambolle-Pock [B5]
Cours 8 : Éclatement de variables
Calcul sous-différentiel - Sous-différentiels partiels [A2]
Éclatement de variables - Block-Coordinate Descent & PALM [B6]
Documents pédagogiques
Polycopié
Module A1 [lecture][impression]
Module A2 [lecture][impression]
Module A3 [lecture][impression]
Module A4 [lecture][impression]
Module A5 [lecture][impression]
Module A6 [lecture][impression]
Module A7 [lecture][impression]
Module B1 [lecture][impression]
Module B2 [lecture][impression]
Module B3 [lecture][impression]
Module B4 [lecture][impression]
Module B5 [lecture][impression]
Module B6 [lecture][impression]
Compléments
C1 : Rappels d'algèbre linéaire [lecture][impression]
C2 : Rappels d'analyse hilbertienne [lecture][impression]
IMPORTANT : La version [lecture] est la seule qui est mise à jour lors de petites corrections (coquilles, énoncés incomplets...). En cas de doute, merci de vous y référer en priorité.
Économisez de l'encre et du papier ! N'imprimez que si nécessaire et si possible en livret (2 pages par page, impression recto-verso). Préférez la version [impression], moins gourmande en couleur.
Feuilles d'exercices, problèmes & énoncés de TP
Il est fortement conseillé de travailler les feuilles d'exercices (TD) associées à chaque cours. Toutes les notions qui y sont abordées sont exigibles à l'examen. Pour aller plus loin, il est possible de travailler un problème (développement d'une thématique abordée dans un module) et / ou un énoncé de TP (qui permet d'appliquer certains algorithmes dans des cadres pratiques).
Problèmes
Fréchet-différentiabilité, Gateaux-différentiabilité, sous-différentiabilité convexe [A2]
Ensembles semi-algébriques, fonctions semi-algébriques [A3]
Optimisation convexe et systèmes linéaires [A4][B2][B6]
Opérateurs monotones maximaux [A5]
Distances de Bregman [A5][B3]
Algorithme ISTA [B4]
Algorithme d'Uzawa [A6][B4][B6]
Opérateur proximal de la variation totale [B4]
Algorithme de Chambolle-Pock dans le cas régulier [B5]
Algorithme ASAP [B6]
Légende : [A1] : module(s) associé(s) / Gras : problèmes conseillés / Normal : problèmes disponibles / Italique : problèmes non disponibles.
Énoncés de TP
Annales des examens
Disclaimer : Le polycopié ayant subi de profondes modifications depuis 2023, les sujets ci-dessous (et en particulier leurs corrigés) peuvent ne plus correspondre au programme actuel.
Bibliographie
Ressources bibliographiques utilisées dans ce cours (attention : fichier mis-à-jour régulièrement)
Quelques ouvrages de références :
Heinz H. Bauschke et Patrick L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2017
Amir Beck, First-Order Methods in Optimisation, SIAM, 2017
R. Tyrrell Rockafellar et Roger J-B Wets, Variational Analysis, Springer, 1998
Antonin Chambolle et Thomas Pock, An introduction to continuous optimization for imaging, Acta Numerica, 2016
Autres outils
Geogebra : calculatrice graphique, très utile pour la visualisation 3D (choisir la calculatrice 3D)
WolframAlpha : calculatrice formelle
Modalités de validation du cours
L'évaluation de ce module se fera par un examen écrit final.
Aucun document imprimé ne sera autorisé. Chaque étudiant a droit à une feuille recto-verso format A4 de notes manuscrites.
Informations pratiques
Les cours ont lieu sur le campus Pierre et Marie Curie les mardis de 13h30 à 16h30 et les jeudis de 9h30 à 12h30.
8 cours de 3h
Équipe pédagogique
Responsable du cours
Pauline Tan (contact : prénom.nom@sorbonne-universite.fr)