Skip to article
← All posts

Displacement convexity

Why optimal transport respects a density cap

Preserving density bounds along quadratic Wasserstein geodesics in Euclidean space.

Suppose a population must move from one density to another, without exceeding a prescribed density along the way. In a convex Euclidean domain, the ordinary quadratic optimal transport path already meets this requirement whenever both endpoint densities lie below the same constant cap. There is no need to modify the path.

This follows from displacement convexity: convexity along the straight trajectories of optimally matched particles. We first recall this notion, then use a change-of-variables argument to prove the density bound. The result is discussed in Proposition 15.22 of Optimal Transport for Machine Learners [1].

Mixture and displacement interpolation

Let \(\alpha_0,\alpha_1\in\mathcal P_2(\mathbb R^d)\), the probability laws with finite second moment. The ordinary mixture \((1-t)\alpha_0+t\alpha_1\) removes mass from one distribution and adds it to the other. Displacement interpolation instead matches particles and moves them. If \(\pi\) is a quadratic optimal coupling, define

\[\alpha_t=((1-t)x+ty)_\#\pi,\qquad 0\le t\le1.\]

This is a constant-speed geodesic for the quadratic Wasserstein distance:

\[W_2(\alpha_s,\alpha_t)=|s-t|W_2(\alpha_0,\alpha_1).\]

For an absolutely continuous source, the coupling is induced by the Brenier map \(T=\nabla\phi\), with \(\phi\) convex, and \(\alpha_t=(T_t)_\#\alpha_0\), where \(T_t=(1-t)\operatorname{Id}+tT\).

A functional \(\mathcal F\) is \(\lambda\)-displacement convex when

\[\begin{aligned} \mathcal F(\alpha_t) \le{}&(1-t)\mathcal F(\alpha_0)+t\mathcal F(\alpha_1)\\ &-\frac{\lambda}{2}t(1-t)W_2(\alpha_0,\alpha_1)^2. \end{aligned}\]

Here we require the inequality along the geodesics under discussion. For absolutely continuous endpoints the geodesic is unique. In settings where geodesics are not unique, “along every geodesic” and “along some geodesic” must be distinguished.

Displacement convexity of potential energy

If \(V\) is a \(\lambda\)-convex function on \(\mathbb R^d\), apply its ordinary convexity inequality to each particle segment and integrate:

\[\mathcal V(\alpha)=\int V(x)\,d\alpha(x) \quad\Longrightarrow\quad \mathcal V\text{ is }\lambda\text{-displacement convex}.\]

The converse follows by testing Dirac masses. Mixture convexity is different: \(\mathcal V\) is always linear along mixtures, even when \(V\) is nonconvex, so it does not test the convexity of the potential.

Similarly, if \(W(x,y)\) is jointly convex, then \(\frac12\iint W(x,y)\,d\alpha(x)d\alpha(y)\) is displacement convex. Apply the convexity of \(W\) to two independent copies of the optimal particle coupling. Internal energies, which depend on the density, require a different argument.

The change-of-variables formula

Write \(\alpha_i=\rho_i\,dx\). In the smooth case, mass conservation along the transport map gives

\[\rho_t(T_t(x)) =\frac{\rho_0(x)}{\det((1-t)I+tDT(x))}.\]

The matrix \(DT\) is positive semidefinite because \(T\) is the gradient of a convex function. We can therefore apply the following determinant inequality.

Lemma 1 (density along an optimal trajectory). For quadratic displacement interpolation between absolutely continuous measures,

\[\begin{aligned} \rho_t(T_t(x))^{-1/d} \ge{}&(1-t)\rho_0(x)^{-1/d}\\ &+t\rho_1(T(x))^{-1/d} \end{aligned}\]

for \(\alpha_0\)-almost every \(x\), whenever the endpoint densities are positive at the corresponding points.

Proof: the concavity of the determinant root

For a smooth positive-definite Jacobian, the endpoint identity gives \(\rho_1(T(x))=\rho_0(x)/\det DT(x)\). The matrix inequality

\[\det((1-t)I+tA)^{1/d} \ge(1-t)+t\det(A)^{1/d},\qquad A\succeq0,\]

therefore yields the result after division by \(\rho_0(x)^{1/d}\).

Why does the determinant inequality hold?

For positive eigenvalues \(\lambda_1,\ldots,\lambda_d\), let \(g=(\prod_i\lambda_i)^{1/d}\). Expand \(\prod_i((1-t)+t\lambda_i)\) by choosing \(k\) factors \(\lambda_i\) at a time. For \(1\le k\le d\), the arithmetic–geometric mean inequality over all \(\binom dk\) such products gives

\[\sum_{|S|=k}\prod_{i\in S}\lambda_i \ge\binom dk g^k.\]

Indeed, each eigenvalue occurs in exactly \(\binom{d-1}{k-1}\) subsets. Applying this bound to every coefficient in the expansion yields \(\det((1-t)I+tA)\ge((1-t)+tg)^d\). Zero eigenvalues follow by continuity.

For nonsmooth optimal maps, use their almost-everywhere approximate derivative and the change-of-variables theorem for Brenier maps. The derivative is symmetric positive semidefinite, and the same Jacobian identities hold almost everywhere on the positive-density sets. This is the standard optimal-Jacobian result underlying McCann's displacement-convexity theorem [2]; smoothness of the map is not an additional hypothesis of the lemma. \(\square\)

For example, the convexity of \(-\log\det\) gives displacement convexity of the entropy \(\operatorname{Ent}(\rho)=\int\rho\log\rho\,dx\), when the integrals are well defined:

\[\operatorname{Ent}(\alpha_t) =\operatorname{Ent}(\alpha_0) -\int\log\det((1-t)I+tDT)\,d\alpha_0.\]

Adding a finite \(\lambda\)-convex potential \(V\) gives \(\lambda\)-displacement convexity of \(\mathrm{KL}(\alpha\mid Z^{-1}e^{-V}dx)\), where \(Z=\int e^{-V}dx<\infty\). One first adds the entropy and potential inequalities for finite-energy endpoints; the extended-valued statement follows by approximation. This avoids manipulating undefined differences of infinite integrals. The density cap below follows from the stronger determinant-root inequality.

Preservation of a uniform density bound

Theorem 1 (preservation of a density cap). Let \(\Omega\subset\mathbb R^d\) be convex, and let \(\alpha_0,\alpha_1\in\mathcal P_2(\Omega)\) have densities bounded above by a common constant \(0<\kappa<\infty\). Their quadratic Wasserstein geodesic stays in \(\Omega\) and satisfies

\[0\le\rho_t\le\kappa \qquad\text{for every }t\in[0,1].\]
Proof: interpolate the reciprocal density

Both endpoint terms in Lemma 1 are at least \(\kappa^{-1/d}\). Their convex combination is therefore at least \(\kappa^{-1/d}\), giving \(\rho_t(T_t(x))\le\kappa\) almost everywhere. Convexity of \(\Omega\) keeps each segment between \(x\) and \(T(x)\) inside \(\Omega\). \(\square\)

The same proof gives a sharper bound for different endpoint caps \(\|\rho_i\|_\infty\le\kappa_i\):

\[\|\rho_t\|_\infty \le\bigl((1-t)\kappa_0^{-1/d} +t\kappa_1^{-1/d}\bigr)^{-d}.\]

Optimality of the matching is essential. For example, let both endpoints be uniform on \([-1,1]\), with density \(1/2\). Matching \(x\) to \(-x\) has the correct marginals, but all interpolating particles collide at zero when \(t=1/2\). The resulting Dirac mass has no finite density cap. The optimal matching is instead the identity, which keeps the density unchanged.

Equivalently, the set

\[\mathcal K_\kappa =\{\rho\,dx\in\mathcal P_2(\Omega):0\le\rho\le\kappa\}\]

is geodesically convex. Its indicator—zero on this set and \(+\infty\) outside—is a displacement-convex functional.

Density constraints in the Benamou–Brenier formulation

The Benamou–Brenier formulation expresses transport as the least kinetic action among density–velocity pairs satisfying the continuity equation and fixed endpoints [3]:

\[W_2(\alpha_0,\alpha_1)^2 =\inf\int_0^1\int|v_t(x)|^2\,d\alpha_t(x)\,dt.\]

When motion is restricted to \(\Omega\), require each \(\alpha_t\) to be concentrated there and impose the continuity equation on \(\mathbb R^d\) after extension by zero; this encodes no flux through the boundary. Add the requirement \(\rho_t\le\kappa\). This can only increase the infimum. But Theorem 1 says that the ordinary optimal geodesic is feasible for the constrained problem, and its action is already \(W_2^2\). Thus the constrained and unconstrained values are equal.

The conclusion need not hold after changing these assumptions. A nonconvex domain may force particles around obstacles; a varying cap \(\kappa(x)\) may create a bottleneck; an additional running cost may favor paths other than the ordinary geodesic. Crowd-motion and congestion models can therefore behave differently. The theorem concerns a constant cap, a convex Euclidean domain, admissible endpoints, and pure kinetic transport.

Numerical experimentation: one-dimensional density bounds

On the line, write \(Q_i\) for the endpoint quantiles. The interpolation is simply \(Q_t=(1-t)Q_0+tQ_1\). In the smooth strictly increasing example below, density satisfies \(\rho_t(Q_t(r))=1/Q_t'(r)\). A cap means \(Q_i'\ge1/\kappa\), a condition immediately preserved by interpolation.

Both endpoints are mixtures of localized Gaussians. Separate sliders select the source and target component counts \(k_0,k_1\), from one to eight; they need not be equal. With \(\varphi_\sigma(x)=(2\pi\sigma^2)^{-1/2}e^{-x^2/(2\sigma^2)}\), the initial choice \(k_0=k_1=2\) is

\[\begin{aligned} \rho_0(x)&=0.55\varphi_\sigma(x+1.5)+0.45\varphi_\sigma(x-0.2),\\ \rho_1(x)&=0.40\varphi_\sigma(x+0.2)+0.60\varphi_\sigma(x-1.5). \end{aligned}\]

The time slider follows their Wasserstein geodesic, not their linear mixture. The bandwidth slider makes the Gaussian components narrower or broader. We invert the two Gaussian-mixture CDFs numerically, then evaluate the intermediate density using

\[\rho_t(Q_t(r))= \left(\frac{1-t}{\rho_0(Q_0(r))} +\frac{t}{\rho_1(Q_1(r))}\right)^{-1}.\]

The dashed horizontal line is a certified common endpoint cap, close to the larger peak. For a mixture \(\rho(x)=\sum_{j=1}^k w_j\varphi_\sigma(x-m_j)\), all maxima lie between the extreme component centers: outside that interval every Gaussian varies in the same direction. Partition this interval into small cells \(I\). On each cell,

\[\sup_{x\in I}\rho(x)\le \frac{1}{\sigma\sqrt{2\pi}} \sum_{j=1}^k w_j e^{-\operatorname{dist}(m_j,I)^2/(2\sigma^2)}.\]

Each term is bounded by evaluating its Gaussian at the closest point of the cell to its center. Taking the largest cell bound gives a global cap; for a single Gaussian, its peak is known exactly. The figure recomputes this bound for both mixtures when their counts or bandwidth change. The density plot uses a tight vertical range starting at zero; the right panel shows the corresponding quantiles.

Source density in red, target in blue, and the interpolated density in teal. Both endpoint laws live on the whole real line; the plotted rank interval omits only \(2\times10^{-9}\) of the mass, without renormalization. The bound follows from the harmonic-density formula, rather than from a constraint imposed by a solver.

References

  1. Gabriel Peyré. Optimal Transport for Machine Learners, §15.2 and Proposition 15.22. Book manuscript.
  2. Robert J. McCann. A Convexity Principle for Interacting Gases. Advances in Mathematics 128(1), 153–179, 1997.
  3. Jean-David Benamou and Yann Brenier. A Computational Fluid Mechanics Solution to the Monge–Kantorovich Mass Transfer Problem. Numerische Mathematik 84, 375–393, 2000.
  4. Filippo Santambrogio. {Euclidean, Metric, and Wasserstein} Gradient Flows: an Overview. Bulletin of Mathematical Sciences 7, 87–154, 2017.

For the relation between geodesic convexity, variational evolution, and density-constrained gradient flows, see also [4].

How these posts and numerical experiments were prepared: AI disclosure.

Subscribe with an RSS reader: RSS Atom

How to subscribe

RSS and Atom let a reader app collect new posts for you; they are not email subscriptions. Opening these links in Safari may display plain text instead of a subscription form.

  1. Open an RSS reader, such as NetNewsWire on Mac.
  2. Choose Add feed or Subscribe in your reader (NetNewsWire calls it New Web Feed), then paste the RSS feed URL below. You can also use the Atom link above.

To copy manually, select the URL and press Command+C on Mac or Ctrl+C on Windows/Linux.

Back to the blog · Gabriel Peyré