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

A continuación presento un resumen técnico detallado del artículo "Finding the Convex Envelope of a Boundary Datum Using Random Geometric Graphs" (Encontrando la envolvente convexa de un dato de frontera utilizando grafos geométricos aleatorios), escrito por Aurelia Deshayes, Nicolás Frevenza, Alfredo Miranda y Julio D. Rossi.

1. Planteamiento del Problema

El objetivo central del trabajo es aproximar la envolvente convexa de una función de frontera $f$ definida en el borde $\partial D$ de un dominio acotado y suave $D \subset \mathbb{R}^d$ (con $d \geq 2$), extendiendo dicha función al interior de $D$ bajo la restricción de convexidad.

Matemáticamente, si $f: \partial D \to \mathbb{R}$ es continua y $D$ es estrictamente convexo, la envolvente convexa $u^*$ se define como:
$$u^*(x) := \sup \{ v(x) : v \text{ es convexa en } D \text{ y } v|_{\partial D} \leq f \}$$
Se sabe que esta función es la única solución (en sentido de viscosidad) del problema de Dirichlet asociado al primer valor propio del Hessiano:
$$\begin{cases} -\lambda_1(D^2 u)(x) = 0 & x \in D \\ u(x) = f(x) & x \in \partial D \end{cases}$$
donde $\lambda_1(D^2 u)(x) = \inf_{z \in S^{d-1}} \langle D^2 u(x)z, z \rangle$.

El desafío abordado en el paper es discretizar este problema utilizando un conjunto de puntos aleatorios distribuidos uniformemente en un dominio que contiene a $D$, conectados mediante un grafo geométrico aleatorio, y demostrar que la solución de una ecuación discreta en este grafo converge a la envolvente convexa continua cuando el número de puntos tiende a infinito.

2. Metodología

La metodología se basa en tres pilares fundamentales: la teoría de grafos geométricos aleatorios, la teoría de juegos estocásticos y la teoría de soluciones de viscosidad para EDPs.

A. Configuración del Grafo Aleatorio

• Se considera una nube de puntos $\chi_n = \{X_1, \dots, X_n\}$ distribuida uniformemente en $[0, 1]^d$.
• Se construye un grafo geométrico aleatorio $G_n = G(\chi_n, r_n)$, donde dos vértices $x, y$ están conectados si su distancia euclidiana $|x - y| < r_n$.
• Se trabaja en el régimen de superconectividad, donde $n r_n^d / \log n \to \infty$ (y bajo condiciones más fuertes para la prueba), lo que garantiza que el grafo sea conexo con probabilidad 1 cuando $n \to \infty$.
• Se define un subconjunto de vecinos $N_x^{\delta_n}$ en una corona anular de radio $(1-\delta_n)r_n$ a $r_n$, asegurando que existan vecinos en "todas las direcciones" para cada vértice.

B. Formulación del Juego

Se define un juego de un solo jugador (controlador) en el grafo:

1. Estado inicial: Una ficha se coloca en un vértice $x_0 \in D_n$ (interior del grafo).
2. Movimiento: El jugador elige un vecino $y$ en la corona anular $N_{x_k}^{\delta_n}$.
3. Transición: La siguiente posición $x_{k+1}$ se elige aleatoriamente con probabilidad $1/2$ entre $y$ y su "vecino reflejado aproximado" $y_x$ (el punto en el grafo más cercano al reflejo geométrico de $y$ respecto a $x$).
4. Fin del juego: El juego termina cuando la ficha alcanza el conjunto de frontera $B_n$ (vértices fuera de $D$).
5. Pago: El jugador paga $f(x_\tau)$, donde $x_\tau$ es la posición final.
6. Objetivo: El jugador busca minimizar el pago esperado.

El valor del juego $u_n(x)$ satisface el Principio de Programación Dinámica (DPP) discreto:
$$\begin{cases} u(x) = \min_{y \in N_x^{\delta_n}} \left( \frac{1}{2}u(y) + \frac{1}{2}u(y_x) \right) & x \in D_n \\ u(x) = f(x) & x \in B_n \end{cases}$$
Esta ecuación es la aproximación discreta de la ecuación $\lambda_1(D^2 u) = 0$, ya que el término $\frac{1}{2}u(y) + \frac{1}{2}u(y_x) - u(x)$ aproxima la segunda derivada direccional.

