Finding the convex envelope of a boundary datum using random geometric graphs

1. Problématique et Contexte

L'objectif principal de cet article est d'approximer l'enveloppe convexe d'une donnée frontière définie sur le bord d'un domaine borné $D \subset \mathbb{R}^d$ (avec $d \ge 2$), en utilisant des graphes géométriques aléatoires.

• Contexte mathématique : L'enveloppe convexe d'une fonction continue $f$ définie sur $\partial D$ est la plus petite fonction convexe $u$ dans $D$ telle que $u \le f$ sur le bord. En termes d'équations aux dérivées partielles (EDP), cette fonction est l'unique solution (au sens des solutions de viscosité) du problème de Dirichlet :
  $$\begin{cases} -\lambda_1(D^2 u)(x) = 0 & x \in D \\ u(x) = f(x) & x \in \partial D \end{cases}$$
  où $\lambda_1(D^2 u)$ désigne la plus petite valeur propre de la matrice hessienne de $u$.
• Approche proposée : Au lieu de discrétiser directement l'EDP sur une grille régulière, les auteurs utilisent un nuage de points aléatoires (distribution uniforme) connectés par proximité pour former un graphe géométrique aléatoire. Ils formulent le problème comme un jeu à un joueur (un contrôleur) sur ce graphe discret et montrent que la valeur de ce jeu converge vers l'enveloppe convexe continue lorsque le nombre de points tend vers l'infini.

2. Méthodologie

La méthodologie repose sur trois piliers principaux : la construction du graphe, la formulation du jeu, et l'analyse asymptotique via la théorie des solutions de viscosité.

A. Construction du Graphe Géométrique Aléatoire

• Points : Soit $(X_n)_{n \in \mathbb{N}}$ une suite de variables aléatoires indépendantes et uniformes sur $[0, 1]^d$.
• Connexité : Pour un rayon $r_n > 0$ décroissant, on définit le graphe $G_n$ où deux sommets $x, y$ sont connectés si $|x - y| < r_n$.
• Régime de super-connectivité : Les auteurs travaillent dans un régime où $n r_n^d / \log n \to +\infty$. Cela garantit que, presque sûrement, le graphe possède une composante connexe majeure $C_n$ qui est dense dans le domaine et que chaque sommet a des voisins dans toutes les directions nécessaires.
• Voisins annulaires : Pour chaque sommet $x$, on considère un ensemble de voisins $N_x^{\delta_n}$ situés dans une couronne d'épaisseur $\delta_n$ (rayons $(1-\delta_n)r_n$ et $r_n$). Cela assure une bonne couverture directionnelle.

B. Le Jeu et le Principe de Programmation Dynamique (DPP)

• Le Jeu : Un pion est placé sur un sommet $x_0 \in D_n = C_n \cap D$. À chaque étape, le joueur $J$ choisit un voisin $y$ dans la couronne. La nouvelle position $x_{k+1}$ est choisie aléatoirement avec probabilité $1/2$ entre $y$ et son « reflet approximatif » $y_x$ (le point le plus proche du reflet géométrique $2x-y$ parmi les voisins).
• Arrêt : Le jeu s'arrête lorsque le pion atteint la frontière discrète $B_n = C_n \cap D^c$. Le joueur paie le coût $f(x_\tau)$.
• Objectif : Le joueur cherche à minimiser l'espérance du paiement.
• Équation discrète : La valeur du jeu $u_n$ satisfait le Principe de Programmation Dynamique (DPP) :
  $$u_n(x) = \min_{y \in N_x^{\delta_n}} \left( \frac{1}{2} u_n(y) + \frac{1}{2} u_n(y_x) \right), \quad x \in D_n$$
  avec la condition aux limites $u_n(x) = f(x)$ pour $x \in B_n$.

C. Outils d'Analyse

