Optimisation Numérique, M1 Ingénierie
Mathématique
Calendrier
Cours : 8 séances les vendredis, 13h30-16h30, du 21/1 au 18/3, sauf le 25/2
(vacances d'hiver) ;
TP : 5 séances les jeudis 13h30-15h30, du 27/2 au 3/3, sauf le
24/2 (vacances) ;
Examen écrit : le 24/3 ;
Un devoir maison de TP est prévu également,
à rendre pour le 17/3. Il pourra donner un bonus pour la note
finale.
Un dévoir maison (non noté) sur le cours a
été également distribué.
Programme du cours
Les 5
premières séances du cours seront
suivies d'un TP la semaine suivante et les 3
dernières porteront sur des sujets complémentaires ou plus
théoriques, non traités en TP.
Le programme est plus ou moins le suivant:
1) Introduction à l'optimisation, existence des optima,
conditions d'optimalité, multiplicateurs de Lagrange
2) Exemples de semi-continuité et d'utilisation des
multiplicateurs de Lagrange ; description des
algorithmes de Newton et lien avec le théorème des contractions
3) Rôle de la convexité en minimisation, algorithme
de gradient à pas fixe et pas optimal
4) Liens entre Newton et gradient ; algorithme du
gradient conjugué avec preuve de convergence, algorithme du
gradient projeté, méthode de pénalisation
5) Plus de détails sur les fonctions convexes :
différentiabilité, sous-différentiel, algorithme
de sous-gradient, problèmes de minimum avec un paramètre,
dualité, transformé de Legendre, algorithme d'Uzawa
6)
Calcul des variations : lien entre équations elliptiques et
minimisation, équation d'Euler-Lagrange et bref aperçu de
l'existence (espaces de Sobolev en dim 1)
7)
Programmation dynamique : description des types des problèmes et de leurs résolution "algorithmique" pour un problème en temps discret et horizon fini, exemples
8)
Programmation linéaire, exemple du problème de
Monge-Kantorovitch (transport) discret, algorithme du symplexe,
d'autres algorithmes basés sur la dualité
Sujet du dévoir maison du
cours, avec l'examen de l'an dernier (attention : ne pas trop se fier au style de l'examen de 2010,
c'était un autre prof).
Corrigé du DM.
Examen du 24 mars
Voici sujet et corrigé de
l'examen.
Travaux Pratiques
Les TP ont été assurés par Aude Roudneff-Chupin
Feuille 1 de TP (optimisation en dim 1)
Feuille 2 de TP (optimisation sans contrainte)
Feuille 3 de TP (optimisation sous contrainte)
Devoir maison de TP
Bibliographie
Une bonne partie du cours (les multiplicateurs de Lagrange, tous les algorithmes de gradient, le
symplexe...) se trouve sur le livre de Ph. Ciarlet "Introduction
à l'analyse numérique matricielle et à
l'optimisation".
L'introduction et le chapitre 1 du poly suivant
Poly de
Guillaume Carlier sur l'optimisation dynamique
présentent ce qui sera traité sur la programmation
dynamique.
Pour la partie de calcul des variations, voici une introduction
rapide, qui contient néanmoins des ingrédients d'analyse
fonctionnelle (ignorer la section 2.1, trop détaillée)
:
Un petit poly informel sur les espaces de
Sobolev
Séance par séance
1) beaucoup des choses étaient des rappels (attention à
la semi-cntinuité qui était probablement nouvelle) ; pour les
multiplicateurs de Lagrange voir Ciarlet, Chap. 7.2 ;
2) Ciarlet,
Chap. 7.5 ;
3) Ciarlet, Chap. 8.4 (sauf relaxation) ;
4) Ciarlet page 166 + Chap. 8.5 et 8.6 (sauf relaxation)
5) Ciarlet Chap. 9.2, 9.3 et 9.4 (attention, on a été un
peu rapides, sans faire trop de preuves).
6) Poly de Carlier, Chap. 4, pages 25-29 + Poly Sobolev, sans la
section 2.1 + éventuellement regarder dans le Ciarlet Chap. 3
ce qu'il dit sur l'approximation variationnelle.
7) Poly de Carlier, 1.1, 1.2 et 1.3 + Chap 2 + 3.3 + page 20 + 3.5
8) Ciarlet, Chap. 10.3