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 décrit ci-dessous. En deuxième session ce sera un examen.

Vous aurez cinq notes pour deux interrogations et trois petits devoirs à la maison.

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 DS2 de 2019

Références

Notes de cours provisoires

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

Des corrigés d’exercices de la feuille 4 : Exercice 1, Exercice 4, Exercice 4 bis, Exercice 2, Exercice 6, Exercice 8, Exercice 9, Exercice 12, Exercice 13, Exercice 14.

Le dernier contrôle est un devoir à la maison à

Avancement du cours

Cours 1 (18/1) : Introduction. Quelques exemples. L’algorithme de Dijkstra.

Cours 2 (25/1) : La méthode hongroise pour les problèmes d’affectation. La droite de régression.

Cours 3 (1/2) : Méthode de Héron pour approcher racine de 2. Programmation linéaire : un exemple en dimension 2, résolution graphique, notations, formulation matricielle des problèmes de programmation linéaire. Sous-espace affine (direction, enveloppe affine).

Cours 4 (8/2) : Enveloppe affine : exemples. Convexes : faces, points extrémaux, théorème de projection sur un convexe fermé, hyperplan d’appui.

Cours 5 (15/2) : Ensembles convexes. Points extrémaux, demi-droites extrémales. Théorèmes de Minkowski. Exemples de polyèdres.

Cours 6 (22/2) :  Polyèdres, formes standard et canonique, dualité, forme des points extrémaux dans le cas standard, algorithme du simplexe sur l'exemple donné dans les notes de cours.

Cours 7 (8/3) : Algorithme du simplexe.

Cours 8 (15/3) : Les points critiques de fonctions définies sur R^d et de leurs natures en fonction des signes des valeurs propres de la matrice hessienne. Comment trouver les signes des valeurs propres d'une matrice symétrique réelle ? Trois méthodes : calculer le polynôme caractéristique et étudier le signe de ses racines (pas forcément en trouvant les racines), décomposition de Gauss de la forme quadratique associée, calculer les mineurs principaux et utiliser la suite de leurs signes. 

Cours 9 (22/3) : Fonctions convexes. DS1.

Cours 10 (29/3) : Méthode de Newton (en dimension 1 et d), méthode de descente. Tangentes à des lignes ou surfaces de niveau de fonctions régulières, théorème d’inversion locale, théorème des fonctions implicites.

Cours 11 (12/4) : Les théorèmes des extrema liés et de Karush, Kuhn, Tucker.