• Inégalités de concentration : Utilisation de l'inégalité de concentration de Talagrand-Bousquet pour les processus empiriques afin de prouver que, pour des paramètres bien choisis ($r_n, \delta_n$), le graphe possède des voisins dans toutes les directions presque sûrement.
• Théorie des solutions de viscosité : Pour passer à la limite ($n \to \infty$), les auteurs utilisent la théorie des solutions de viscosité (théorème de comparaison, principe de Perron) pour montrer que la limite de la valeur du jeu satisfait l'EDP continue.
• Estimations de Taylor : Des développements de Taylor d'ordre 2 sont utilisés pour relier la différence finie discrète du jeu à l'opérateur $\lambda_1(D^2 u)$.

3. Résultats Principaux

Les résultats sont établis sous des hypothèses précises sur la décroissance des paramètres $r_n$ et $\delta_n$ (notamment $r_n \to 0$ et $\delta_n = o(r_n)$, avec une condition plus forte sur $n r_n^d$).

1. Existence et Unicité Discrete (Théorème 1) :
   Pour $n$ suffisamment grand, la valeur du jeu $u_n$ est l'unique solution du DPP discret. Cela repose sur un principe de comparaison pour les solutions sub/sur-optimales du système discret.

2. Convergence vers l'Enveloppe Convexe (Théorème 2) :
   Soit $u$ l'unique solution de viscosité du problème continu (1.8). En étendant la fonction discrète $u_n$ au domaine continu $D$ via l'interpolation par le point le plus proche ($\tilde{u}_n(x) = u_n(T_n(x))$), on démontre que :
   $$\tilde{u}_n \xrightarrow[n \to \infty]{\text{uniformément}} u \quad \text{presque sûrement.}$$
   La limite est indépendante des paramètres du jeu, ne dépendant que de la donnée frontière $f$.

3. Régularité et Conditions aux Limites :
   Le papier démontre que la condition aux limites est atteinte continûment, ce qui est techniquement délicat dans le contexte des graphes aléatoires où la frontière est approximée par des points discrets.

4. Contributions Clés

• Lien entre Jeux Stochastiques et Enveloppe Convexe : L'article établit une connexion rigoureuse entre un jeu à un joueur sur un graphe aléatoire et l'EDP non-linéaire associée à l'enveloppe convexe ($\lambda_1(D^2 u) = 0$).
• Contrôle des Paramètres du Graphe : Une contribution majeure est la détermination précise des conditions sur le rayon de connexion $r_n$ et l'épaisseur de la couronne $\delta_n$ nécessaires pour garantir que le graphe aléatoire possède suffisamment de voisins dans toutes les directions pour approximer correctement les dérivées secondes.
• Approche par Graphes Aléatoires : Contrairement aux méthodes classiques sur grilles, cette approche fonctionne sur des nuages de points non structurés, ce qui est pertinent pour l'apprentissage semi-supervisé et les données réelles irrégulières.
• Preuve de Convergence Presque Sûre : Les résultats sont prouvés presque sûrement par rapport à la mesure de probabilité du nuage de points, renforçant la robustesse de la méthode.

5. Signification et Impact

Ce travail est significatif pour plusieurs domaines :

• Analyse Numérique et EDP : Il fournit une nouvelle méthode de discrétisation pour les équations de Monge-Ampère et les équations d'enveloppe convexe, particulièrement utile dans des géométries complexes ou avec des données dispersées.
• Apprentissage Automatique (Machine Learning) : Il renforce le lien théorique entre les méthodes d'apprentissage semi-supervisé basées sur les graphes (graph-based learning) et les EDP. Il montre que certaines procédures d'apprentissage sur graphes convergent vers des solutions d'EDP spécifiques, offrant une justification théorique pour l'utilisation de ces algorithmes.
• Théorie des Jeux Stochastiques : Il élargit la classe de jeux (type "Tug-of-War") dont la limite continue est connue, en passant des équations de Laplace/p-Laplacien à des équations de type enveloppe convexe.

En résumé, l'article démontre qu'il est possible de reconstruire numériquement l'enveloppe convexe d'une fonction à partir de données frontières dispersées en résolvant un jeu simple sur un graphe aléatoire, avec une garantie de convergence rigoureuse vers la solution continue.