🔢 mathematics

Convex Relaxations for the Optimization of Markov Processes

This paper addresses the curse of dimensionality in optimizing Markov processes between prescribed distributions by reformulating the problem via sequential couplings and developing convex relaxations based on local marginals and cluster moments to provide computable bounds and recover low-order statistics, including applications to dynamic optimal transport and Ising models.

Original authors: Hongyi Zhang, Yuehaw Khoo, Tianyun Tang

Published 2026-07-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Hongyi Zhang, Yuehaw Khoo, Tianyun Tang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to guide a massive, invisible cloud of gas from one shape to another. Maybe it starts as a perfect sphere and needs to become a twisted pretzel. But here's the catch: you can't just snap your fingers and change the shape instantly. You have to move the gas particle by particle, step by step, over a specific period of time, and you want to do it in the most energy-efficient way possible.

This is the problem the authors are tackling. They call it "optimizing Markov processes," but let's call it "The Great Cloud Shaping Challenge."

The Big Problem: Too Many Particles, Not Enough Brainpower

The main hurdle is what mathematicians call the "curse of dimensionality." Imagine your cloud isn't just in 3D space, but in 50 dimensions (or even more). To track every single particle and know exactly where every one of them is relative to every other one, you would need to write down a list of numbers so huge that no computer in the world could ever hold it. It's like trying to memorize the location of every grain of sand on every beach on Earth, all at once.

The paper argues that trying to solve this by tracking the entire cloud at once is a dead end. Instead, the authors propose a clever trick: Don't look at the whole cloud; just look at the neighborhoods.

The Solution: The Neighborhood Watch

Instead of trying to map the whole universe, the authors suggest breaking the cloud down into small, manageable clusters. Think of it like a city. You don't need to know the traffic flow of the entire country to understand how a specific neighborhood is moving. You just need to know how the people in your block are moving and how they interact with the next block over.

The authors developed a method called convex relaxation. In plain English, this means they turned a super-hard, messy puzzle into a smoother, easier one that gives a "best guess" answer.

How it works: They only keep track of the "local marginals." This is a fancy way of saying they only track the statistics of small groups of particles (like a pair of neighbors or a small cluster) rather than the whole crowd.
The Result: They get a "lower bound." Imagine you are trying to find the shortest path through a maze. You can't see the whole maze, so you calculate the absolute minimum distance you could possibly travel. You might not find the exact path yet, but you know you can't do better than that number. The paper shows that their method gives a very tight, computable lower bound on the cost of moving the cloud.

The Special Case: The "Benamou-Brenier" Highway

The paper highlights a special version of this problem called Dynamic Optimal Transport. This is like a super-highway where the cloud moves according to the laws of physics (specifically, fluid dynamics).

The Discovery: The authors proved that if you use their method on this specific type of problem, you don't just get a lower bound; you actually recover the exact "velocity field." Think of this as a wind map that tells you exactly how fast and in what direction the air is blowing at every point to get the cloud from shape A to shape B.
The Confidence: They didn't just guess this; they mathematically proved that their discrete, step-by-step method recovers the exact same result as the famous continuous physics formula (the Benamou-Brenier formula) when you look at the grid points.

The "Fitting" Trick: From Statistics to a Movie

Here is the really cool part. The math gives them the statistics of the cloud at each step (like "50% of the particles in this corner are moving left"), but it doesn't give them a movie of the particles moving. It's like having a photo of a crowd but not knowing who is walking where.

To fix this, they developed a kernel-fitting procedure.

The Analogy: Imagine you have a blurry photo of a dance floor. You know the average position of the dancers. Now, you want to find a specific dance move (a "kernel") that, if you taught it to a robot, would make the robot mimic that blurry photo.
The Application: They tested this on Ising models, which are like grids of tiny magnets (spins) that can point up or down. They wanted to move a grid of magnets from a state where they all like to align (ferromagnetic) to a state where they like to alternate (antiferromagnetic).
The Result: They used their math to get the "blurry photo" (the local statistics) and then "fitted" a specific type of magnetic update rule (called Glauber dynamics) to match it. In their simulations, the robot dance (the fitted Glauber dynamics) matched the blurry photo almost perfectly.

