Détails du cours MAP-OPT1

Differentiable Optimisation

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : MAP-OPT1
Titre français : Optimisation Différentiable: Théorie et Algorithmes [V1A]
Titre anglais : Differentiable Optimisation
Méta infos : modifiée le : 05/01/2017   par : guest   Nb de visiteurs : 552   annee : 2A      periode : 1      Rattachement/module : voie      unités : 2      ECTS : 2      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Non     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1,1a,1b    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : Jean-Charles GILBERT,   
Maitres de conférences : Jean-Charles GILBERT,    Anna DÉSILLES,    Filippo SANTAMBROGIO,    Jean-Baptiste APOUNG-KAMGA,    Emilien FLAYAC,   

Contenu

a pour prérequis : AO101
est prérequis pour : Les cours OROC-OP-ND, OROC-OP-OC, OROC-OP-DP, OROC-OP-GS
Objectifs :

1. Descriptif

L'optimisation est la discipline qui étudie les problèmes dans lesquels on cherche à déterminer «au mieux» des variables, qui sont contraintes d'appartenir à un ensemble donné. Déterminer «au mieux» signifie que l'on cherche à minimiser ou maximiser un critère fonctionnel dépendant de ces variables. Ce cours présente les concepts, résultats et algorithmes principaux de l'optimisation différentiable (par opposition à l'optimisation combinatoire ou discrète, qui ne sera pas abordée) en dimension finie (on ne parlera pas de commande optimale ou de problèmes de forme optimale). On s'intéresse donc à la fois aux aspects théoriques (existence et unicité de solution, conditions d'optimalité, technique de pénalisation, dualité) et aux aspects algorithmiques (algorithmes à directions de descente et à régions de confiance, algorithmes du gradient, du gradient conjugué, de Newton, de quasi-Newton, pénalisation, lagrangien augmenté, optimisation quadratique successive, algorithmes de dualité, algorithmes du simplexe et de points intérieurs en optimisation linéaire). Ce cours construit ainsi les bases sur lesquelles peuvent s'appuyer des disciplines plus avancées, telles que l'optimisation stochastique, l'optimisation robuste, l'optimisation conique (SDP, copositive, ...), l'optimisation non lisse, la commande optimale, l'optimisation de forme, l'apprentissage, etc. Cette branche de l'optimisation repose pour une bonne part sur l'analyse convexe, si bien que le cours introduit quelques notions et démontre quelques résultats de cette discipline importante des mathématiques, située entre l'algèbre linéaire et l'analyse non linéaire, qui jouent un rôle majeur en optimisation: projection, séparation, cône dual, conjugaison, sous-différentiabilité. On peut aussi voir l'analyse convexe, comme une voie d'accès à l'analyse non lisse, qui décrit des situations où sont utilisées des notions de différentiabilité plus faibles que la différentiabilité de Fréchet et qui est précieuse dans l'étude des inéquations variationnelles, en mécanique du contact, etc. Le cours est divisé en deux parties: MAP-OPT1 et MAP-OPT2. Dans la première partie, on se concentre sur les techniques de base: les conditions d'optimalité, les notions essentielles de l'analyse convexe, l'algorithmique des problèmes d'optimisation sans contrainte et la pénalisation. Remarque: ce cours compte pour 3 ECTs pour l'obtention du M1-Mathématiques Appliquées

2.Compétences à acquérir

Être capable grâce aux techniques de base de l’optimisation différentiable en dimension finie : - d’écrire les conditions d'optimalité ; - de manipuler les notions essentielles de l'analyse convexe ; - de mettre en œuvre l'algorithmique des problèmes d'optimisation sans contrainte et la pénalisation.

3. Programme des séances

1. Introduction : optimisation et analyse convexe + TD1 2. Conditions d’optimalité I : méthode et outils + TP1 3. Conditions d’optimalité II : égalités et inégalités + TD2 4. Conditions d’optimalité III (ordre 2) et méthodes de descente + TP2 5. Méthodes newtoniennes + TD3 6. Dualité + TD4 7. Contrôle des connaissances + TP3
Mots clés : Optimisation - Conditions d'optimalité - Méthodes Numériques - Algorithmes -
Recherche Linéaire - Gradient Conjugué - Newton - Quasi-Newton - Pénalisation
- Méthode du Simplexe - Méthode de points intérieurs - Dualité.
Objectives : Optimisation techniques are used in various scientific fields needed by the
engineer, both as basic numerical analysis tools and to solve optimum control
problems in systems. These problems are trajectory optimisation, shape
optimisation, parameter identification, etc.

The aim of the course is to present finite dimension optimisation theory
(optimality conditions and duality, etc.), as well as the main methods in
numeric optimisation (gradient, conjugate gradient, Newton, quasi-Newton, and
simplex algorithms, penalty function and duality approaches). We will
concentrate particularly on the principles that underlie these methods as well
as their implementation.

Numeric methods will be illustrated by presenting some industrial problems
involving optimisation. This presentation will be the subject of a lecture given
by EDF engineers.
Keywords : Optimisation – Optimality Conditions – Numerical Methods - Algorithms –
Linearsearch – Conjugate Gradient - Newton - Quasi-Newton - Penalty –
Simplex Method - Interior point method - Duality.
Supports :
  • Le polycopié en version papier. La version PDF du syllabus peut également être obtenue en suivant la procédure décrite à la PAGE DE CELUI-CI (notez que le document envoyé par email fait plus de 10 Mo, ce qui excède les capacités des boîtes mail de l'ENSTA; il vous faudra donc donner une autre adresse mail, du type gmail).
  • Un résumé, copie des supports de cours. La version couleur de ce résumé est également disponible en ligne ici.
  • Les sujets d'examen des années précédentes: 2015-2016, 2016-2017.
Biblio :
Contrôle : Interrogation écrite et projet à réaliser en TP.

- Pour l'interrogation écrite: durée 1h30; on peut consulter tous les
documents distribués au cours, ainsi que ses propres notes; les sujets des
années précédentes sont téléchargeables dans la rubrique "Bibliographie,
liens, supports".

- Pour le projet en Matlab/Scilab à réaliser en TP: l'élève doit résoudre
numériquement un problème où interviennent de manière essentielle des
techniques d'optimisation (modélisation, implémentation, utilisation
d'algorithmes d'optimisation divers, interprétation des résultats); le projet
peut se faire en binôme; chaque enseignant propose un sujet à son groupe; le
projet se fait pendant 3 séances, mais pourra demander un peu de travail de la
part de l'élève en dehors de celles-ci; lévaluation du travail réalisé se
fait sous forme de contrôle continu, au cours des séances.

Le calcul de la note finale se fait par la formule
P[(1-t)*min(ne,np)+t*max(ne,np)], où ne est la note de l'écrit, np est la note
du projet, t est généralement pris égal à 1/2 et P est le projecteur sur
l'intervalle [ne-e,ne+e] (avec e généralement pris égal à 3). Explications:
on fait la moyenne des deux notes, mais celle-ci ne peut améliorer ou
détériorer la note de l'écrit de plus de 3 points car c'est cette dernière
qui a le plus d'objectivité et reflète le mieux les connaissances de
l'élève.

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

lun. 12 sept. 2016   - 14:45 à 15:45 : Cours Magistral (CM)
programme : Introduction, rappels, différentiabilité, convexité: - introduction aux problèmes d'optimisation (tout en dimension finie), - existence et unicité de solutions, - caractérisation de la convexité d'une fonction par ses dérivées.
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT,
lun. 12 sept. 2016   - 16:00 à 18:00 : Petite Classe (PC)
programme : Calcul différentiel, fonctions convexes, existence et unicité de solutions. Enoncés et solutions du TD1
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Filippo SANTAMBROGIO, Emilien FLAYAC,
lun. 19 sept. 2016   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Conditions d'optimalité I - motivation, - cône tangent, - CN1 d'optimalité générique de Peano-Kantorovitch. Analyse convexe - projection sur un convexe, - séparation des convexes (Hahn-­Banach), - cône dual (lemme de Farkas).
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT,
lun. 19 sept. 2016   - 10:15 à 12:15 : TD en salle info (TD)
programme : Introduction du sujet.
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Jean-Baptiste APOUNG-KAMGA, Emilien FLAYAC,
lun. 26 sept. 2016   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Conditions d'optimalité II (contraintes d'égalité et d'inégalité) - qualification des contraintes (avec Mangasarian-­Fromovitz), , - conditions de Lagrange, - conditions de KKT.
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT,
lun. 26 sept. 2016   - 10:15 à 12:15 : Petite Classe (PC)
programme : Conditions d'optimalité des problèmes avec contraintes d'égalité et d'inéga­lité. Enoncés et solutions du TD3
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Filippo SANTAMBROGIO, Emilien FLAYAC,
lun. 03 oct. 2016   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Conditions d'optimalité III - conditions du 2-­ième ordre. Algorithmes de descente - algorithmes à directions de descente, - exemples de directions de descente (G, GC, N, qN, GN), - recherche linéaire (RL), - résultat de convergence (Zoutendijk).
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT,
lun. 03 oct. 2016   - 10:15 à 12:15 : TD en salle info (TD)
programme : Recherche linéaire ou région de confiance.
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Jean-Baptiste APOUNG-KAMGA, Emilien FLAYAC,
lun. 10 oct. 2016   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Algorithmes newtoniens - vitesse de convergence des suites, - algorithme de Newton pour la résolution de systèmes d'équations non linéaires et en optimisation, - algorithmes de quasi-­Newton, - Globalisation par RL.
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT,
lun. 10 oct. 2016   - 10:15 à 12:15 : Petite Classe (PC)
programme : Conditions d'optimalité, recherche linéaire, Newton et Gauss-­Newton. Enoncés et solutions du TD5
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Filippo SANTAMBROGIO, Emilien FLAYAC,
lun. 17 oct. 2016   - 09:00 à 10:00 : Cours Magistral (CM)
programme : Dualité - motivation - dualité min­max (introduction d'un problème dual, dualité faible, point-selle et dualité, produit-cartésien des points-selles, récupération d'une solution primale à partir d'une solution duale, schéma algorithmique), - dualisation de contraintes fonctionnelles (relaxation lagrangienne, relaxation lagrangienne augmentée).
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT,
lun. 17 oct. 2016   - 10:15 à 12:15 : Petite Classe (PC)
programme : Dualité. Enoncés et solutions du TD6
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Jean-Baptiste APOUNG-KAMGA, Emilien FLAYAC,
lun. 07 nov. 2016   - 09:00 à 10:30 : Contrôle (CC)
programme : Examen écrit d'1h30.
besoin : Vidéo,
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Jean-Baptiste APOUNG-KAMGA, Emilien FLAYAC,
lun. 07 nov. 2016   - 10:45 à 12:15 : TD en salle info (TD)
programme : Fin du TP.
besoin :
Intervenants : Jean-Charles GILBERT, Anna DÉSILLES, Jean-Baptiste APOUNG-KAMGA, Emilien FLAYAC,