Optimisation convexe, M2 MathSV
Ce cours constitue 1/3 d'un
cours qui s'appelle Optimisation et Simulation Numérique du M2
Mathématiques du Vivant (MathSV).
Calendrier, planning et modalités
3 séances, le 29 septembre, le 6 et le 13 octobre. Chaque séance a lieu de
9h30 à 12h30 en salle 117-119, bât 425.
Modalité d'examen : il y aura un examen sur table (2/3
de la note) sur
cette partie et la suivante (E. Kuhn) ; la dernière partie du
cours (S. Faure)
donnera lieu à une évaluation par projet informatique /
compte-rendu de TP (1/3 de la note).
Date de l'examen : lundi 13 décembre 2016, 14h-17h, places 597 à 626 dans la salle 2 du bât 337.
Programme du cours et références
1) (séance du 29/9) Introduction à
l'optimisation et à l'analyse convexe.
Rappels sur l'existence des minima, semicontinuité, conditions
d'optimalité d'ordre 1 et 2, multiplicateurs de Lagrange.
Définitions équivalentes de fonctions convexes,
sous-différentiel, conditions suffisantes d'optimalité, transformée de Legendre-Flenchel.
Références :
pour la première partie du cours vous pouvez voir
ce poly de
calcul différentiel et en particulier les pages 93 et
suivantes ; pour la suite essentiellement le livre de R. T. Rockafellar
Convex Analysis.
2) (séance du 6/10) Dualité ; Algorithmes de gradient.
Dualité en optimisation convexe, points-selle et applications.
Algo de gradient à pas fixe et lien avex le
théorème des contractions (point fixe) ; algo
de sous-gradient (sans preuves).
Condition d'optimalité dans les problèmes convexes avec
contraintes ; projection sur un convexe ;
algos de gradient et sous-gradient projetés ; exemples de
projection.
Références :
essentiellement le livre de Ph. Ciarlet Introduction
à l'analyse numérique matricielle et à
l'optimisation, chapitre 8.
3) (séance du 13/10) Sujets plus avancés
Algorithme d'Uzawa (dualité pour la minimisation convexe sous
contraintes d'inégalités). Variante du Lagrangien Augmenté.
Algorithme FISTA pour la minimisation de f(x)+g(x) avec f lisse et g
non. Description de la méthode ISTA pour
g(x)=║x║1 ; lien avec l'algo de
gradient à pas fixe ; ordre de convergence du gradient à
pas fixe sans ellipticité ; idée et détails de la
méthode FISTA.
Références : Uzawa = Ciarlet, chapitre 9 ; FISTA = voir
l'article original de Beck et Teboulle.
Exercices
Vous pouvez voir le sujet du devoir maison donné en 2014 : sujet (version avec la solution de 3
exos sur 6 : ici).
Regarder également ces exercices supplémentaires
(avec la solution de 2 exos sur 4 : ici).
Sujets d'examen de 2015/16 (attention, le format était
différent, il y avait un écrit de 2h pour cette partie
uniquement) : 1ère session,
2ème
session. Corrigé de certains exercices de première
session : ici (scanné).