What They Don't Do (and What They Rule Out)

It's important to know what this paper doesn't claim:

No Magic: They don't claim to solve the problem for every possible situation instantly. They specifically focus on situations where the interactions are "local" (neighbors affect neighbors) and sparse. If every particle affected every other particle in a complex, dense way, their method would still struggle.
Not a "Win" for Everything: They don't say their method is better than all other methods in every case. For example, they compared their method to a "particle-based back-propagation" method (which is like training a neural network to guess the path). In their specific test with 15 dimensions, their method was faster and more accurate at predicting the cloud's shape than the particle method. But they present this as a specific experimental result, not a universal law.
No "Future" Guarantees: They don't claim this will immediately cure diseases or build new engines. They explicitly state that extending this to broader classes of controlled dynamics is a "direction that remains open." They are laying the groundwork, not finishing the building.

The Numbers and The Proof

The Experiments: They ran simulations with dimensions up to 50.
The Time Steps: They used grids with 10 time steps for the Gaussian tests and 5 time steps for the Ginzburg–Landau tests.
The Ising Model: They tested on a 1D chain of 30 spins and a 2D grid of 4x4 (16 spins).
The Speed: In one test, their method solved the problem in about 99.55 seconds (for the static reference) and 539.09 seconds (for the dynamic version), which was significantly faster than the particle-based training method they compared it against.

The Bottom Line

The authors have built a new set of tools that let us navigate the "curse of dimensionality" by ignoring the impossible task of tracking everything and focusing only on the local neighborhood. They proved that for certain physics problems, this shortcut gives the exact right answer. For other complex problems (like the magnetic spins), it gives a very good lower bound and a way to reconstruct a working model that mimics the behavior.

They didn't solve the whole universe, but they found a very smart way to solve a huge chunk of it without needing a supercomputer the size of a planet.

Technical Summary: Convex Relaxations for the Optimization of Markov Processes

Problem Statement
The paper addresses the problem of optimizing a Markov process that interpolates between two prescribed probability distributions, $\mu$ and $\nu$ , over a state space $\Omega$ while minimizing a cumulative cost. The process is defined by a sequence of intermediate laws $\{\rho_s\}_{s=0}^T$ and Markov transition kernels $\{K_s\}_{s=0}^{T-1}$ . The objective is to minimize the sum of one-step costs:
$\inf \sum_{s=0}^{T-1} \int_{\Omega} \int_{\Omega} c_s(x, y) K_s(x, dy) d\rho_s(x)$
subject to the initial and terminal constraints ( $\rho_0 = \mu, \rho_T = \nu$ ) and the Markov evolution constraint ( $\rho_{s+1} = (K_s)_* \rho_s$ ).

The primary computational challenge is the curse of dimensionality. In high-dimensional state spaces, representing the full joint distribution of consecutive states (the coupling $\pi_s$ ) is intractable. The paper focuses on settings where the admissible transition kernels satisfy specific constraints (e.g., support constraints, local update rules) and where the cost function admits a local decomposition.

Methodology
The authors propose a framework based on sequential-coupling formulations and convex relaxations that exploit locality and sparse interaction structures.

Sequential-Coupling Reformulation:
The problem is reformulated from optimizing transition kernels to optimizing a sequence of joint couplings $\pi_s(dx, dy) = \rho_s(dx)K_s(x, dy)$ . The constraints are rewritten in terms of the marginals of these couplings. The intermediate distributions are absorbed into the couplings, where $\rho_{s+1}$ is the right marginal of $\pi_s$ and the left marginal of $\pi_{s+1}$ .
Convex Relaxations:
To avoid representing the full coupling $\pi_s$ , the authors develop two types of convex relaxations that retain only low-order local information:
- Marginal Relaxation: The full coupling is replaced by its local marginals on a set of coordinate clusters $\mathcal{C}$ $C$ and cluster pairs defined by a cluster graph $\mathcal{G} = (\mathcal{C}, \mathcal{E})$ $G = (C, E)$ . The relaxation enforces:
  - Consistency between cluster and cluster-pair marginals.
  - Mass conservation across time steps (projected onto retained cluster pairs).
  - Local positivity and global positivity constraints (the latter ensuring the local marginals can be extended to a global non-negative measure, often via a Positive Semidefinite (PSD) constraint on a moment-like matrix).
  - Admissibility constraints projected onto the local marginals.
