v1.12.0 (721)

Cours scientifique - OPT201 : Optimisation Différentiable: Théorie et Algorithmes

Domaine > Mathématiques et leurs applications.

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: OPT201 et OPT202. Dans la première partie, décrite ici, 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

Objectifs pédagogiques

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

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Avoir suivi le cours AO101 en 1ère année.

 

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Palaiseau

Vos modalités d'acquisition :

F=note finale, PR=Projet, TD=Travaux dirigés, E=Examen final - Session 1 Paris-Sud : F=0,5PR+0,25TD+0,25E - Session 1 ENSTA : F=0,5TD+0,5E -
Session 2 : F=1E

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
  • le rattrapage peut être demandé par l'étudiant si :
    7 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 3 ECTS

Le coefficient de l'UE est : 3

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Orsay

Vos modalités d'acquisition :

F=note finale, PR=Projet, TD=Travaux dirigés, E=Examen final - Session 1 Paris-Sud : F=0,5PR+0,25TD+0,25E - Session 1 ENSTA : F=0,5TD+0,5E -
Session 2 : F=1E

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
  • le rattrapage peut être demandé par l'étudiant si :
    7 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 3 ECTS

Le coefficient de l'UE est : 3

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Vos modalités d'acquisition :

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 sur le site pédagogique du cours.
  • 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.

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2 ECTS
  • Scientifique acquis : 2

Le coefficient de l'UE est : 2

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

  1. CM: 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.solutions.
    TD1: Calcul différentiel, fonctions convexes, existence et unicité de solutions.
  2. CM: 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).
    TP info: Introduction du sujet.
  3. CM: Conditions d'optimalité II (contraintes d'égalité et d'inégalité)
    • qualification des contraintes (avec Mangasarian-­Fromovitz), ,
    • conditions de Lagrange,
    • conditions de KKT.
    TD3: Conditions d'optimalité des problèmes avec contraintes d'égalité et d'inéga­lité.
  4. CM: 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).
    TP info: Recherche linéaire ou région de confiance.
  5. CM: 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.
    TD5: Conditions d'optimalité, recherche linéaire, Newton et Gauss-­Newton.
  6. CM: 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).
    TD6: Dualité
  7. Examen écrit d'1h30 + Fin du TP (1h30)

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é

Méthodes pédagogiques

En version papier: Syllabus (voir aussi https://who.rocq.inria.fr/Jean-Charles.Gilbert/ensta/optim.html ), réumé de cours; tous les documents (y compris les énoncés et solutions des TDs) sont disponibles sur le site pédagogique.
Veuillez patienter