Programme (contenu détaillé) :
– Introduction à l’optimisation sous contrainte : définitions et généralités, questions d’existence de solutions, convexité et unicité
– Conditions d’optimalité : conditions du premier et du second ordre en optimisation différentiable sans contrainte, conditions de Karush-Kuhn-Tucker (KKT) en optimisation différentiable avec contraintes, notion de Lagrangien
– Algorithmes pour l’optimisation sans contrainte : algorithme du gradient (pas fixe, pas optimal), algorithme de Newton, problèmes de moindres carrés linéaires et non linéaires
– Introduction à l’optimisation sous contraintes linéaires : formalismes de modélisation, caractérisation de l’espace de recherche, interprétation géométrique, résolution graphique, lien avec les conditions de KKT, algorithme du simplexe, méthode des dictionnaires, complexité, dualité d’un problème de PL, théorèmes de dualité forte et faible, théorèmes des écarts complémentaires, lemme de Farkas, théorème des alternatives
Polycopiés de cours détaillés fournis.
Mots clés : optimisation différentiable, conditions d’optimalité du premier et du second ordre, algorithmes du gradient, Newton, problèmes de moindres carrés, programmation linéaire et algorithme du simplexe.
Objectifs
A la fin de ce module, l’étudiant.e devra avoir compris et pourra expliquer (principaux concepts) :
- Les notions d'extremum local et de convexité
- Caractérisation d'un extremum local par des conditions d'optimalité : conditions du premier et du second ordre en optimisation différentiable sans contrainte, conditions de Karush-Kuhn-Tucker (KKT) en optimisation différentiable avec contrainte.
- Les premiers algorithmes pour l'optimisation sans contrainte : algorithme du gradient (pas fixe, pas optimal), algorithme de Newton, problèmes des moindres carrés linéaires et non linéaires.
- L’optimisation sous contraintes linéaires (Programmation linéaire/PL): modélisation en PL, caractérisation de l’espace de recherche, interprétation géométrique, principe de résolution, algorithme du simplexe, méthodes des dictionnaires, complexité, dualité.
L’étudiant devra être capable de :
Choisir et mettre en œuvre et implémenter une méthode d'optimisation pertinente et numériquement efficace pour un problème d'optimisation différentiable sans contrainte ou pour un problème de programmation linéaire.
Liste des compétences : 1.1, 1.3, 1.4, 2.1, 2.5, 3.1
Pré-requis
Calcul différentiel : savoir calculer un gradient et une hessienne. Lien avec la différentielle
Algèbre linéaire : savoir diagonaliser une matrice, calculer les valeurs propres, notion de semi-définie positivité.
Évaluation
L’évaluation des acquis d’apprentissage est réalisée en continu tout le long du semestre. En fonction des enseignements, elle peut prendre différentes formes : examen écrit, oral, compte-rendu, rapport écrit, évaluation par les pairs…
