Convex Relaxations for the Optimization of Markov Processes

Resumen Técnico: Relajaciones Convexas para la Optimización de Procesos de Markov

Planteamiento del Problema
El artículo aborda el problema de optimizar un proceso de Markov que interpola entre dos distribuciones de probabilidad prescritas, $\mu$ y $\nu$, sobre un espacio de estados $\Omega$ mientras se minimiza un costo acumulado. El proceso se define mediante una secuencia de leyes intermedias $\{\rho_s\}_{s=0}^T$ y núcleos de transición de Markov $\{K_s\}_{s=0}^{T-1}$. El objetivo es minimizar la suma de los costos de un solo paso:
$$\inf \sum_{s=0}^{T-1} \int_{\Omega} \int_{\Omega} c_s(x, y) K_s(x, dy) d\rho_s(x)$$
sujeto a las restricciones iniciales y terminales ($\rho_0 = \mu, \rho_T = \nu$) y a la restricción de evolución de Markov ($\rho_{s+1} = (K_s)_* \rho_s$).

El principal desafío computacional es la maldición de la dimensionalidad. En espacios de estados de alta dimensión, representar la distribución conjunta completa de los estados consecutivos (el acoplamiento $\pi_s$) es inabordable. El artículo se centra en configuraciones donde los núcleos de transición admisibles satisfacen restricciones específicas (por ejemplo, restricciones de soporte, reglas de actualización local) y donde la función de costo admite una descomposición local.

Metodología
Los autores proponen un marco basado en formulaciones de acoplamiento secuencial y relajaciones convexas que aprovechan la localidad y las estructuras de interacción dispersas.

1. Reformulación de Acoplamiento Secuencial:
   El problema se reformula de la optimización de núcleos de transición a la optimización de una secuencia de acoplamientos conjuntos $\pi_s(dx, dy) = \rho_s(dx)K_s(x, dy)$. Las restricciones se reescriben en términos de los marginales de estos acoplamientos. Las distribuciones intermedias se absorben en los acoplamientos, donde $\rho_{s+1}$ es el marginal derecho de $\pi_s$ y el marginal izquierdo de $\pi_{s+1}$.

2. Relajaciones Convexas:
   Para evitar la representación del acoplamiento completo $\pi_s$, los autores desarrollan dos tipos de relajaciones convexas que retienen únicamente información local de bajo orden:

   • Relajación de Marginales: El acoplamiento completo se reemplaza por sus marginales locales en un conjunto de clústeres de coordenadas $\mathcal{C}$ y pares de clústeres definidos por un grafo de clústeres $\mathcal{G} = (\mathcal{C}, \mathcal{E})$. La relajación impone:
     • Consistencia entre los marginales de clústeres y pares de clústeres.
     • Conservación de masa a través de los pasos temporales (proyectada sobre los pares de clústeres retenidos).
     • Restricciones de positividad local y positividad global (esta última asegurando que los marginales locales puedan extenderse a una medida no negativa global, a menudo mediante una restricción de Semidefinida Positiva (PSD) sobre una matriz de tipo momento).
     • Restricciones de admisibilidad proyectadas sobre los marginales locales.
   • Relajación de Momentos de Clúster: En lugar de los marginales completos, el método utiliza un conjunto finito de momentos contra funciones base prescritas (por ejemplo, monomios) en los clústeres. Esto es adecuado para espacios de estados continuos. Las variables de decisión son matrices de momentos. Las restricciones incluyen consistencia de momentos, conservación de masa y positividad global (restricciones PSD sobre las matrices de momentos ensambladas).

   Ambos marcos dan como resultado problemas de optimización convexos (Programas Lineales para estados finitos con restricciones afines, o Programas Semidefinidos (SDP) para estados continuos o restricciones generales). Estos proporcionan cotas inferiores computables para el problema original y recuperan estadísticas de bajo orden de las distribuciones intermedias.

