Optimisation convexe
Niveau M1
"Le module d'optimisation convexe aura pour but de présenter les algorithmes classiques et plus récents de l'optimisation non linéaire. Les outils et méthodes développées dans ce module trouvent des applications dans l'industrie mais également au service d'autres domaines scientifiques comme l'apprentissage automatique ou l'analyse numérique, dont certaines seront traitées en exemple.
À l'issue du module les élèves sauront :
- modéliser un problème réel comme un problème d'optimisation
- identifier à quelle classe de problème d'optimisation appartient un problème
- proposer une méthode de résolution et évaluer la solution obtenue
- implémenter un algorithme d'optimisation à direction de descente"
1. Programmation dynamique
- Chaîne de Markov contrôlée
- Programmation dynamique
- Horizon infini
- Réflexions finales
2. Convexité
- Ensembles convexes
- Fonctions convexes
- Analyse convexe
3. Optimality conditions
- Problème d'optimisation
- Cas sans contrainte
- Condition d'optimalité du premier ordre
4. Dualité
- Dualité lagrangienne
- Dualité forte
- Interprétation marginale du multiplicateur
- Retour sur la condition de Kuhn et Tucker
5. Optimisation et algorithmes
- Classification des problèmes d'optimisation
- Méthodes d'optimisation
6. Algorithmes de gradient
- Méthodes de descente et optimisation "boîte noire"
- Conséquences de la convexité forte
- Descente de gradient
- Gradient conjugué
7. Optimisation sous contraintes
- Construire une trajectoire admissible
- Des contraintes au coût
8. Méthodes de points intérieurs
- Rappels sur les problèmes d'optimisation convexes différentiables
- Optimisation sous contrainte d'égalité
- Méthodes de barrière
- Méthode de points intérieurs
- Application aux problèmes linéaires
9. Méthodes de gradient stochastique
- Cadre du problème
- Méthode "full batch"
- Méthodes stochastique et "mini batch"
Grands scientifiques de ce cours
- Harold William Kuhn
- Albert William Tucker