Convex Relaxations for the Optimization of Markov Processes
For researchers in optimal transport and Markov processes, this work provides a tractable relaxation framework for high-dimensional problems, though it is incremental as it extends existing relaxation techniques to a new class of problems.
The paper addresses the curse of dimensionality in optimizing Markov processes between two distributions by developing convex relaxations based on local marginals and cluster moments, which provide computable lower bounds and recover low-order statistics. The method is applied to dynamic optimal transport and constrained processes between Ising models.
In this paper, we study the problem of optimizing Markov processes that interpolate between two prescribed probability distributions while minimizing a given cost. The main computational challenge is the curse of dimensionality: in high-dimensional state spaces, representing the full distribution is intractable. To address this, we reformulate the problem in terms of sequential couplings and develop convex relaxations based on local marginals and cluster moments. These relaxations exploit locality and sparse interaction structure, provide computable lower bounds, and recover low-order statistics of the intermediate laws. We identify dynamic optimal transport as a special case of our Markov process optimization problem and develop a procedure for recovering the underlying Benamou--Brenier dynamics from the relaxed solution. We also show that the procedure extends to more general Markov processes and illustrate it with a constrained process between Ising models.