3. Recuperación de la Dinámica:

   • Transporte Óptimo Dinámico (Benamou–Brenier): Cuando el espacio de estados es convexo, el costo es cinético ($\|x-y\|^2$) y no existen restricciones de núcleo, el problema recupera la geodésica de Benamou–Brenier. Los autores muestran que las variables duales del problema relajado aproximan los potenciales duales del problema de Benamou–Brenier. Al derivar estos potenciales, uno puede recuperar un campo de velocidad aproximado, el cual induce un flujo y un núcleo de Markov correspondiente.
   • Procesos Restringidos Generales: Para restricciones generales (por ejemplo, actualizaciones de espín único en modelos de Ising), el método ajusta una familia paramétrica de núcleos (por ejemplo, dinámica de Glauber) a las estadísticas locales recuperadas. Esto se realiza minimizando el error cuadrático entre los marginales del siguiente paso predichos (mediante el núcleo paramétrico) y los marginales recuperados de la relajación.

Contribuciones Clave

• Formulación: El artículo redefine la optimización de procesos de Markov en una formulación de acoplamiento secuencial y propone un marco de relajación convexa que escala a altas dimensiones utilizando información local dispersa (marginales o momentos) en lugar de distribuciones conjuntas completas.
• Conexión con el Transporte Óptimo Dinámico: Demuestra que el transporte óptimo dinámico es un caso especial de este marco. Crucialmente, proporciona un procedimiento para recuperar el campo de velocidad de Benamou–Brenier subyacente a partir de las variables duales del problema relajado, cerrando la brecha entre las relajaciones estáticas y los flujos dinámicos.
• Generalización a la Dinámica Restringida: El marco se extiende más allá del transporte sin restricciones para manejar procesos de Markov generales con restricciones estrictas. Los autores ilustran esto ajustando la dinámica de Glauber al transporte entre modelos de Ising, convirtiendo las estadísticas locales recuperadas en un núcleo de Markov implementable.

Resultados
El artículo presenta experimentos numéricos que validan el enfoque:

• Transporte Gaussiano: En un entorno Gaussiano de 50 dimensiones, la relajación de momentos recupera con precisión las medias intermedias, covarianzas y campos de velocidad afines. Se demuestra que el método es computacionalmente eficiente (resuelto en segundos vía SDP) y más preciso que los métodos de retropropagación basados en partículas en términos del error de covarianza a lo largo de la trayectoria.
• Transporte de Ginzburg–Landau: El método transporta con éxito una distribución Gaussiana a una distribución de Ginzburg–Landau no gaussiana en 10 dimensiones. La reconstrucción de máxima entropía a partir de los momentos recuperados captura la deformación gradual de la distribución, incluyendo correlaciones locales y de largo alcance.
• Modelos de Ising: El enfoque maneja el transporte restringido entre modelos de Ising ferromagnéticos y antiferromagnéticos (1D y 2D). La relajación de marginales (resuelta como un LP) recupera los marginales de espín locales, que luego se utilizan para ajustar la dinámica de Glauber no homogénea en el tiempo. La dinámica ajustada reproduce con éxito los marginales recuperados y genera trayectorias de muestra válidas.

Significancia y Reivindicaciones
El artículo afirma que su marco ofrece una alternativa tratable a la optimización de procesos de Markov en alta dimensión al evitar el costo exponencial de la representación completa del estado. Proporciona:

1. Cotas Inferiores Computables: Las relajaciones producen cotas inferiores rigurosas para el costo óptimo.
2. Estadísticas Recuperables: El método recupera estadísticas de bajo orden (medias, covarianzas, momentos) de las leyes intermedias.
3. Reconstrucción Dinámica: A diferencia de los métodos de transporte estático, este marco permite la reconstrucción de la dinámica subyacente (campos de velocidad o núcleos de transición) a partir de la solución relajada.
4. Versatilidad: Unifica el transporte óptimo dinámico y el control estocástico restringido (como la dinámica de Glauber) bajo un único paraguas de optimización convexa, aplicable tanto a espacios de estados discretos como continuos.

Los autores señalan modestamente que, si bien el método recupera estadísticas locales y dinámicas aproximadas, la preservación exacta de la localidad en las distribuciones intermedias sigue siendo una cuestión teórica abierta, y el marco está actualmente limitado a tipos específicos de restricciones y estructuras de costo.