C. Herramientas Analíticas

• Concentración de medida: Se utilizan desigualdades de concentración (específicamente la desigualdad de Bousquet para procesos empíricos) para demostrar que, bajo ciertas condiciones de decaimiento de $r_n$ y $\delta_n$, el grafo tiene suficientes puntos en todas las direcciones anulares con probabilidad 1.
• Teoría de Visosidad: Se emplean técnicas de soluciones de viscosidad (principio de comparación, método de Perron) para establecer la convergencia del límite de las soluciones discretas a la solución continua.

3. Contribuciones Clave

1. Construcción de un Esquema Discreto Convergente: Se propone un método basado en grafos aleatorios para calcular la envolvente convexa, evitando la necesidad de una malla estructurada (grid), lo cual es ventajoso en dimensiones altas.
2. Control de Parámetros Asintóticos: Se establece una relación precisa y no trivial entre el número de puntos $n$, el radio de conexión $r_n$ y el parámetro de la corona anular $\delta_n$. Específicamente, se requiere que:
   $$\frac{\sqrt{n} r_n^{2d}}{\log n} \to \infty \quad \text{y} \quad \delta_n = \frac{r_n}{\sqrt{\log n}}$$
   Estas condiciones aseguran que el grafo sea suficientemente denso para capturar la geometría local necesaria para aproximar el Hessiano, pero lo suficientemente disperso para mantener la estructura aleatoria.
3. Interpretación de Juego: Se proporciona una interpretación de juego estocástico (tipo "Tug-of-war" pero con un solo jugador y movimiento aleatorio simétrico) para la ecuación del primer valor propio del Hessiano, extendiendo la literatura existente sobre el $p$-Laplaciano.
4. Prueba de Convergencia Uniforme: Se demuestra rigurosamente que el valor del juego, extendido al dominio continuo mediante interpolación por el punto más cercano, converge uniformemente a la envolvente convexa continua.

4. Resultados Principales

El paper presenta dos teoremas fundamentales:

• Teorema 1 (Existencia y Unicidad Discreta): Bajo las condiciones de los parámetros mencionadas, para una realización casi segura del grafo aleatorio y para $n$ suficientemente grande, el valor del juego $u_n$ es la única solución del principio de programación dinámica (DPP) discreto. Esto se prueba mediante un principio de comparación y el método de Perron.

• Teorema 2 (Convergencia al Límite Continuo): Sea $(r_n)$ una secuencia que satisface la condición de superconectividad fuerte y sea $f$ continua. Entonces, casi seguramente, la secuencia de funciones de valor del juego $\tilde{u}_n$ (extendidas al dominio $D$) converge uniformemente a $u$, donde $u$ es la única solución de viscosidad del problema de Dirichlet continuo para la envolvente convexa.

5. Significado e Impacto

• Intersección de Disciplinas: El trabajo une la teoría de grafos aleatorios, la teoría de juegos estocásticos y el análisis de EDPs no lineales. Muestra cómo procedimientos de aprendizaje semi-supervisado basados en grafos pueden converger a soluciones de EDPs específicas.
• Aplicaciones en Optimización y Aprendizaje Automático: La envolvente convexa es crucial en optimización convexa y en problemas de interpolación. Este método ofrece una alternativa escalable a métodos basados en mallas para dominios de alta dimensión.
• Rigurosidad en Grafos Aleatorios: Proporciona un marco teórico sólido para entender cómo las propiedades geométricas locales de grafos aleatorios (como la existencia de vecinos en todas direcciones) se traducen en propiedades analíticas globales (convergencia a soluciones de EDPs).
• Limitaciones y Futuro: Los autores reconocen que las condiciones sobre los parámetros (especialmente la tasa de decaimiento de $r_n$) podrían no ser óptimas y que la regularidad asintótica de las soluciones discretas cerca de la frontera es un tema abierto.

En resumen, el artículo demuestra que es posible recuperar la envolvente convexa continua de un dato de frontera resolviendo un juego estocástico simple en un grafo geométrico aleatorio, siempre que la densidad de puntos y el radio de conexión se escalen adecuadamente.