Ordinary differential equations for regularized variational problems involving semi-discrete optimal transport

1. Problem Statement

The paper addresses a class of variational problems involving Optimal Transport (OT) combined with additional potential terms. The general formulation seeks to minimize a functional over a set of probability measures $\nu$:
$$\inf_{\nu \in \mathcal{P}(Y)} \inf_{\gamma \in \Gamma(\mu, \nu)} \left( \int_{X \times Y} c \, d\gamma + F(\nu) \right)$$
where:

• $\mu$ is a prescribed source measure on a compact set $X$.
• $\nu$ is a free target measure on a set $Y$.
• $c$ is a cost function.
• $F$ is a potential function (e.g., entropy, Wasserstein distance, or game-theoretic costs).

The authors focus on the semi-discrete setting where the target space $Y$ is a finite set of points $\{y_1, \dots, y_N\}$, while the source space $X$ remains continuous. To solve these problems numerically, they employ entropic regularization, introducing a parameter $t \in [0, 1]$ that interpolates between a fully regularized problem ($t=0$) and the original unregularized problem ($t=1$).

The specific regularized problem studied is:
$$\inf_{\nu, \gamma} \left( t \int c \, d\gamma + (1-t) \text{Ent}(\gamma | \mu \otimes \sigma) + t F(\nu) \right)$$
where $\text{Ent}$ is the relative entropy and $\sigma$ is the counting measure on $Y$.

2. Methodology

The core methodology involves characterizing the solution trajectory of the regularized problem as a function of the parameter $t$ using Ordinary Differential Equations (ODEs).

Dual Formulation

The authors derive the dual problem, which involves maximizing a concave functional $\Phi(\psi, t)$ with respect to dual variables $\psi \in \mathbb{R}^N$. The optimality condition is given by $\nabla_\psi \Phi(\psi, t) = 0$.

Derivation of the ODE

By applying the Implicit Function Theorem to the first-order optimality condition, the authors differentiate the solution trajectory $\psi(t)$ with respect to $t$. This yields a governing ODE:
$$D^2_{\psi,\psi}\Phi(\psi(t), t) \cdot \psi'(t) + \partial_t \nabla_\psi \Phi(\psi(t), t) = 0$$
However, this ODE is singular at $t=0$ due to terms involving $1/t$. To resolve this, the authors perform a change of variables $z(t) = \psi(t)/t$. They prove that the new trajectory $z(t)$ satisfies a well-posed Cauchy problem (Initial Value Problem) on the interval $[0, 1)$:
$$\left[ t D^2 K(tz, t) - D^2 F^*(-z) \right] z'(t) + \left[ D^2 K(tz, t)z + \partial_t \nabla K(tz, t) \right] = 0$$
with an explicitly known initial condition $z(0) = -\nabla F(\frac{1}{N}\mathbf{1})$.

Extension to $t=1$

The authors prove that the solution map $t \mapsto \psi(t)$ extends continuously to $t=1$. Therefore, by numerically integrating the ODE from $t=0$ to $t=1$, one obtains the solution to the original, unregularized variational problem.

They also analyze a variant where the potential $F(\nu)$ is not scaled by $t$, deriving a similar ODE structure for this case.

3. Key Contributions

The paper makes five primary theoretical and practical contributions:

1. Uniform Boundedness: They prove that the family of scaled dual solutions $\{\psi(t)/t\}_{t \in (0,1)}$ is uniformly bounded, provided the Legendre transform of the potential $F^*$ is strongly convex. This is crucial for stability.
2. Well-Posedness of the Scaled ODE: They establish that the transformed ODE for $z(t)$ is globally well-posed on $[0, 1)$, overcoming the singularity at $t=0$ found in the original formulation.
3. Parameter-Independent Variant: They extend these results to a variant where the regularization parameter does not scale the potential term $F$, proving well-posedness for this alternative formulation.
4. Continuity at the Limit: They rigorously prove that the solution path is continuous at $t=1$, ensuring that the limit of the ODE trajectory yields the exact solution to the unregularized problem.
5. Numerical Robustness: They demonstrate that solving the ODE provides the entire solution trajectory (the evolution of Laguerre cells) and does not require a "good" initial guess, unlike Newton's method.

4. Numerical Results and Experiments

The authors implemented third-order Runge-Kutta solvers to solve the derived ODEs for several test cases in 1D and 2D.

• Test Cases:
  • Standard semi-discrete OT with entropy.
  • Problems involving squared Wasserstein distance ($W_2^2$).
  • Problems with shifted entropy potentials.
  • Hedonic pricing models.
• Performance Metrics:
  • Convergence: The method exhibits empirical first-order convergence (and occasionally second-order) with respect to the time step $\Delta t$.
  • Robustness: The ODE-based approach successfully solved problems where Newton's method failed to converge due to poor initialization (particularly for larger $N$ or non-uniform densities).
  • Visualization: The method naturally generates the evolution of Laguerre cells (the geometric partition of space associated with the transport map) as $t$ goes from 0 to 1, offering geometric insight into the transition from the entropic state to the unregularized state.
• Trade-offs: While Newton's method is faster when it converges and achieves lower residuals, it is highly sensitive to initialization. The ODE method is slower but significantly more robust and provides a continuous path of solutions.

5. Significance

This work bridges the gap between entropic regularization and exact optimal transport solutions in the semi-discrete setting. Its significance lies in:

• Algorithmic Innovation: It offers a new class of algorithms (ODE-based) that are globally convergent without requiring heuristic initialization, addressing a major weakness of Newton-type solvers in high-dimensional or complex variational problems.
• Theoretical Insight: It provides a rigorous characterization of the solution path, proving that the entropic regularization trajectory is a smooth, well-behaved curve connecting the regularized and unregularized solutions.
• Geometric Interpretation: By tracing the trajectory, the method allows researchers to visualize how the transport plan (Laguerre cells) evolves, which is valuable for understanding the stability and structure of optimal transport maps.
• Broad Applicability: The framework applies to a wide range of variational problems beyond standard OT, including game theory (Cournot-Nash), urban planning, and hedonic pricing, making it a versatile tool for applied mathematics and machine learning.