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 un DS cours noté sur 10 (le 13 février), un DS long (le 17 avril) noté sur 20. Votre note finale en optimisation sera le maximum entre la somme des deux notes multipliée par 2/3 et la note du DS du 17 avril.

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).

DS1-2019, DS2-2019, DS3-2019

Un corrigé du DS1 de 2019

Un corrigé du DS2 de 2019 Erratum

DS1-2022, DS2-2022, DS3-2022

DS1 2023 (à moitié corrigé)

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

Correction de l’exercice 10 de la feuille 3 (le numéro a changé), de l’exercice 1 de la feuille 4 (l’énoncé a un peu changé, la notion de quasi-convexité n’y figure plus).

Quelques corrigés d’exercices de la feuille 4 : exercice 4, exercice 7, exercice 9, exercice 10.

Avancement du cours

Cours 1 (16/1) : Introduction. Exemples en dimension 1 (vocabulaire, inf, min, sup, max). Dessin en dimension 2. Algorithme de Dijkstra.

Cours 2 (23/1) : Méthode hongroise. Droite de régression. Algorithme de Héron.

Cours 3 (30/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).

Cours 4 (7/2) : Le cours s’est déroulé à distance car, le 6 février et les jours suivants, il n’était plus possible d’enseigner à l’université. Enveloppe affine d’une partie. Convexité, enveloppe convexe. Théorème de projection sur un convexe fermé.

Cours 5 (13/2) : Retour sur le théorème de projection. Point extrémal d’un convexe fermé. Théorème de Minkowski.

Cours 6 (27/2) : Description des polyèdres sous forme standard (Ax=b, x>=0), description des 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. Deuxième heure : DS1.

Cours 7 (6/3) : La méthode du simplexe. Description sur trois exemples sous forme de tableaux. Début du chapitre sur l’optimisation différentielle.

Cours 8 (13/3) : Optimisation libre : développement limité à l’ordre 2 d’une fonction de plusieurs variables à valeurs réelles, points critiques, gradient, hessienne, signe de la forme quadratique associée à une matrice symétrique réelle. Sur le bord du domaine d’étude (s’il y a un bord) il faut d’autres outils.

Cours 9 (20/3) : Méthode de Newton en dimension 1, en dimension d. Fonctions convexes : définition, rappels en dimension 1 (liens avec les dérivées), caractérisation en dimension d en utilisant la dimension 1.

Cours 10 (27/3) : 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. Direction de plus forte pente. Méthode de descente.