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 (les 13 février et 12 mars), un DS long (le 16 avril) noté sur 20. Votre note finale en optimisation sera la somme des trois notes divisée par 2.
Des devoirs posés les années passées
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
Références
Notes de cours (peut-être évolutives)
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
Quelques corrigés d'exercices
Feuille 2 : Exercice 10, Exercice 11, Exercice 12
Feuille 3 : Exercice 1, Exercice 2, Exercice 3, Correction de l’exercice 10 (le numéro a changé)
Plusieurs choix sont possibles pour mener les calculs : Programme linéaire P8 de l’exercice 3 de la feuille 3
Feuille 4 : Exercice 2, Exercice 2 bis, Exercice 1 (l’énoncé a un peu changé, la notion de quasi-convexité n’y figure plus), Exercice 4, Exercice 6, Exercice 7, Exercice 9, Exercice 10, Exercice 11.
Avancement du cours
Cours 1 (16/1) : Introduction. Exemples en dimension 1. Vocabulaire. Droite de régression.
Cours 2 (25/1) : Algorithme de Dijkstra. Méthode hongroise pour les problèmes d’affectation.
Cours 3 (30/1) : Détails sur la méthode hongroise. Algorithme de Héron. Début du chapitre sur l’optimisation linéaire. Un exemple. Ecriture matricielle.
Cours 4 (6/2) : Rappels d'algèbre linéaire (matrices, rang, produit scalaire, inégalité de Cauchy-Schwarz, matrice orthogonale). Convexité : définition.
Cours 5 (13/2) : Convexité : enveloppe convexe, faces, points extrémaux, énoncé du théorème de Minkowski, énoncé du théorème de projection sur un convexe fermé. Deuxième heure : DS1.
Cours 6 (20/2) : Projection sur un convexe fermé, hyperplan d’appui. Démonstration du théorème de Minkowski. Algorithme du simplexe : un exemple.
Cours 7 (5/3) : Explications sur l’optimisation linéaire. Si un optimum est atteint, c’est en un point extrémal. Description des points extrémaux d’un polyèdre convexe écrit sous forme standard. Un exemple d’application de l’algorithme avec utilisation de la dualité.
Cours 8 (12/3) : Algorithme du simplexe (fin). Début du chapitre sur l’optimisation différentielle : extrema libres locaux de fonctions d’une et deux variables.
Cours 9 (19/3) : Points critiques d’une fonction de d variables et leur nature (plusieurs méthodes). Fonctions convexes et concaves.
Cours 10 (26/3) : Caractérisation de la convexité en dimension d en utilisant la dimension 1. Une fonction convexe a un minimum global en un point critique. Caractérisation des fonctions convexes au moyen de la matrice hessienne. Ligne de niveau, surface de niveau, hypersurface de niveau : exemples, le gradient est orthogonal à une ligne niveau, application à l’obtention des équations de tangentes ou plans tangents. Enoncé du théorème des extremas liés pour une contrainte.
Cours 11 (2/4) : Extrema liés. Exemples de calculs et de raisonnements pour une contrainte. Enoncé du théorème avec plusieurs contraintes.
Cours 12 (9/4) : Exemple de calcul utilisant le théorème des extrema liés avec plusieurs contraintes. Théorème de Karush-Kuhn-Tucker, un exemple d’application.