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 <a href="http://wwwdfr.ensta.fr/Cours/?usebdd=ensta&sigle=MAP-OPT2">MAP-OPT2</a>. 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
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 <a href="http://wwwdfr.ensta.fr/Cours/?usebdd=ensta&sigle=MAP-OPT2">MAP-OPT2</a>. 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
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.
- 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.
21 heures en présentiel (7 blocs ou créneaux)
réparties en:
- Cours magistral : 6
- Contrôle : 1
- Travaux dirigés en salle info : 6
- Petite classe : 8
Diplôme(s) concerné(s)
Parcours de rattachement
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 20Littérale/grade européenPour 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: 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 devra 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. Il s'agira en particulier d'implémenter et de tester plusieurs algorithmes d'optimisation et/ou plusieurs approches de résolution.
Le projet se fera en binôme.
Chaque enseignant proposera 1 sujet à son groupe. L'encadrement se fera pendant 5 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 fera sous forme de contrôle continu, au cours des séances.
<b>La note du projet interviendra à hauteur de 40% dans la note finale.</b>
<!-- L'évaluation du travail réalisé se fera lors de la 13-ième séance : chaque binôme présentera ses résultats dans un exposé de 15 minutes. La présentation se fera devant l'enseignant ayant encadré le projet. De plus, chaque binôme remettra un court rapport de synthèse (de 2-3 pages maximum). Celui-ci sera remis 2 jours AVANT la 13-ième séance. -->
Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)- Pour l'interrogation écrite: 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 devra 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. Il s'agira en particulier d'implémenter et de tester plusieurs algorithmes d'optimisation et/ou plusieurs approches de résolution.
Le projet se fera en binôme.
Chaque enseignant proposera 1 sujet à son groupe. L'encadrement se fera pendant 5 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 fera sous forme de contrôle continu, au cours des séances.
<b>La note du projet interviendra à hauteur de 40% dans la note finale.</b>
<!-- L'évaluation du travail réalisé se fera lors de la 13-ième séance : chaque binôme présentera ses résultats dans un exposé de 15 minutes. La présentation se fera devant l'enseignant ayant encadré le projet. De plus, chaque binôme remettra un court rapport de synthèse (de 2-3 pages maximum). Celui-ci sera remis 2 jours AVANT la 13-ième séance. -->
- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 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.
Pour les étudiants du diplôme Master 1 Mathématiques et Applications
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
- Crédits ECTS acquis : 3 ECTS
Le coefficient de l'UE est : 3
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
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