- Cluster Moment Relaxation: Instead of full marginals, the method uses a finite set of moments against prescribed basis functions (e.g., monomials) on the clusters. This is suitable for continuous state spaces. The decision variables are moment matrices. Constraints include moment consistency, mass conservation, and global positivity (PSD constraints on the assembled moment matrices).
Both frameworks result in convex optimization problems (Linear Programs for finite states with affine constraints, or Semidefinite Programs (SDPs) for continuous states or general constraints). These provide computable lower bounds for the original problem and recover low-order statistics of the intermediate distributions.
Recovery of Dynamics:
- Dynamic Optimal Transport (Benamou–Brenier): When the state space is convex, the cost is kinetic ( $\|x-y\|^2$ ), and no kernel constraints exist, the problem recovers the Benamou–Brenier geodesic. The authors show that the dual variables of the relaxed problem approximate the dual potentials of the Benamou–Brenier problem. By differentiating these potentials, one can recover an approximate velocity field, which induces a flow and a corresponding Markov kernel.
- General Constrained Processes: For general constraints (e.g., single-spin updates in Ising models), the method fits a parametric family of kernels (e.g., Glauber dynamics) to the recovered local statistics. This is done by minimizing the squared error between the predicted next-step marginals (via the parametric kernel) and the recovered marginals from the relaxation.

Key Contributions

Formulation: The paper recasts Markov process optimization into a sequential-coupling formulation and proposes a convex relaxation framework that scales to high dimensions by utilizing sparse local information (marginals or moments) rather than full joint distributions.
Dynamic Optimal Transport Connection: It demonstrates that dynamic optimal transport is a special case of this framework. Crucially, it provides a procedure to recover the underlying Benamou–Brenier velocity field from the dual variables of the relaxed problem, bridging the gap between static relaxations and dynamic flows.
Generalization to Constrained Dynamics: The framework extends beyond unconstrained transport to handle general Markov processes with hard constraints. The authors illustrate this by fitting Glauber dynamics to transport between Ising models, converting recovered local statistics into an implementable Markov kernel.

Results
The paper presents numerical experiments validating the approach:

Gaussian Transport: In a 50-dimensional Gaussian setting, the moment relaxation accurately recovers intermediate means, covariances, and affine velocity fields. The method is shown to be computationally efficient (solved in seconds via SDP) and more accurate than particle-based back-propagation methods in terms of covariance error along the trajectory.
Ginzburg–Landau Transport: The method successfully transports a Gaussian distribution to a non-Gaussian Ginzburg–Landau distribution in 10 dimensions. Maximum-entropy reconstruction from the recovered moments captures the gradual deformation of the distribution, including local and longer-range correlations.
Ising Models: The approach handles constrained transport between ferromagnetic and antiferromagnetic Ising models (1D and 2D). The marginal relaxation (solved as an LP) recovers local spin marginals, which are then used to fit time-inhomogeneous Glauber dynamics. The fitted dynamics successfully reproduce the recovered marginals and generate valid sample trajectories.

Significance and Claims
The paper claims that its framework offers a tractable alternative to high-dimensional Markov process optimization by avoiding the exponential cost of full state representation. It provides:

Computable Lower Bounds: The relaxations yield rigorous lower bounds for the optimal cost.
Recoverable Statistics: The method recovers low-order statistics (means, covariances, moments) of the intermediate laws.
Dynamic Reconstruction: Unlike static transport methods, this framework allows for the reconstruction of the underlying dynamics (velocity fields or transition kernels) from the relaxed solution.
Versatility: It unifies dynamic optimal transport and constrained stochastic control (like Glauber dynamics) under a single convex optimization umbrella, applicable to both discrete and continuous state spaces.

The authors modestly note that while the method recovers local statistics and approximate dynamics, the exact preservation of locality in intermediate distributions remains an open theoretical question, and the framework is currently limited to specific types of constraints and cost structures.