Archive 2022
RequirementsAnalyse S1, Optimisation L3
Program requirementsCC+examen
TeacherGuillaume Garrigos
Weekly hours 4 h CM , 5 h TD
Years M1 Mathématiques et Informatique M1 mathématiques (MFA)

Contents

  • 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).

Bibliography

  • 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.