Optimisation convexe, M2 MathSV et MathAléa
Ce cours constitue 1/3 d'un
cours qui s'appelle Bayesien, MCMC, Optimisation du M2
Mathématiques de l'Aléatoire (MathAléa) ainsi qu'1/3 d'un cours
qui s"appelle Optimisation et Simulation Numérique du M2
Mathématiques du Vivant (MathSV). La valeur en ECTS et les
modalités d'examen changent entre les deux masters.
Calendrier, planning et modalités
3 séances, le 1, 8 et 15 obtobre. 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 ; de plus, pour les étudiants de MathSV il y aura aussi un projet informatique à
faire par binômes (un seul projet pour les parties optimisation
déterministe + optimisation stochastique, à
confirmer).
Date de l'examen : jeudi 5 novembre 2015, 10h-12h, salle 117-119.
Programme du cours et références
1) (séance du 1/10) 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,
théorème de dualité.
Références :
essentiellement le livre de R. T. Rockafellar
Convex Analysis.
2) (séance du 8/10) Algorithmes de gradient.
(tout d'abord on terminera la preuve de la dualité
laissée en suspens la première fois).
Algo de gradient à pas fixe et lien avex le
théorème des contractions (point fixe), variantes: pas
ariable, pas optimal ; l'exemple de la minimisation quadratique ; 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 15/10) Sujets plus avancés
Algorithme d'Uzawa (dualité pour la minimisation convexe sous
contraintes d'inégalités ; conditions d'optimalité de
Kuhn-Tucker).
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 les algos proximaux et le
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.
Regarder également ces exercices supplémentaires
Avec solutions (3 exos
corrigés sur 6) et (2 corrigés sur 4).