Convex Relaxations for the Optimization of Markov Processes

Résumé Technique : Relaxations Convexes pour l'Optimisation de Processus de Markov

Énoncé du Problème
L'article traite du problème de l'optimisation d'un processus de Markov qui interpole entre deux distributions de probabilité prescrites, $\mu$ et $\nu$, sur un espace d'états $\Omega$, tout en minimisant un coût cumulé. Le processus est défini par une séquence de lois intermédiaires $\{\rho_s\}_{s=0}^T$ et de noyaux de transition de Markov $\{K_s\}_{s=0}^{T-1}$. L'objectif est de minimiser la somme des coûts à une étape :
$$\inf \sum_{s=0}^{T-1} \int_{\Omega} \int_{\Omega} c_s(x, y) K_s(x, dy) d\rho_s(x)$$
sous réserve des contraintes initiale et terminale ($\rho_0 = \mu, \rho_T = \nu$) et de la contrainte d'évolution de Markov ($\rho_{s+1} = (K_s)_* \rho_s$).

Le principal défi computationnel est la malédiction de la dimensionnalité. Dans des espaces d'états de haute dimension, représenter la distribution jointe complète des états consécutifs (le couplage $\pi_s$) est intraitable. L'article se concentre sur les cas où les noyaux de transition admissibles satisfont des contraintes spécifiques (par exemple, des contraintes de support, des règles de mise à jour locales) et où la fonction de coût admet une décomposition locale.

Méthodologie
Les auteurs proposent un cadre basé sur des formulations de couplage séquentiel et des relaxations convexes qui exploitent la localité et les structures d'interaction creuses.

1. Reformulation par Couplage Séquentiel :
   Le problème est reformulé, passant de l'optimisation des noyaux de transition à l'optimisation d'une séquence de couplages joints $\pi_s(dx, dy) = \rho_s(dx)K_s(x, dy)$. Les contraintes sont réécrites en termes de marges de ces couplages. Les distributions intermédiaires sont absorbées dans les couplages, où $\rho_{s+1}$ est la marge droite de $\pi_s$ et la marge gauche de $\pi_{s+1}$.

2. Relaxations Convexes :
   Pour éviter de représenter le couplage complet $\pi_s$, les auteurs développent deux types de relaxations convexes qui ne conservent que des informations locales d'ordre faible :

   • Relaxation de Marges : Le couplage complet est remplacé par ses marges locales sur un ensemble de clusters de coordonnées $\mathcal{C}$ et de paires de clusters définis par un graphe de clusters $\mathcal{G} = (\mathcal{C}, \mathcal{E})$. La relaxation impose :
     • La cohérence entre les marges des clusters et des paires de clusters.
     • La conservation de la masse à travers les étapes temporelles (projetée sur les paires de clusters conservées).
     • Des contraintes de positivité locale et globale (cette dernière assurant que les marges locales peuvent être étendues en une mesure non négative globale, souvent via une contrainte de Sémi-Définie Positive (SDP) sur une matrice de type moment).
     • Des contraintes d'admissibilité projetées sur les marges locales.
   • Relaxation de Moments de Cluster : Au lieu des marges complètes, la méthode utilise un ensemble fini de moments par rapport à des fonctions de base prescrites (par exemple, des monômes) sur les clusters. Cette approche est adaptée aux espaces d'états continus. Les variables de décision sont des matrices de moments. Les contraintes incluent la cohérence des moments, la conservation de la masse et la positivité globale (contraintes SDP sur les matrices de moments assemblées).

   Les deux cadres aboutissent à des problèmes d'optimisation convexe (Programmes Linéaires pour les états finis avec contraintes affines, ou Programmes de Programmation Semi-Définie (SDP) pour les états continus ou les contraintes générales). Ceux-ci fournissent des bornes inférieures calculables pour le problème original et permettent de récupérer les statistiques d'ordre faible des distributions intermédiaires.

