Licence MiaSHS Troisième année
Optimisation
Modalités de contrôle des connaissances.
En première session l'évaluation est un contrôle continu. En deuxième session ce sera un examen.
Vous aurez deux DS cours notés sur 10, un DS long (le 26 avril) noté sur 20. Votre note finale en optimisation sera la somme des trois notes divisée par deux.
Les devoirs posés en 2018 et 2019
DS1, DS2, Sujet de l’examen de deuxième session (en 2017-2018 le DS3 n’a pas eu lieu et la deuxième session s’est déroulée de manière particulière car il a été interdit d’accéder à l’université pendant plusieurs semaines). Une correction pour l’exercice 2 (ce n’est pas la seule formulation possible).
Un corrigé du DS2 de 2019 Erratum
Quelques corrigés d'exercices
Feuille 2 : Exercice 10, Exercice 11, Exercice 12
Feuille 3 : Exercice 1, Exercice 2, Exercice 3
Plusieurs choix sont possibles pour mener les calculs : Programme linéaire P8 de l’exercice 3 de la feuille 3
Feuille 4 : Exercice 1, Exercice 4, Exercice 4 bis, Exercice 2, Exercice 6, Exercice 8, Exercice 9, Exercice 12, Exercice 13, Exercice 14.
Références
J.-B. Hiriart-Urruty, Les mathématiques du mieux faire, vol. 1, Ellipse (pour l'optimisation différentiable).
Feuilles d'exercices
Feuille 1, Feuille 2, Feuille 3, Feuille 4
Avancement du cours
Cours 1 ( 17/1) : Introduction. Exemples : théorème des quatre couleurs, droite de régression, algorithme de Dijkstra.
Cours 2 (25/1) : Algorithme de Dijkstra (fin), algorithme de Héron, méthode hongroise, un calcul de cotisation d’assurance.
Cours 3 (31/1) : Début du chapitre sur la programmation linéaire. Un exemple. Rappels d'algèbre linéaire (matrices, rang, produit scalaire, inégalité de Cauchy-Schwarz, Gram-Schmidt, matrice orthogonale). Sous-espaces affines de R^n, enveloppe affine d'une partie de R^n.
Cours 4 (7/2) : Convexes : définitions, exemples (dont les polyèdres), théorème de projection sur un convexe fermé, points extrémaux.
Cours 5 (21/2) : Enveloppe convexe, points extrémaux, faces, demi-droites extrémales, théorème de Minkowski (début de la démonstration). Deuxième heure : DS1.
Cours 6 (28/2) : Description des polyèdres sous forme standard (Ax=b, x>=0), points extrémaux, justification du fait que si le sup de <c,x> est atteint sur un tel convexe, il l'est en un point extrémal.
Cours 7 (7/3) : Programmation linéaire : quelques explications théoriques (pages 48 à 51 des notes de cours survolées ; une partie des calculs justifiant les propositions 3.15 et 3.16). Pratique sous forme de tableaux deux exemples.
Cours 8 (14/3) : Fin de la partie sur l'optimisation linéaire par l'exemple des pages 57-58-59 (recherche d'un point extrémal par l'introduction des variables artificielles s_i en étape 1, puis algorithme à partir du point trouvé (étape 2)). Optimisation différentielle : en un extremum local libre le gradient s'annule, la nature d'un point critique peut dans certaines conditions être déterminée par le spectre de la matrice hessienne. Détails pour les dimensions 1 et 2.
Cours 9 (21/3) : Signe d’une forme quadratique. Exemple en dimension 3 (trois méthodes). Fonctions convexes. En dimension 1 (définition, caractérisation avec les dérivées). Une fonction convexe a un minimum global en un point critique. En dimension d. Définition. Se ramener à la dimension 1.
Cours 10 (28/3) : Une fonction convexe a un minimum global en un point critique. Caractérisation d’une fonction convexe au moyen de sa matrice hessienne. La méthode de Newton : en dimension 1, en dimension d, Newton généralisée. Algorithme de descente (présentation de la méthode dans le cas d’une fonctionnelle quadratique).
Cours 11 (4/4) : Lignes et surfaces de niveau. Le gradient est orthogonal aux surfaces de niveau. Equations de droites ou plans tangents. Théorème des extrema liés. Exemples d’applications.