ECTS
6 crédits
Composante
UFR Mathématiques
Volume horaire
9h
Période de l'année
Semestre 2
Description
- Convexité: Ensembles et fonctions convexes
- Semi-continuité inférieure. Coercivité. Existence/unicité de minimiseurs.
- Cone normal. Cone tangent. Polarité. Théorème de Moreau pour les cones.
- Sous-différentielle. Conditions d'optimalité. Sous-différentiel de la somme (théorème de Moreau-Rockafellar). Composition par un opérateur linéaire.
- Revisite des conditions de KKT.
- Méthodes de point intérieur pour le cas lisse avec contraintes lisses
- Rappels sur la méthode de Newton, et sa convergence locale, BFGS.
- Programmation convexe lisse. Exemples de la programmation linéaire et quadratique. Condition de Slater.
- Principe des fonctions barrière, de chemin central. Théorème de convergence du chemin central (sous condition de Slater).
- Principe des méthodes de point intérieur. Théorème de convergence de la méthode (basée sur Newton) pour la programmation linéaire.
- Méthodes d'éclatement (primales) pour les problèmes structurés non-lisses
- Rappels sur l'algorithme du gradient.
- Méthode du gradient implicite. Opérateur proximal.
- Algorithmes du gradient projeté, et Forward-Backward. Théorème de convergence de Forward-Backward.
- Algorithme de Douglas-Rachford.
- Dualité convexe
- Conjuguée de Fenchel-Legendre. Théorème de Fenchel-Moreau sur la biconjuguée. Dualité entre les fonctions fortement convexes et C1,1C1,1.
- Calcul du gradient de la conjuguée. Calcul de l'opérateur proximal de la conjuguée (théorème de Moreau).
- Dualité de Moreau-Rockafellar. Exemple avec les problèmes convexes sous contraintes linéaires, lien avec le Lagrangien.
- Méthodes d'éclatement primales-duales pour les problèmes structurés non-lisses
- Algorithme du Lagrangien (vu comme l'algorithme du gradient sur le dual).
- Algorithme du Lagrangien Augmenté (vu comme l'algorithme proximal sur le dual).
- Algorithmes de Tseng et ADMM (vus comme les algorithmes Forward-Backward et Douglas-Rachford sur le dual).
Heures d'enseignement
- OptimisationCours Magistral4h
- Optimisation5h
Syllabus
- Hiriart-Urruty, J. B., & Lemaréchal, C. (2012). Fundamentals of convex analysis. Springer
- Rockafellar, R. T. (2015). Convex analysis. Princeton university press.
- Peypouquet J. (2015) Convex Optimization in Normed Spaces. Springer.
- Borwein J.M & Lewis, A.S. (2006). Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer.
Dernière mise à jour le 10 juillet 2023