3. Récupération de la Dynamique :

   • Transport Optimal Dynamique (Benamou–Brenier) : Lorsque l'espace d'états est convexe, le coût est cinétique ($\|x-y\|^2$) et qu'aucune contrainte de noyau n'existe, le problème retrouve la géodésique de Benamou–Brenier. Les auteurs montrent que les variables duales du problème relaxé approchent les potentiels duaux du problème de Benamou–Brenier. En dérivant ces potentiels, on peut récupérer un champ de vitesse approximatif, qui induit un flux et un noyau de Markov correspondant.
   • Processus Contraints Généraux : Pour des processus avec des contraintes générales (par exemple, mises à jour de spins uniques dans les modèles d'Ising), la méthode ajuste une famille paramétrique de noyaux (par exemple, la dynamique de Glauber) aux statistiques locales récupérées. Cela est fait en minimisant l'erreur quadratique entre les marges de l'étape suivante prédites (via le noyau paramétrique) et les marges récupérées de la relaxation.

Contributions Clés

• Formulation : L'article reformule l'optimisation de processus de Markov en une formulation de couplage séquentiel et propose un cadre de relaxation convexe qui passe à l'échelle dans les hautes dimensions en utilisant des informations locales creuses (marges ou moments) plutôt que des distributions jointes complètes.
• Connexion avec le Transport Optimal Dynamique : Il démontre que le transport optimal dynamique est un cas particulier de ce cadre. Crucialement, il fournit une procédure pour récupérer le champ de vitesse de Benamou–Brenier sous-jacent à partir des variables duales du problème relaxé, comblant ainsi le fossé entre les relaxations statiques et les flux dynamiques.
• Généralisation aux Dynamiques Contraintes : Le cadre s'étend au-delà du transport non contraint pour gérer des processus de Markov avec des contraintes strictes. Les auteurs illustrent cela en ajustant la dynamique de Glauber pour le transport entre des modèles d'Ising, convertissant les statistiques locales récupérées en un noyau de Markov implémentable.

Résultats
L'article présente des expériences numériques validant l'approche :

• Transport Gaussien : Dans un cadre gaussien à 50 dimensions, la relaxation de moments récupère avec précision les moyennes, les covariances et les champs de vitesse affines intermédiaires. La méthode s'avère efficace sur le plan computationnel (résolue en quelques secondes via SDP) et plus précise que les méthodes de rétropropagation basées sur les particules en termes d'erreur de covariance le long de la trajectoire.
• Transport de Ginzburg–Landau : La méthode transporte avec succès une distribution gaussienne vers une distribution de Ginzburg–Landau non gaussienne en 10 dimensions. La reconstruction par entropie maximale des moments récupérés capture la déformation graduelle de la distribution, incluant les corrélations locales et à plus longue portée.
• Modèles d'Ising : L'approche gère le transport contraint entre des modèles d'Ising ferromagnétiques et antiferromagnétiques (1D et 2D). La relaxation de marge (résolue comme un LP) récupère les marges de spins locales, qui sont ensuite utilisées pour ajuster des dynamiques de Glauber non homogènes dans le temps. La dynamique ajustée reproduit avec succès les marges récupérées et génère des trajectoires d'échantillons valides.

Signification et Revendications
L'article affirme que son cadre offre une alternative traitable à l'optimisation de processus de Markov de haute dimension en évitant le coût exponentiel d'une représentation complète de l'état. Il fournit :

1. Des Bornes Inférieures Calculables : Les relaxations produisent des bornes inférieures rigoureuses pour le coût optimal.
2. Des Statistiques Récupérables : La méthode récupère les statistiques d'ordre faible (moyennes, covariances, moments) des lois intermédiaires.
3. Une Reconstruction Dynamique : Contrairement aux méthodes de transport statique, ce cadre permet la reconstruction des dynamiques sous-jacentes (champs de vitesse ou noyaux de transition) à partir de la solution relaxée.
4. Polyvalence : Il unifie le transport optimal dynamique et le contrôle stochastique contraint (comme la dynamique de Glauber) sous une seule bannière d'optimisation convexe, applicable tant aux espaces d'états discrets que continus.

Les auteurs notent avec modestie que, bien que la méthode récupère les statistiques locales et les dynamiques approximatives, la préservation exacte de la localité dans les distributions intermédiaires reste une question théorique ouverte, et que le cadre est actuellement limité à certains types de contraintes et de structures de coût.