Scolarité M2 (sauf MIC, MIDS)
- Mme Chatoux
- bureau 5055
- 01 57 27 93 06
- Mme Prudlo
- bureau 5055
- 01 57 27 93 06
Optimisation
6 ECTS, semestre 2, 6 semaines
| Prérequis | Analyse S1, Optimisation L3 |
| Validation | CC+examen |
| Enseignant | Yves Achdou |
| Horaires hebdomadaires | 4 h CM , 6 h TD |
| Années | M1 Mathématiques et Informatique M1 mathématiques (MFA) |
Sommaire
- 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 $C^1,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).
Bibliographie
- 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.