Optimal Transportation with Constraint

In Barcelona, Robert McCann talked about his work with Jonathan Korman and Christian Seis on optimal transportation with a constraint h(x,y) on the flow from x to y. A constant constraint h means that an x must be spread out over at least fraction 1/h of the target; there is not the capacity to send it all to the most desirable spot. Here we present a simplified extension of some of their results. 

1. Proposition. Consider a Riemannian manifold of say unit volume, with a transitive group of measure-preserving isometries, with cost of transportation c(x,y) increasing in distance and constant constraint 0 < h < ∞. Then optimal transportation is uniquely given by relating a point x to a geodesic ball about x of volume 1/h.

Note that the ball can have interesting topology, as on a torus for example.

Proof. By the constraint a point x must relate to a set of volume at least 1/h, and the geodesic ball minimizes cost among such. By the symmetry assumption, all balls of the same radius have the same volume, so the set related to a target point y is the ball about y with volume 1/h and the correspondence is admissible.

2. Proposition. Consider two Riemannian manifolds X, Y (or more generally two metric measure spaces) of say unit volume, with transportation cost c(x,y) and constant constraint h. Suppose that for for a point x in X, c(x,y) is negative for 1/h of the y’s in Y and positive for the rest, and for a point y in Y, c(x,y) is negative for 1/h of the x’s in X and positive for the rest (modulo sets of measure 0). Then the correspondence between points of negative cost uniquely provides optimal transportation under the constraint.

The proof is trivial: the correspondence minimizes cost.


2.1. For integer h ≥ 2, let X consist of h equal-volume regions in Rn such that the maximum diameter of a region is less than the minimum distance between regions. Let c(x,y) be a cost function on X×X increasing in distance. Then optimal transportation from X to X with constant constraint h relates the points of each region to itself. (To apply the Proposition, subtract a constant from the cost.)

2.2. For a centrally symmetric body in Rn, cost c(x,y) = –2 xy (which is equivalent to (x–y)2 because its integral differs by a constant), and constraint h = 2, under optimal transportation x corresponds to y with xy positive. In R1 central symmetry is unnecessary as long as the origin is the median. Similarly for any cost with the same sign as –xy. The analysis generalizes to any centrally symmetric probability measure on Rn for which hyperplanes through the origin have measure 0 and to any probability measure on R1.

2.3. For a planar region with h-fold rotational symmetry, such as a square (h=4), cost

c(x,y) = (cos π/h)|x||y| – xy,

and constant constraint h, optimal transportation relates all points on a ray from the origin to a cone of angle π/h about that ray.

2.4. Such examples of optimal transportation from Xi to Yi extend to optimal transportation from ΠXi to ΠYi with a cost which is negative if and only if the costs of the projections are all negative: optimal transportation with constraint h = Πhi relates points of negative cost. In particular, Example 2.3 generalizes to a product of such actions on R2n with cost negative if and only if xiyi ≥ (cos π/hi)|xi||yi| for all i : optimal transportation with constant constraint h = Πhi relates all points with projections on rays from the origin to a product of cones of angle π/hi about the ray.

2.5. Such examples of optimal transportation from X to Y with cost c(x,y) extend to optimal transportation on warped products A×X, A×Y, as long as the cost c′(a,x,a,y) has the same sign as c(x,y). For example, for any 0 < h < ∞, Proposition 1 on the sphere, with cost c(x,y) = a|x||y| – xy, with a chosen so that optimal transportation relates points of negative cost, extends to the ball, with points on a ray from the origin related to a cone of negative cost about that ray.

The following proposition is a generalization of McCann-Korman (Insights into Capacity Constrained Optimal Transport, Prop. 4.2).

3. Proposition. Let M1, M2 be subsets of Rn or Riemannian manifolds with boundary or metric measure spaces of volume V. Let Ti be a measure-preserving map from Mi to Mi and let T = T1×T2. Let c(x,y) be a cost satisfying coT = -c. If density f h on M1×M2 provides optimal transportation from M1 to M2 with constant constraint h, then density fh’oT provides optimal transportation with constraint h’, where 1/h + 1/h’ = 1 and  f ‘ = 1-f.

Proof.  If  h provides optimal transportation for cost c with constraint h, then fh‘  provides the most expensive transportation for cost c with constraint h’, and hence optimal transportation for cost –c. Therefore  f’h’oT provides optimal transportation for cost –coT = c with constraint h‘.

Example. Take M1 and M2 in Rn, with M1 centrally symmetric, and cost  –xy (which is equivalent to (x–y)2). Then central inversion in x carries optimal transportation with constraint h to optimal transportation with constraint h‘.

Revised 7 October 2013.

Leave a Reply

Your email address will not be published. Required fields are marked *