Une première série de travaux se situe essentiellement dans le domaine de l’optimisation combinatoire et concerne des problèmes de transport optimal en dimension 1. Dans ce cas et lorsque le coût de déplacement est convexe en la distance, le plan de transport optimal entre deux mesures est donné explicitement par le réarrangement monotone. Nous avons considéré deux variantes de ce problème pour lesquelles il n’existait pas de tel résultat : le transport optimal sur le cercle en coût convexe [12] et le transport optimal en coût concave [16]. Une méthode classique pour modifier les couleurs d’une image consiste à transporter de manière optimale son histogramme de couleurs sur un histogramme souhaité. Or certains codages de couleurs, tels le HSV ou le HSL, ont une composante périodique qui ne peut être traitée par réarrangement monotone. Face à ce problème et dans le cas convexe, une technique généralement employée consiste à se ramener au cas de la droite en « coupant » le cercle successivement en différents points et on calcule le coût de chacun des réarrangements monotones associés. On choisit alors le plan le moins coûteux. Dans ce cadre, nos contributions ont été de justifier mathématiquement la validité de cette méthode et de construire un algorithme de calcul rapide du point de coupure associé à la solution optimale.
L’étape essentielle fut de remarquer que ce point était solution d’un problème de minimisation convexe. Le travail sur le coût concave se situe dans un cadre entièrement discret : après avoir partitionné l’ensemble des points en chaînes, sous-ensembles correspondant à des appariements admissibles, nous avons remarqué que celles-ci contiennent au moins deux points consécutifs appariés dans le plan de transport optimal global. L’idée fut alors de détecter ces deux points, pour les apparier et retirer ainsi successivement tous les points du problème considéré. Nous avons ainsi défini une classe hiérarchique d’indicateurs, les indicateurs d’appariements locaux basés sur des tests locaux et peu coûteux, qui permettent de garantir l’optimalité d’appariements de points voisins. Parallèlement, nous avons travaillé sur des modèles de transport continus où l’optimalité d’un déplacement se traduit par un système d’EDP couplées [Proc. 4], ce qui revient à aborder le problème dans un cadre de contrôle optimal. Le transport avec diffusion correspondait à une dynamique de Fokker-Planck. Les principales innovations de ce travail concernent le couplage du schéma d’optimisation avec une méthode de simulation de Fokker-Planck et la stratégie d’optimisation qui reprend certaines idées des algorithmes monotones.
Les algorithmes pour le cercle et pour le coût concave sont originaux. Dans les deux cas, la difficulté principale fut d’identifier ce que l’on souhaitait obtenir comme résultat et donc avant tout de poser les bonnes conjectures.Pour ce qui concerne l’approche par EDP, il fallu exporter l’approche proposée par les chimistes à une équation de transport. Outre les complications liées à l’implémentation, cela impliqua d’astreindre l’algorithme d’optimisation aux conditions de stabilité du schéma de simulation, tout en préservant la monotonie des itérations.
L'algorithme sur le cercle est utilisé régulièrement pour des modifications de couleurs d’images (l’absence d’algorithme pour des histogrammes périodiques est à l’origine de notre travail). De manière inattendue, le travail sur le coût concave a été utilisé par des physiciens pour modéliser les repliements de brins d’ARN. Avec A. Lachapelle nous avons repris l’approche EDP pour la simulation de modèles économiques.
Les publications liées à cette contribution sont [12], [16], [Proc. 4], [C.R.A.S. 2] et [11].
