École Nationale Supérieure de Techniques Avancées
	Année scolaire 2020/2021
	Cours SOD314
	Optimisation non différentiable et méthodes proximales

Enseignants responsables

Pierre Carpentier, Andres Contreras

Objectifs

A partir des outils de l'analyse convexe, l'objectif de ce cours est de présenter les algorithmes de résolution des problèmes d'optimisation non différentiables. Le cours fait appel à de nombreux exemples d'application et met en évidence la nécessité de prendre spécifiquement en considération le caractère non différentiable des problèmes.

• La première séance est consacrée à l'exposé des principales propriétés des fonctions sous-différentiables, dans le cadre de l'analyse convexe. On détaillera les conditions d'optimalité générales dans le cas sous-différentiable, ainsi que les propriétés de différentiabilité des fonctions marginales en optimisation.
• Les trois séances suivantes présentent plusieurs classes d'algorithmes en optimisation sous-différentiable, leurs applications dans le cadre de la relaxation Lagrangienne et leur utilisation en dualité : méthodes proximales et algorithmes du gradient proximal, méthodes de plans sécants et algorithme des faisceaux, méthode du recouvrement progressif en optimisation stochastique.
• Les deux dernières séances seront consacrées à des travaux pratiques effectués en Julia, un langage de programmation particulièrement adapté à l'optimisation.

Programmation 2020/2021

Le cours sera donné cette année en anglais, avec des supports de cours en français.

• Séance No.1
  Mardi 02 février 2021, 8h30 - 12h15, Salle x.x.xx
  Sous-différentiabilité. Calcul sous-différentiel.
  • énoncé et corrigé des travaux dirigés de la séance No.1
• Séance No.2
  Mardi 09 février 2021, 8h30 - 12h15, Salle x.x.xx
  Algorithmes en optimisation sous-différentiable. Méthodes proximales.
  • énoncé et corrigé des travaux dirigés de la séance No.2
• Séance No.3
  Mardi 16 février 2021, 8h30 - 12h15, Salle x.x.xx
  Dualité et relaxation lagrangienne. Travaux dirigés.
  • énoncé et corrigé des travaux dirigés de la séance No.3
• Séance No.4
  Mardi 02 mars 2021, 8h30 - 12h15, Salle x.x.xx
  Lagrangien augmenté. Algorithme du recouvrement progressif.
• Séance No.5
  Mardi 09 mars 2021, 8h30 - 10h00, Salle x.x.xx
  Examen écrit.
• Séance No.5 (suite)
  Mardi 09 mars 2021, 10h15 - 12h15, Salles x.x.xx et x.x.xx
  Travaux pratiques en Julia : méthode du gradient proximal.
• Séance No.6
  Mardi 16 mars 2021, 8h30 - 12h15, Salles x.x.xx et x.x.xx
  Travaux pratiques en Julia : méthodes de plans sécants et faisceaux.

Notes de cours (PDF)

• En-tête et table des matières

• Chapitre 1 - Sous-différentiabilité

• Chapitre 2 - Méthodes proximales

• Chapitre 3 - Méthodes de plans sécants et de faisceaux

• Chapitre 4 - Algorithme du recouvrement progressif

• Bibliographie

Documents et codes pour les travaux pratiques

• le notebook du TP "Gradient proximal",
• le notebook TP "Méthodes de faisceaux",
• le fichier de données associé.

Modalités d'évaluation

• Examen écrit
• Devoir sur table d'une heure et demie. Les documents de cours (polycopié, notes) sont autorisés.
• Travaux pratiques en Julia
Les étudiants constituent des binômes. Les TPs sont réalisés en langage Julia, sous la forme de notebooks Jupyter.
• Les résultats du premier TP (gradient proximal) sont à remettre sous forme d'un notebook contenant les codes et les plots demandés.
• Les résultats du second TP (méthodes de faisceaux) sont à remettre sous forme d'un notebook contenant les codes et les plots demandés, ainsi que les commentaires et interprétations des méthodes.
La note finale du cours est obtenue en faisant la moyenne pondérée de la note de l'examen écrit (60%) et de la note des TPs (40%).

Mise en oeuvre de Julia

• Installation de Julia et Jupyter sur les ordinateurs du réseau enseignement ENSTA
• se connecter avec ses identifiants ENSTA
• entrer la commande : useuma julia
• entrer la commande : julia_sumo_add
• entrer la commande : julia_notebook_installkernel
• Installation de Julia et Jupyter sur un ordinateur portable personnel
• installer Python (distribution recommandée : anaconda)
• installer Julia (version recommandée : 1.3 ou plus récent)
• entrer la commande : julia
• dans Julia, entrer les commandes :
• add JuMP
• add OSQP
• add IJulia
• add Pyplot
• Utilisation de Julia et Jupyter
• entrer la commande : julia
• dans Julia, entrer les commandes :
• using IJulia
• notebook()