Optimisation différentiable

Objectif

Description du cours

L'optimisation est une discipline mathématique qui étudie les problèmes visant à déterminer les meilleures valeurs pour des variables, sous certaines contraintes, afin de minimiser ou maximiser un critère fonctionnel. Ce cours présente les concepts fondamentaux, les méthodes et les principaux algorithmes de l'optimisation en dimension finie.

L'optimisation s'appuie fortement sur l'analyse convexe. Par conséquent, le cours introduit également des notions essentielles et démontre des résultats importants de cette branche des mathématiques, qui se situe à l'intersection de l'algèbre linéaire et de l'analyse non linéaire.

Objectifs d'apprentissage

À l'issue de ce cours, les étudiants seront capables de :

1. Calculer des gradients et des hessiennes de fonctions à plusieurs variables
2. Déterminer les points extrémaux d'une fonction à plusieurs variables et identifier leur nature grâce à la hessienne
3. Établir les conditions de Karush-Kuhn-Tucker (KKT) et les résoudre pour des problèmes d'optimisation sous contraintes
4. Formuler le problème dual d'un problème d'optimisation convexe différentiable et l'utiliser pour résoudre les conditions KKT
5. Construire un algorithme de descente de gradient pour résoudre un problème d'optimisation

Évaluation

- à 2/3 de la note de l'examen écrit de fin de semestre;
- à 1/3 d'une note de contrôle continu, elle-même composée d'une note de mi-parcours (50%), d'une note d'assiduité (25%) et d'une note de participation (25%).

Plan

Le cours est structuré comme suit.

1. Typologie des problèmes d'optimisation
2. Gradient et hessienne. Convexité des fonctions différentiables
3. Conditions nécessaires du premiers et second ordre
4. Conditions suffisantes du premiers et second ordre
5. Méthode du nombre d'or et algorithme de dichotomie
6. Descente de gradient: convergence pour les fonctions convexes
7. Descente de gradient: convergence pour les fonctions fortement convexes
8. Méthode de Newton
9. Optimisation sous contraintes d'égalité: multiplicateurs de Lagrange
10. Théorème de Lagrange. Exemples d'application.
11. Preuve du Théorème de Lagrange. Conditions du second ordre.
12. Optimisation sous contraintes d'inégalité :Théorème de Karush-Kuhn-Tucker
13. Méthodologie générale de résolution d’un problème d’optimisation 
14. Dualité

Références

• Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge University Press.
• Lectures on Modern Convex Optimization, A. Nemirovski and A. Ben-Tal, SIAM.
• Edwin K. P. Chong, Stanislaw H. Zak, An Introduction to Optimization, 4e édition, Volume 76 de la série Wiley en mathématiques discrètes et optimisation, John Wiley & Sons, 2013.
• Jorge Nocedal, Stephen J. Wright, Numerical Optimization, Springer, 2006.
• Frederick S. Hillier, Gerald J. Lieberman, Introduction to Operations Research, 10e édition, McGraw-Hill Education, 2015.