AnnalesÉcoles d'ingénieurs

X-ENS PSI 2023 — Maths

Transport optimal régularisé par l'entropie et algorithme de Sinkhorn · 6 pages

Le sujet rappelle d'abord des outils d'optimisation convexe : minimisation d'une fonction convexe, extremum sous une contrainte affine $Ax = b$ et points selles d'un lagrangien. Il introduit ensuite l'entropie d'une loi discrète et la divergence de Kullback-Leibler et en déduit, via l'inégalité de Kraft, que la longueur moyenne d'un code préfixe est au moins $H(p)/\ln 2$ . Il étudie enfin le problème de transport entre deux lois discrètes régularisé par l'entropie, montre l'existence, l'unicité et la stricte positivité du couplage optimal, puis, par dualité, introduit les itérations de Sinkhorn, montre que la fonction duale croît le long de ces itérations et que, si les potentiels convergent, les couplages associés convergent vers le couplage optimal.

Le sujet, partie par partie

Notations et Partie I — Convexité et points selles p. 2–3

Fonctions convexes · Extrema liés et multiplicateurs de Lagrange · Ensembles convexes · Espaces préhilbertiens et euclidiens · Calcul différentiel · Dualité · Applications linéaires et rang — fonction strictement convexe, minimum unique, multiplicateurs de Lagrange, lagrangien, point selle, noyau et image de la transposée

Partie II — Entropie et codage p. 3

Espérance, variance, moments · Fonctions convexes · Informatique et algorithmique · Espaces probabilisés · Inégalités classiques — entropie, divergence de Kullback-Leibler, code préfixe, inégalité de Kraft, longueur moyenne d'un code, fonction $x \ln x - x + 1$

Partie III — Transport régularisé p. 4

Fonctions convexes · Couples et sommes de variables aléatoires · Extrema et optimisation · Compacité · Conditionnement et indépendance — transport optimal, couplage de deux lois, lois marginales, régularisation entropique, minimum sur un fermé borné, stricte convexité

Partie IV — Dualité et algorithme de Sinkhorn p. 4–5

Extrema et optimisation · Fonctions convexes · Suites numériques · Extrema liés et multiplicateurs de Lagrange · Points fixes et suites itératives · Calcul différentiel — dualité, point selle, fonction concave, algorithme de Sinkhorn, suite monotone bornée, convergence d'un algorithme itératif