Convergence en dimension infinie d'un algorithme pour le transport optimal

De Ensiwiki
Aller à : navigation, rechercher


Convergence en dimension infinie d'un algorithme de transport optimal

Labo LJK
Equipe EDP
Encadrants Romain.Hug@imag.fr,Emmanuel.Maitre@imag.fr

Thème général

Dans cet IRL on s'intéresse à la convergence théorique et numérique, en formulation continue (non discrétisée) d'un algorithme permettant la résolution d'un problème de transport optimal.

Sujet

La première partie de l'étude sera essentiellement théorique, sur une question portant sur un algorithme dans sa version continue, dont la forme discrétisée permet de calculer efficacement le transport optimal entre deux densités. Cet algorithme est de la famille des méthodes primales-duales dont un tutoriel est disponible dans ces slides. Dans un premier temps, il s'agit de reformuler cette question sous la forme d'un problème de convergence vers un point fixe d'une suite d'opérateurs hilbertiens. Dans un deuxième temps, une étude des conditions d'existence d'un point fixe sera nécessaire et pourra utiliser les résultats déjà établis concernant cette situation pour un autre algorithme (algorithme de Benamou-Brenier). A cette fin, il sera probablement nécessaire d'effectuer une étude des caractéristiques de l'opérateur en question versus l'opérateur intervenant dans l'algorithme de Benamou-Brenier. Pour ce qui est de l'algorithme de Benamou-Brenier, l'étude de la convergence à l'aide d'opérateurs non-expansif ne permet en général que de démontrer une convergence faible. Cependant une légère modification de l'algortihme à l'aide d'une pondération classique pour les algorithme itérant un opérateur non-expansif permet obtenir une variante à convergence forte. L'étude consistera également à constater si de telles variantes sont également possible pour les algorithmes étudiers et si elles permettent effectivement d'en modifier le type de convergence.

Dans la pratique (du moins pour ce qui concerne l'algorithme de Benamou-Brenier), nous sommes dans l'incapacité d'effectuer de manière théorique une comparaison effective de convergence entre l'algorithme d'origine et ses diverses variantes, principalement à cause du fait que nous ne disposons pas de moyens théoriques d'estimer la distance entre une solution étape (de l'algorithme utilisé) et la solution théorique, et donc que nous ne disposons pas de critère d'arrêt efficace. C'est pourquoi, dans un deuxième temps, il serait également intéressant d'ajouter à ces notions abstraites de convergence faibles ou fortes, une étude comparée plus empirique entre ces deux algos (i.e. une étude numérique). Etant pour l'instant incapable d'estimer la distance à une solution théorique, il sera nécéssaire de l'estimer par rapport à une solution calculée "lointaine", puis tenter d'interpréter les résultats obtenues : quels y seront les phénomènes liés à la distance utilisée (ici la distance L2), à l'implémentation numérique (qui pourrait perturber très significativement le processus), etc... Selon les hypothèses émises, il sera probablement nécéssaire de chercher à valider ou invalider certaines d'entre elles via divers expérimentations numériques.

Compétences attendues

Cet IRL s'adresse aux étudiants de la filière MMIS. Il s'agira dans un premier temps d'adapter à un nouvel algorithme un raisonnement théorique qui a été mené avec succès dans le cadre d'un autre algorithme de la même famille, et dans un deuxième temps de compléter cette première étude théorique par une étude numérique plus empirique sur certains aspects de la convergence que la première étude n'aura pas été en mesure de couvrir.

Contexte du travail

L'IRL se déroulera dans l'équipe Equations aux Dérivées Partielles (EDP) du laboratoire Jean Kuntzmann (LJK). La thématique développée peut s'appliquer à la résolution de problèmes actuellement étudiés au laboratoire (notamment de transport optimal).

Résultats attendus

L'objectif principal est la compréhension de la problématique, et l'analyse mathématique critique des algorithmes comparés.