{"id":1593,"date":"2013-09-14T06:11:30","date_gmt":"2013-09-14T11:11:30","guid":{"rendered":"http:\/\/sites.williams.edu\/Morgan\/?p=1593"},"modified":"2014-02-06T07:49:49","modified_gmt":"2014-02-06T12:49:49","slug":"optimal-transportation-with-constraint","status":"publish","type":"post","link":"https:\/\/sites.williams.edu\/Morgan\/2013\/09\/14\/optimal-transportation-with-constraint\/","title":{"rendered":"Optimal Transportation with Constraint"},"content":{"rendered":"

In Barcelona<\/a>, Robert McCann<\/a> talked<\/a> about his work<\/a>\u00a0with Jonathan Korman and Christian Seis on optimal transportation<\/a> with a constraint h<\/em>(x<\/em>,y<\/em>) on the flow from x<\/em> to y<\/em>. A constant constraint h<\/em> means that an x<\/em> must be spread out over at least fraction 1\/h<\/em> 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.\u00a0<\/p>\n

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

Note that the ball can have interesting topology,\u00a0as on a torus for example.<\/p>\n

Proof.<\/em> By the constraint a point x<\/em> must relate to a set of volume at least 1\/h<\/em>, 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<\/em> is the ball about y<\/em> with volume 1\/h<\/em> and the correspondence is admissible.<\/p>\n

2. Proposition.<\/strong> 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. <\/em><\/p>\n

The proof is trivial: the correspondence minimizes cost.<\/p>\n

Examples:<\/strong><\/p>\n

2.1<\/strong>. For integer\u00a0h<\/em>\u00a0\u2265 2, let\u00a0X<\/em>\u00a0consist of\u00a0h<\/em>\u00a0equal-volume regions in\u00a0Rn<\/sup><\/em>\u00a0such that the maximum diameter of a region is less than the minimum distance between regions. Let\u00a0c<\/em>(x<\/em>,y<\/em>) be a cost function on\u00a0X<\/em>\u00d7X<\/em>\u00a0increasing in distance. Then optimal transportation from\u00a0X<\/em>\u00a0to\u00a0X<\/em>\u00a0with constant constraint\u00a0h<\/em>\u00a0relates the points of each region to itself. (To apply the Proposition, subtract a constant from the cost.)<\/p>\n

2.2.<\/strong> For a centrally symmetric body in R<\/strong>n<\/sup><\/em>, cost c<\/em>(x<\/em>,y<\/em>)\u00a0= \u20132 x<\/em>\u2022y<\/em> (which is equivalent to (x\u2013<\/em>y<\/em>)<\/strong>2<\/sup>\u00a0because its integral differs by a constant), and constraint h<\/em> = 2, under optimal transportation x<\/em> corresponds to y<\/em> with x<\/em>\u2022y<\/em>\u00a0positive. In R<\/strong>1<\/sup>\u00a0central symmetry is unnecessary as long as the origin is the median. Similarly for any cost with the same sign as \u2013x<\/em>\u2022y<\/em>.\u00a0The analysis generalizes to any centrally symmetric probability measure on\u00a0R<\/strong>n<\/sup><\/em>\u00a0for which hyperplanes through the origin have measure 0 and to any probability measure on R<\/strong>1<\/sup>.<\/p>\n

2.3.<\/strong> For a planar region with h<\/em>-fold rotational symmetry, such as a square (h<\/em>=4), cost<\/span><\/strong><\/p>\n

c<\/em>(x<\/em>,y<\/em>) = (cos \u03c0\/h<\/em>)|x<\/em>||y<\/em>| \u2013\u00a0x<\/em>\u2022y<\/em>,<\/p>\n

and constant constraint h<\/em>, optimal transportation relates all points on a ray from the origin to a cone of angle \u03c0\/h<\/em> about that ray.<\/p>\n

2.4.<\/strong> Such examples of optimal transportation from Xi<\/sub><\/em>\u00a0to Yi<\/sub><\/em>\u00a0extend to optimal transportation from \u03a0Xi<\/sub><\/em>\u00a0to\u00a0\u03a0Yi<\/sub><\/em>\u00a0with a cost which is negative if and only if the costs of the projections are all negative: optimal transportation with constraint h<\/em> = \u03a0hi<\/sub><\/em>\u00a0relates points of negative cost. In particular, Example 2.3 generalizes to a product of such actions on R<\/strong>2<\/sup>n<\/sup><\/em>\u00a0with cost negative if and only if xi<\/sub><\/em>\u2022yi<\/sub><\/em> \u2265 (cos \u03c0\/hi<\/sub><\/em>)|xi<\/sub><\/em>||yi<\/sub><\/em>| for all i<\/em>\u00a0: optimal transportation with constant constraint h<\/em>\u00a0= \u03a0hi<\/sub><\/em>\u00a0relates all points with projections on rays from the origin to a product of cones of angle \u03c0\/hi<\/sub><\/em> about the ray.<\/p>\n

2.5.<\/strong> Such examples of optimal transportation from X<\/em> to Y<\/em> with cost c<\/em>(x<\/em>,y<\/em>)\u00a0extend to optimal transportation on warped products A\u00d7X<\/em>, A\u00d7Y<\/em>, as long as the cost c\u2032<\/em>(a<\/em>,x<\/em>,a<\/em>,y<\/em>) has the same sign as c<\/em>(x<\/em>,y<\/em>).\u00a0For example, for any 0 < h<\/em> < \u221e, Proposition 1 on the sphere, with cost c<\/em>(x<\/em>,y<\/em>) = a<\/em>|x<\/em>||y<\/em>| \u2013\u00a0x<\/em>\u2022y<\/em>, with a<\/em> 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.<\/p>\n

The following proposition is a generalization of McCann-Korman (Insights into Capacity Constrained Optimal Transport, Prop. 4.2).<\/p>\n

3. Proposition.<\/strong>\u00a0Let M1<\/sub>, M2<\/sub> be subsets of <\/em>R<\/strong>n<\/sup><\/em>\u00a0or Riemannian manifolds with boundary or metric measure spaces of volume V. Let Ti<\/sub> be a measure-preserving map from Mi<\/sub> to Mi<\/sub> and let T = T1<\/sub>\u00d7T2<\/sub>. Let c(x,y) be a cost satisfying coT = -c. If density f\u00a0h on M1<\/sub>\u00d7M2<\/sub>\u00a0provides optimal transportation from M1<\/sub>\u00a0to M2<\/sub>\u00a0with constant constraint h, then density f‘<\/em>h’oT provides optimal transportation with constraint h’, where 1\/h + 1\/h’ = 1 and <\/em>\u00a0f\u00a0‘ = 1-f.<\/em><\/p>\n

Proof.\u00a0<\/em> If \u00a0f\u00a0<\/em>h<\/em> provides optimal transportation for cost c<\/em> with constraint h<\/em>, then f<\/em> ‘h<\/em>‘ \u00a0provides the most expensive transportation for cost c<\/em> with constraint h’<\/em>, and hence optimal transportation for cost –c<\/em>. Therefore \u00a0f’h’oT <\/em>provides\u00a0optimal transportation for cost –coT =\u00a0<\/em>c<\/em>\u00a0with constraint h<\/em>‘.<\/p>\n

Example.<\/em> Take M<\/em>1<\/sub>\u00a0and M<\/em>2<\/sub>\u00a0in R<\/strong>n<\/sup><\/em><\/em>, with M<\/em>1<\/sub>\u00a0centrally symmetric, and cost\u00a0\u00a0–x<\/em>\u2022y<\/em>\u00a0(which is equivalent to (x\u2013<\/em>y<\/em>)<\/strong>2<\/sup>). Then central inversion in x<\/em> carries optimal transportation with constraint h<\/em>\u00a0to optimal transportation with constraint h<\/em>‘.<\/p>\n

Revised 7 October 2013.<\/p>\n","protected":false},"excerpt":{"rendered":"

In Barcelona, Robert McCann talked about his work\u00a0with 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 […]<\/p>\n","protected":false},"author":269,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[14043],"tags":[],"class_list":["post-1593","post","type-post","status-publish","format-standard","hentry","category-math"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/1593","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/users\/269"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/comments?post=1593"}],"version-history":[{"count":31,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/1593\/revisions"}],"predecessor-version":[{"id":1597,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/posts\/1593\/revisions\/1597"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/media?parent=1593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/categories?post=1593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/tags?post=1593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}