1. Introduction
In recent years, the Monge-Kantorovich theory of optimal mass transport has impacted a wide range of mathematical and scientific disciplines from probability theory to geophysics and from thermodynamics to machine learning [Reference Ambrosio, Gigli and Savaré1, Reference Cullen and Douglas7, Reference Gangbo and McCann10, Reference Villani20, Reference Villani21]. Indeed, the Monge-Kantorovich paradigm of transporting one distribution to another, by seeking to minimize a suitable cost functional, has proved enabling in many ways. It gave rise to a class of control problems [Reference Chen, Georgiou and Pavon5, Reference Chen, Georgiou and Pavon6], underlies variational principles in physics [Reference Jordan, Kinderlehrer and Otto13, Reference Otto16], provided natural regularization penalties in inverse problems [Reference Bredies, Carioni, Fanzon and Romero2], led to new identification techniques in data science [Reference Haker, Zhu, Tannenbaum and Angenent12, Reference Peyré and Cuturi17], in graphical models [Reference Fan, Haasler, Karlsson and Chen9], and linked to large deviations in probability theory [Reference Chen, Georgiou and Pavon4, Reference Léonard15].
Historically, the Monge-Kantorovich theory proved especially relevant in economics when physical commodities were the object to be transported – a fact that contributed to L. Kantorovich receiving the Nobel prize. Extensions that pertain to physical constraints along the transport naturally were soon brought up. For instance, moment-type constraints have been considered in [Reference Svetlozar18, Section 4.6.3] and, more recently, far generalized in [Reference Ekren and Soner8]. Congestion being a significant impediment to transport has also drawn the attention of theorists and practitioners alike. For instance, besides optimizing for transportation, considerations of an added path-dependent cost to alleviate congestion have been considered in [Reference Carlier, Jimenez and Santambrogio3], see also [Reference Santambrogio19, Section 4] for a comprehensive study of this research direction. Along a different direction, constraints have been introduced for probability densities as part of the optimization problem. Such bounds can capture the capacity of the transportation medium and as such have been studied in [Reference Korman and McCann14] or dynamical flow constraints as in [Reference Gladbach and Kopfer11].
Figure 1. Illustration of optimal transport through a toll with finite throughput.
In the present work, we formulate and address a natural variant of the standard optimal mass transport problem by imposing a hard constraint on the flux rate at a point along the path between distributions. Specifically, we pose and resolve the most basic problem where the restriction on throughput of the transport plan takes place at a single point. With this constraint in place, we seek to minimize a usual quadratic cost functional.
The analysis we provide focuses on one-dimensional distributions, with transport taking place on
$\mathbb R$
. We prove existence and uniqueness of an optimal transport plan and, under suitable regularity conditions, give an explicit construction. A slight generalization of our formulation, where the distributions have support on
$\mathbb R^d$
but the transportation is to take place through a specified ‘constriction’ point, with a similar throughput constraint, can be worked out in the same manner, and it is sketched in the concluding remarks. The more general case where the transport takes place on higher dimensional manifolds with the throughput through possibly multiple points, curves, or surfaces similarly restricted is substantially more challenging and much remains open.
The problem formulation and ideas in the mathematical analysis that follows can be visualized by appealing to Figure 1. We begin with two probability densities
$\rho _0, \rho _1$
having support on
$\mathbb{R}$
and finite second-order moments and seek to transport one to the other,
$\rho _0$
to
$\rho _1$
, within a window of time (herein, of duration normalized to
$1$
) while minimizing a quadratic cost in the local velocity. That is, we seek to minimize the action integral of kinetic energy along the transport path. The minimal cost of the unrestricted transport is the so-called Wasserstein distance
$\mathcal W_2(\rho _0,\rho _1)$
(a metric on the space of probability measures); we refer to standard references [Reference Villani20, Reference Villani21] for the unconstrained optimal transport problem. The schematic in Figure 1 exemplifies a constraint at a pre-specified point,
$x_0$
, that can be seen as the location of constriction, or, of a toll along the transport, where throughput is bounded. That is, the flow rate across
$x_0$
for mass times velocity is bounded by a value
$h$
. A vertical axis pointing downwards at
$x_0$
marks the time when a specific mass-element crosses the toll, necessitating at least
$1/h$
duration for the unit mass of the probability density
$\rho _0$
to go through, in the most favourable case where the throughput rate is maintained for the duration (that is normalized to
$1$
time unit).
In the body of the paper, we prove existence and uniqueness of an optimal transport plan, and, assuming suitable regularity of the distributions, we provide an explicit construction for the solution. We further explore consequences of the toll being kept maximally ‘busy’ while mass is being transported through, in conjunction with minimizing the quadratic cost criterion on the kinetic energy, and we highlight ensuing properties of the optimal plan.
Specifically, in Section 2 we develop the formulation of the flux constraint and give a precise definition of the problem (Problem 1). In Section 3, we prove existence and uniqueness (Theorem 1) of solution, while conveniently recasting the problem in terms of a flux variable (Problem 2). Section 5 deals with the structural form of the transport and properties of solutions; we summarize the basic elements that allow an explicit construction of the solution in Algorithm 1. Section 6 provides a rudimentary example of transporting between uniform distributions, that highlights the essential property that speed needs to be suitably adjusted so as to fully utilize the throughput of the toll, while minimizing the quadratic cost. We close (Section 7) with a discussion on possible extensions of the problem to higher dimensions and multiple tolls. While the theory may be readily extended in certain cases, much remains to be understood. Such problems are of natural engineering and scientific interest.
2. Problem formulation
We consider two probability measures
$\rho _0$
and
$ \rho _1$
on
$\mathbb{R}$
, having finite second-order moments and that each admits a density with respect to the Lebesgue measure. Throughout, we follow a standard (slight) abuse of notation and use the same symbols
$\rho _i\;:\;\mathbb{R}\rightarrow \mathbb{R}_{\geq 0}$
, for
$i=1,2$
, for the corresponding probability densities of the two measures. In this case, there exists a unique non-decreasing optimal transport map
$T$
from
$\rho _0$
to
$\rho _1$
(Theorem 2.5, [Reference Santambrogio19]). Following a standard formulation of transport problems, we consider
$Y\;:\;[0,1]\times \mathbb{R} \rightarrow \mathbb{R}$
such thatFootnote 1
$Y_{0\# \rho _0} = \rho _0$
and
$Y_{1\# \rho _0} = \rho _1$
, and we are interested in minimizing
\begin{equation} J(\partial _t Y) \;:\!=\; \int _0^1 \int _{\mathbb{R}} (\partial _t Y_t(x))^2\rho _0(x)dxdt. \end{equation}
In the absence of any additional constraint on
$Y$
, the solution is
$Y^\star _t(x)= x + t(T(x)-x)$
for
$T$
the optimal transport map between
$\rho _0$
and
$\rho _1$
and
$J(\partial _tY_t^\star )=\mathcal{W}_2^2(\rho _0,\rho _1)$
, the squared Wasserstein-2 distance between the two [Reference Villani20]. Here, however, for a certain
$x_0 \in \mathbb{R}$
, we introduce a constraint on the flux passing through
$x_0$
, as explained below. Throughout the paper,
$T$
will always denote the optimal transportation map in the absence of any such constraint. The purpose of the present work of course is to develop a theory that addresses the case of transport with a bound on the flux through
$x_0$
.
When all functions are smooth and well defined, a flux constraint at
$x_0$
can be expressed as
\begin{equation*}|\rho _t(x_0)v_t(x_0)|\leq h\ \ \ \forall t\in (0,1)\end{equation*}
for
$\rho _t$
the density of
$Y_{t\# \rho _0}$
and
$v_t(x_0)=\partial _t Y_t(Y_t^{-1}(x_0))$
. However in the general case, if
$\rho _t$
is not continuous (or does not even exist), this constraint is not well defined. One way to deal with such a situation is to recast the constraint as requiring that,Footnote 2
$\forall t\in (0,1)$
,
\begin{equation} \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\ \frac{1}{|\alpha _2-\alpha _1|} \int \unicode{x1D7D9}_{\{x_0 \in (Y_t(x) + \alpha _1, Y_t(x) + \alpha _2)\}} |\partial _t Y_t(x)|\rho _0(x)dx \leq h. \ \end{equation}
Then, if
$\rho _0$
is continuous and
$Y_t$
is a
$C^1$
diffeomorphism, the left-hand side (LHS) of (2.2) amounts to
\begin{align*} \mbox{LHS } (2.2) & = \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\frac{1}{|\alpha _2-\alpha _1|}\int \unicode{x1D7D9}_{\{x_0 \in (y + \alpha _1, y + \alpha _2)\}} |\partial _t Y_t(Y_t^{-1}(y))|\rho _t(y)dy \\[5pt] & = \rho _t(x_0)v_t(x_0). \end{align*}
Interestingly, when
$Y_t$
fails to be a
$C^1$
diffeomorphism, special care is needed. For instance, take
$x_0=0$
and
$Y_t(x) = \unicode{x1D7D9}_{\{x\in [-2,-1]\}}(1-2t)^3x$
. The constraint (2.2) is satisfied since
$\partial _t Y_t(x)=0$
at
$t=1/2$
, and no mass sits near the toll for any
$t\neq 1/2$
. Thus, the formulation (2.2) fails to capture the situation where infinite mass passes through with zero velocity. We reformulate so as to avoid this technicality.
Consider the modified constraint that bounds the flux passing through
$x_0$
, expressed as requiring that
$\forall t\in (0,1)$
\begin{equation} \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\ \frac{1}{|\alpha _2-\alpha _1|} \int \unicode{x1D7D9}_{\{x_0 \in (Y_{t + \alpha _1}(x), Y_{t + \alpha _2}(x))\}} \rho _0(x)dx \leq h. \end{equation}
In the case where
$Y_t$
is
$C^1$
, using the Taylor expansion of
$Y$
in time, the left-hand side (LHS) of (2.3) amounts to
\begin{align*} \mbox{LHS } (2.3) = & \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}} \ \frac{1}{|\alpha _2-\alpha _1|} \int \unicode{x1D7D9}_{\{x_0 \in (Y_{t}(x)+\partial _tY_{t }(x)\alpha _1+o(\alpha _1), Y_{t}(x)+\partial _tY_{t }(x)\alpha _2+o(\alpha _2))\}} \rho _0(x)dx\\[5pt] = & \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}} \int \Big ( \unicode{x1D7D9}_{\{Y_t(x) \in (x_0-\partial _tY_{t }(x)\alpha _2+o(\alpha _2), x_0-\partial _tY_{t }(x)\alpha _1+o(\alpha _1))\}} \frac{|\partial _t Y_t(x)|\unicode{x1D7D9}_{\{|\partial _t Y_t(x)|\gt 0\}}}{|\alpha _2-\alpha _1||\partial _t Y_t(x)|}\\[5pt] & +\unicode{x1D7D9} _{\{Y_t(x) \in (x_0+o(\alpha _1), x_0+o(\alpha _2))\}} \frac{\unicode{x1D7D9}_{\{\partial _t Y_t(x)=0\}}}{|\alpha _2-\alpha _1|} \Big ) \rho _0(x)dx . \end{align*}
Using a change of variables, we readily see that (2.3) implies (2.2) and that if
$Y_t$
is a
$C^1$
diffeomorphism, the two constraints are identical. Note also that,
$\forall t\in (0,1)$
, condition (2.3) is equivalent to
\begin{equation} \forall \alpha _1,\alpha _2\in \mathbb{R}, \quad \int \unicode{x1D7D9}_{\{x_0 \in (Y_{t + \alpha _1}(x), Y_{t + \alpha _2}(x))\}} \rho _0(x)dx \leq h|\alpha _2-\alpha _1|. \end{equation}
Define
\begin{equation} \Omega = \{x\in \mathrm{Supp}\,(\rho _0)\ | \ x_0 \in (x,T(x)) \text{ or } x_0 \in (T(x),x)\}, \end{equation}
where
$T$
is the optimal transport map of the unconstrained problem. Thus,
$\Omega$
contains the support of mass that needs to cross the toll station, at some point in time, in either direction. From (2.4), it is evident that
$h \geq \rho _0(\Omega )$
is necessary for the existence of a map satisfying the constraint (since the transport will take place over the time interval
$[0,1]$
). Typically,
$h \gt \rho _0(\Omega )$
is required, except in some special cases where
$h = \rho _0(\Omega )$
may suffice, as for example when
$\rho _0 =\unicode{x1D7D9}_{\{[0,1]\}}$
,
$x_0=1$
and
$\rho _1 =\unicode{x1D7D9}_{\{[1,2]\}}$
. From here on we assume that
$h\gt \rho _0(\Omega )$
.
We are now in a position to cast our optimization problem in terms of a velocity field
$v_t(x)$
that will effect the transport; formally,
$v_t(x)=\partial _tY_t(x)$
relates to our earlier notation when functions are smooth. For any
$v \in L^2([0,1]\times \mathbb{R}, \mathbb{R})$
, define the map
$Y^v\;:\;[0,1]\times \mathbb{R}\rightarrow \mathbb{R}$
as the flow of
$v$
:
\begin{equation} Y^v_t=\mathrm{Id}+\int _0^t v_\tau d\tau, \end{equation}
with
$\mathrm{Id}$
denoting the identity map in
$\mathbb{R}$
.
Definition 2.1.
Let
${\mathcal V}$
denote the set of functions
$v \;:\;[0,1]\times \mathbb{R}\rightarrow \mathbb{R}$
for which
$\int _{0}^1\int _{\mathbb{R}}v(x,t)^2\rho _0(x)dxdt$
$\lt \infty$
and are such that
$Y^v$
(the flow of
$v$
) satisfies:
-
(i)
$Y_{1\# \rho _0}^v = \rho _1$
-
(ii)
$\forall t \in (0,1)$
,
$Y_t^v$
satisfies the constraint (2.4).
Our problem can now be stated as follows.
Problem 1. Determine
\begin{equation} \inf \limits _{v\in{\mathcal V}} J(v), \end{equation}
over the class
$\mathcal V$
of Definition 2.1
, and assert existence, uniqueness, and the functional form of minimizing solutions.
We first show that there exist velocity fields belonging to
$\mathcal V$
.
Proposition 2.2.
Supposing that
$\rho _0,\rho _1$
have finite second-order moments and are absolutely continuous with respect to the Lebesgue measure, the set of functions
$\mathcal V$
of Definition 2.1 is non-empty.
Proof. Let us build an explicit map
$v\in{\mathcal V}$
. First, for
$x\notin \Omega$
(with
$\Omega$
defined in (2.5)), we can set
$v_t(x)=T(x)-x$
, as mass at the point
$x$
does not cross the toll. Let us now take care of the points that lie in
$\Omega$
by splitting it into two sets:
\begin{equation*}\Omega _1=\{x\in \Omega | x\lt x_0\} \quad \text { and } \quad \Omega _2=\{x\in \Omega | x\gt x_0\}. \end{equation*}
The velocity
$v_t(x)$
for
$x\in \Omega$
will be piecewise constant with 3 different pieces.
-
(i) Define
$T_1$
the optimal transport map between the densities
$\rho _{0|\Omega _1}$
(the restriction of
$\rho _0$
to
$\Omega _1$
) and
$\mu _1(x)=h\unicode{x1D7D9}_{\{x\in [x_0-\rho _0(\Omega _1)/h,x_0]\}}$
. Likewise, define
$T_2$
the optimal transport map between the densities
$\rho _{0|\Omega _2}$
and
$\mu _2(x)=h\unicode{x1D7D9}_{\{x\in [x_0,x_0+\rho _0(\Omega _2)/h]\}}$
. Letand
\begin{equation*}t^\star = \rho _0(\Omega )\end{equation*}
$a\;:\;\Omega \rightarrow \mathbb{R}$
defined byThen, the flow of
\begin{equation*}a(x)=\unicode {x1D7D9}_{\{x\in \Omega _1\}}\frac {2}{1-t^\star/h}(T_1(x)-x)+\unicode {x1D7D9}_{\{x\in \Omega _2\}}\frac {2}{1-t^\star/h}(T_2(x)-x).\end{equation*}
$a$
transports the densities
$\rho _{0|\Omega _1}$
onto
$\mu _1$
and
$\rho _{0|\Omega _2}$
onto
$\mu _2$
in a time
$(1-t^\star/h)/2$
.
-
(ii) Define
$b\;:\;[x_0-\rho _0(\Omega _1)/h,x_0+\rho _0(\Omega _2)/h]\rightarrow \mathbb{R}$
byLikewise, the flow of
\begin{equation*}b(x)=\unicode {x1D7D9}_{\{x\in [x_0-\rho _0(\Omega _1)/h,x_0]\}}\frac {\rho _0(\Omega _1)}{t^\star }-\unicode {x1D7D9}_{\{x\in [x_0,x_0+\rho _0(\Omega _2)/h]\}}\frac {\rho _0(\Omega _2)}{t^\star }.\end{equation*}
$b$
transports the densities
$\mu _1$
onto
$\mu _1^+(x)=\mu _1(x-\frac{\rho _0(\Omega _1)}{h})$
and
$\mu _2$
onto
$\mu _2^-(x)=\mu _2(x+\frac{\rho _0(\Omega _2)}{h})$
in a time
$\frac{t^\star }{h}$
. Writing
$T$
for the optimal transport map between
$\rho _0$
and
$\rho _1$
, let be
$T_1^{\prime}$
the optimal transport map between the densities
$\mu _1^{+}$
and
$T_{\#\rho _{0|\Omega _1}}$
. Likewise, let be
$T_2^{\prime}$
the optimal transport map between the densities
$\mu _2^{-}$
and
$T_{\#\rho _{0|\Omega _2}}$
respectively.
-
(iii) Finally, define
$c\;:\;[x_0-\rho _0(\Omega _2)/h,x_0+\rho _0(\Omega _1)/h]\rightarrow$
byThen, the flow of
\begin{equation*}c(x)=\unicode {x1D7D9}_{\{x\in [x_0-\rho _0(\Omega _2)/h,x_0]\}}\frac {2}{1-t^\star/h}(T_2^{\prime}(x)-x)+\unicode {x1D7D9}_{\{x\in [x_0,x_0+\rho _0(\Omega _1)/h]\}}\frac {2}{1-t^\star/h}(T_1^{\prime}(x)-x).\end{equation*}
$c$
transports the densities
$\mu _1^{+}$
onto
$T_{\#\rho _{0|\Omega _1}}$
and
$\mu _2^{-}$
onto
$T_{\#\rho _{0|\Omega _2}}$
in a time
$(1-t^\star/h)/2$
.
Therefore, the flow of the three velocity fields
$a,b,c$
applied successively transports
$\rho _{0|\Omega }$
onto
$T_{\# \rho _{0|\Omega }}$
in a time
$(1-t^\star/h)/2+t^\star/h+(1-t^\star/h)/2=1$
. Furthermore, mass crosses the toll only during the interval
$[(1-t^\star/h)/2,t^\star/h+(1-t^\star/h)/2]$
and the flow rate at the toll values
$h\frac{\rho _0(\Omega _1)}{t^\star }+h\frac{\rho _0(\Omega _2)}{t^\star }=h$
during this time. Finally, as
$\rho _0$
and
$\rho _1$
have finite second-order moment, we easily see that
$a,b$
and
$c$
verify the
$L^2$
condition.
3. Existence of a solution
Let us first define the set of flows of velocity fields in the class
$\mathcal V$
.
Definition 3.1.
The class of functions
$\mathcal Y$
is defined as the set of maps
$Y\;:\;[0,1]\times \mathbb{R}\rightarrow \mathbb{R}$
such that there exist
$v\in{\mathcal V}$
so that
$Y$
is the flow of
$v$
, i.e.,
$Y_t=Y^v_t=\mathrm{Id}+\int _0^t v_\tau d\tau$
.
From here on, the
$v$
in the notation
$Y^v_t$
is suppressed as we are truly interested in the transport map. We first derive certain useful properties of candidate minimizers of our problem. To this end, for any
$Y \in{\mathcal Y}$
and
$x\in \Omega$
, we define
\begin{equation*} {toll}_Y(x)=\inf \{ t \mid x_0=Y_t(x)\}. \end{equation*}
Thus, the function
${toll}_Y$
specifies the times of transit through the toll station of mass that is initially located at
$x$
and then transported via
$Y$
.
It is clear that the function
${toll}_Y$
must be injectiveFootnote 3 for a minimizing solution and that mass flow takes place always in the same direction across the toll station. Then,
$\forall t\in (0,1)$
, (2.3) is equivalent to
\begin{equation*} \limsup \limits _{\substack {\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\ \frac {1}{|\alpha _2-\alpha _1|}{toll}_{Y\#\rho _0}((t+ \alpha _1,t+ \alpha _2)) \leq h, \end{equation*}
and so, if
${toll}_{Y\#\rho _0}$
(the measure on
$[0,1]$
that weighs the mass that goes through
$x_0$
at different times
$t\in [0,1]$
) admits a continuous density
$\varrho _{{toll}}$
, the constraint amounts to
$\varrho _{{toll}}(t)\leq h$
. Note also that this condition is different than simply stating
$\rho _t(x_0)\leq h$
, as the latter does not take into account the speed of transport. Then we see that for
$x\notin \Omega$
, we can restrict ourselves to considering maps
$Y\in{\mathcal Y}$
such that
$Y_t(x)=x + t(T(x)-x)$
for
$T$
the optimal transport map between
$\rho _0$
and
$\rho _1$
. Thus, in the sequel, without loss of generality we always suppose that
$\Omega =\mathrm{Supp}\,(\rho _0)$
and that
$\sup \mathrm{Supp}\,(\rho _0)\leq x_0 \leq \inf \mathrm{Supp}\,(\rho _1)$
. For clarity, we group together the set of assumptions used on probability measures
$\rho _0$
and
$\rho _1$
.
Assumptions 1.
The probability measures
$\rho _0$
and
$\rho _1$
satisfy the following:
-
• They have finite second-order moments.
-
• They are absolutely continuous with respect to the Lebesgue measure.
-
•
$\sup \mathrm{Supp}\,(\rho _0)\leq x_0 \leq \inf \mathrm{Supp}\,(\rho _1)$
.
Note that
$\Omega$
in (2.5) is precisely
$\mathrm{Supp}\,(\rho _0)$
, since all the mass in
$\rho _0$
needs to be transported across the toll. Also note that if
$h$
is large enough so that the optimal transport map
$T$
verifies the constraint, then
$T$
automatically provides a solution to Problem 1. Thus, the problem is equivalent to that in the unconstrained case.
For
$Y\in{\mathcal Y}$
and
${toll}_Y$
, its corresponding transit-time function define the map
$\overline{Y}\;:\;[0,1]\times \mathbb{R}\rightarrow \mathbb{R}$
by
\begin{equation} \overline{Y}_t(x) = \left \{ \begin{array}{ll} x+t\frac{x_0-x}{{toll}_{Y}(x)} & \text{if } t\leq{toll}_{Y}(x) \\[5pt] x_0+(t-{toll}_{Y}(x))\frac{T(x)-x_0}{1-{toll}_{Y}(x)} & \text{if } t \geq{toll}_{Y}(x) \end{array} \right . \end{equation}
and note
$\overline{{\mathcal Y}}=\{ \overline{Y} \ |\ Y \in{\mathcal Y}\}$
the set of functions of this type. The next statement states that we can restrict our minimization problem to functions of the form (3.1). Specifically, it states that for any candidate minimizer
$Y \in{\mathcal Y}$
, the speed of transport needs to remain constant at all times prior to transit, and again, constant at all times after transit. In addition, from the functional form, we see that
$Y_1=T(x)$
for all
$x$
. This last statement says that the final destination of mass originally located at
$x$
is the same, whether we apply
$T$
or the optimal plan that abides by the constraint; the only thing that changes in the two cases is the speed while the mass traverses the segment before
$x_0$
and after (cf. example in Section 6).
Proposition 3.2.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 1, we have
\begin{equation*}\inf \limits _{Y\in {\mathcal Y}} J(\partial _t Y) = \inf \limits _{\overline {Y}\in \overline {{\mathcal Y}}} J(\partial _t \overline {Y})\end{equation*}
Proof. For
$Y\in{\mathcal Y}$
and
${toll}_Y$
, define
\begin{equation} Y^c_t(x) = \left \{ \begin{array}{ll} x+t\frac{x_0-x}{{toll}_Y(x)} & \text{if } t\leq{toll}_Y(x) \\[5pt] x_0+(t-{toll}_Y(x))\frac{Y_1(x)-x_0}{1-{toll}_Y(x)} & \text{if } t \geq{toll}_Y(x) \end{array} \right . \end{equation}
Thus,
$Y^c$
maintains the terminal destination
$Y_1(x)$
and the crossing time
${toll}_Y(x)$
, for the mass that was initially at
$x$
, while the speed of each particle remains constant before and after crossing. It follows that
$Y^c \in{\mathcal Y}$
and that
$J(\partial _t Y^c)\leq J(\partial Y)$
as for any
$x\in \mathrm{Supp}\,(\rho _0)$
and path
$\gamma_x \in C^{1}([0,{toll}_Y(x)],[x,x_0])$
, the mean squared velocity of this path is always larger than the one of the path of constant speed, i.e.,
\begin{equation*}\int _0^{{toll}_Y(x)}\dot{\gamma}_x(t)^2dt\geq \int _0^{{toll}_Y(x)}\left (\frac {x_0-x}{{toll}_Y(x)}\right )^2dt=\frac {(x_0-x)^2}{{toll}_Y(x)}.\end{equation*}
We can then restrict
$\mathcal Y$
to the set of functions that are of the form (3.2) since candidate minimizers will always be of that form.
As the position
$Y_1(x)$
in (3.2) doesn’t impact the constraint (2.3), we consider how
$Y_1(x)$
may depend on the time of crossing
${toll}_Y(x)$
. Specifically,
$Y_1$
must be a minimum over the set of functions
\begin{equation*}\{f\;:\;\mathrm{Supp}\,(\rho _0)\rightarrow \mathrm {Supp}\,(\rho _1)\ | \ f_{\#\rho _0}=\rho _1\},\end{equation*}
for the cost
\begin{equation*} \int _{{toll}_Y(x)}^1 \int _{\mathbb {R}} \left (\frac {Y_1(x)-x_0}{1-{toll}_Y(x)}\right )^2\rho _0(x)dxdt = \int _{\mathbb {R}} \frac {(Y_1(x)-x_0)^2}{1-{toll}_Y(x)}\rho _0(x)dx. \end{equation*}
From this, we deduce that almost everywhere,
${toll}_Y(x)\leq{toll}_Y(y)$
iff
$Y_1(x)\geq Y_1(y)$
. Indeed, for
$x_1,x_2,t_1,t_2\in \mathbb{R}_{\gt 0}$
, we have that if
$x_1\lt x_2$
and
$t_1\leq t_2$
then
$\frac{x_1}{t_1}+\frac{x_2}{t_2}\lt \frac{x_1}{t_2}+\frac{x_2}{t_1}$
. Then if
${toll}_Y(x)\leq{toll}_Y(y)$
and
$Y_1(x)\lt Y_1(y)$
, then
\begin{equation*}\frac {(Y_1(x)-x_0)^2}{1-{toll}_Y(x)}+\frac {(Y_1(y)-x_0)^2}{1-{toll}_Y(y)}\gt \frac {(Y_1(x)-x_0)^2}{1-{toll}_Y(y)}+\frac {(Y_1(y)-x_0)^2}{1-{toll}_Y(y)}\end{equation*}
so
$Y_1$
would not be optimal. Furthermore, as the problem is reversible (we can switch
$\rho _0$
and
$\rho _1$
), we can deduce in the same way that
${toll}_Y(x)\geq{toll}_Y(y)$
iff
$x\leq y$
. Therefore,
$Y_1(x)$
is increasing, and we conclude that it is identical to
$T$
the optimal transport map between
$\rho _0$
and
$\rho _1$
.
From Proposition 3.2, we deduce that for
$Y$
, the flow of a (candidate) optimal solution, the map
$x\mapsto{toll}_{Y}$
is strictly decreasing on the support of
$\rho _0$
and that
$Y_t$
is one to one, for all
$t$
. We also deduce that for almost every
$x\in \mathrm{Supp}\,(\rho _0)$
, the velocity
$v_t(x)$
is constant (in
$t$
) before crossing the toll, changes at the toll, and then stays the same until
$Y_t(x)$
reaches
$T(x)$
at time
$t=1$
. This can be formally written as
\begin{equation*}v_t(x)=v_0(x)\unicode {x1D7D9}_{\{t\lt {toll}_Y(x)\}}+v_1(x)\unicode {x1D7D9}_{\{t\geq {toll}_Y(x)\}}.\end{equation*}
Let us write
$\mathrm{v}(x)=\frac{x_0-x}{{toll}_Y(x)}$
for the velocity of transport prior to crossing the toll, for the mass initially located at
$x$
at the start. Then, in light of Proposition 3.2, our problem is reduced to the following formulation.
Problem 1′. Determine
\begin{align} \mathrm{arg}\,\min_{\mathrm{v}} & \int _0^1 \int _{\mathbb{R}} \Big ( \mathrm{v}(x)^2\unicode{x1D7D9}_{\{t\leq \frac{x_0-x}{\mathrm{v}(x)}\}} + \left (\frac{T(x)-x_0}{1-\frac{x_0-x}{\mathrm{v}(x)}}\right )^2\unicode{x1D7D9}_{\{t\geq \frac{x_0-x}{\mathrm{v}(x)}\}}\Big ) \rho _0(x)dxdt\nonumber \\[5pt] =\, & \mathrm{arg}\,\min_{\mathrm{v}} \int _{\mathbb{R}} \Big ( \mathrm{v}(x)(x_0-x) + \frac{(T(x)-x_0)^2}{1-\frac{x_0-x}{\mathrm{v}(x)}}\Big ) \rho _0(x)dx, \end{align}
subject to
$x\mapsto \frac{x_0-x}{\mathrm{v}(x)}={toll}_{\mathrm{v}}(x)$
being decreasing and bounded between 0 and 1, (since
$\frac{x_0-x}{\mathrm{v}(x)}={toll}(x)$
) and
\begin{equation} \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\ \frac{1}{|\alpha _2-\alpha _1|} \int \unicode{x1D7D9}_{\{(t+\alpha _1)\mathrm{v}(x)\lt x_0-x \lt (t+\alpha _2)\mathrm{v}(x)\}} \rho _0(x)dx \leq h. \end{equation}
We now argue the existence of a minimizer
$\mathrm{v}^\star$
.
Proof. Let
$(\mathrm{v}_n)_n$
be a minimizing sequence of Problem 2 (therefore also of Problem 1) and write
$toll_n\;:\ \mathrm{Supp\,}(\rho _0)\rightarrow (0,1)$
the associated toll function:
$toll_n(x)=\frac{x_0-x}{\mathrm{v}_n(x)}$
. Let
$(\alpha _k)_k$
be a dense sequence in
$\mathrm{Supp\,}(\rho _0)$
(for example the rational numbers). By compactness, we have that
$\forall k\in \mathbb{N}$
,
$toll_n(\alpha _k)$
admits a converging subsequence in
$n$
. Then using a diagonal argument, there exists a subsequence
$(\mathrm{v}_{\varphi (n)})_n$
and
$\beta _k\in [0,1]$
such that,
$\forall k\in \mathbb{N}$
,
$toll_{\varphi (n)}(a_k)\xrightarrow [n \to +\infty ]{} \beta _k$
, and
$\alpha _k\leq \alpha _l \iff \beta _l\leq \beta _k$
. For
$x\in \mathrm{Supp\,}(\rho _0)$
, and
$(\alpha _{\psi _x(k)})_k$
a decreasing subsequence converging to
$x$
, let be
$toll(x)=\lim _k \beta _{\psi _x(k)}=\lim _k \lim _n toll_{\varphi (n)}(a_{\psi _x(k)})$
, which is well defined as
$\beta _{\psi _x(k)}$
is increasing. Then,
$toll_{\varphi (n)}(x)$
converges to
$toll(x)$
for any
$x$
being a point of continuity of
$toll$
. As
$toll$
is a non-increasing map, it has at most a countable number of points of discontinuity; therefore,
$toll_{\varphi (n)}$
converges to
$toll$
a.e. Let be
$f\;:\;\mathbb{R}\rightarrow \mathbb{R}$
a continuous bounded map, we then have by dominated convergence
\begin{equation*}\int _{\mathbb {R}}f(toll_{\varphi (n)}(x))\rho _0(x)dx \xrightarrow [n \to +\infty ]{} \int _{\mathbb {R}}f(toll(x))\rho _0(x)dx,\end{equation*}
so
$toll_{\varphi (n)\# \rho _0}$
converges weakly to
$toll_{\# \rho _0}$
. For
$x\in \mathrm{Supp}\,(\rho _0)\setminus \{x\ | \ toll(x)=0\}$
, define
$\mathrm{v}(x)=\frac{ x_0-x}{toll(x)}$
, it is well defined a.e. because
$\{x\ | \ toll(x)=0\}$
has measure 0 as
$(\mathrm{v}_n)_n$
is a minimizing sequence. Then,
$\mathrm{v}_{\varphi (n)}$
converges a.e. to
$\mathrm{v}$
and as the constraint (3.4) is equivalent to
\begin{equation*} \forall \alpha _1,\alpha _2\in \mathbb {R}, \quad \ {toll}_{\mathrm {v}}((t+ \alpha _1,t+ \alpha _2)) \leq h|\alpha _2-\alpha _1|, \end{equation*}
$\mathrm{v}$
verifies the constraint. Finally, using Fatou’s lemma we have
$\lim _nJ(\mathrm{v}_n)\geq J(\mathrm{v})$
so
$\mathrm{v}$
is a minimizer of Problem 1.
4. Uniqueness of the solution
Before we proceed with the proof of uniqueness of the minimizer, we recast our problem in terms of flux as the optimization variable. For
$u \in L^1([0,1]\times \mathbb{R},\mathbb{R})$
, a candidate flux (i.e., mass times velocity) defines a corresponding mass-measure
$\rho _t^u$
on
$\mathbb{R}$
by duality via:
$\forall \phi \in C_c^\infty (\mathbb{R},\mathbb{R})$
,
\begin{equation*} \int _{\mathbb {R}} \phi (x)d\rho _t^u(x) = \int _{\mathbb {R}} \phi (x)\rho _0(x)dx+\int _0^t\int _{\mathbb {R}} (\nabla \phi (x))u_r(x)dxdr . \end{equation*}
Equivalently, we have that
$\rho ^u$
solves in the weak sense the continuity equation
\begin{equation*} \left \{\begin {array}{ll} \partial _t\rho _t^u = - \nabla \cdot u\\[5pt] \rho _0^u=\rho _0 \end {array}\right .. \end{equation*}
For a flux
$u$
such that
$\forall t \in (0,1)$
,
$\rho ^u_t$
admits a positive density, let us express the cost of
$u$
as
\begin{equation} \mathrm{J}(u)= \int _0^1 \int _{\mathbb{R}} \frac{u_t(y)^2}{\rho _t^u(y)}dydt \end{equation}
In the above, by a slight abuse of notation as it is often done, we used
$\rho ^u$
to denote both the measure and the corresponding density, allowing these to be distinguished by the specific usage and context. Let us define the set of admissible fluxes.
Definition 4.1.
The class of functions
$\mathcal U$
is defined as the set of flux
$u\;:\;[0,1]\times \mathbb{R}\rightarrow \mathbb{R}$
defined a.e. such that
$\mathrm{J}(u)\lt \infty$
and
-
(i′)
$\forall t \in (0,1)$
,
$\rho ^u_t$
admits a positive density function and
$\rho ^u_1 = \rho _1$
-
(ii′) for
$T_t^u$
the optimal transport map between
$\rho _0$
and
$\rho ^u_t$
, for
$x\in \mathrm{Supp}\,(\rho _0)$
a.e. the map
$t\mapsto T_t^u(x)$
is a bijection from
$[0,1]$
to
$[x,T(x)]$
and is differentiable a.e.
-
(iii′) satisfy
(4.2)
\begin{equation} \forall t \in (0,1), \limsup \limits _{x_1 \rightarrow x_0,\ x_2 \rightarrow x_0}\ \frac{1}{|x_2-x_1|} \int _{x_1}^{x_2} |u_t(y)|dy \leq h. \end{equation}
In the proof of Proposition 4.2, we show that
$\mathcal U$
is non-empty as any solution
$v\in{\mathcal V}$
of Problem 2 generates a flux
$u\in{\mathcal U}$
. We can now recast our problem in terms of flux as the optimization variable.
Problem 2. Consider
\begin{equation} \inf \limits _{u\in{\mathcal U}} \mathrm{J}(u). \end{equation}
over the class
$\mathcal U$
of Definition 4.1
. Determine existence, uniqueness, and functional form for a minimizing solution
$u$
.
We will first prove the equivalence of the above formulation in Problem 2 with that in Problem 1. The advantage of Problem 2 is that the constraint is now convex which will be convenient in proving uniqueness. Note that here we use roman
$\mathrm{J}$
with argument the flux field, to echo the earlier usage in (2.1) where the action integral
$J$
first appeared with argument the velocity.
Proposition 4.2.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 1, Problems
1
and 3 are equivalent.
Proof. Let
$Y\in \overline{{\mathcal Y}}$
be a solution of Problem 1,
$v_t({\cdot})=\partial _tY_t(Y_t^{-1}({\cdot}))$
the associated velocity (defined everywhere except at the points
$(toll(x),x)$
, for all
$x\in \mathrm{Supp}\,(\rho _0)$
) and
$\rho _t=Y_{t\#\rho _0}$
the associated mass flow. Then for
$\phi \in C_c^\infty (\mathbb{R},\mathbb{R})$
, we have
\begin{align*} \int _{\mathbb{R}} \phi (x)d\rho _t(x) & = \int _{\mathbb{R}} \phi (Y_t(x))\rho _0(x)dx\\[5pt] & = \int _{\mathbb{R}} \Big (\phi (Y_0(x))+\int _0^t \partial _t\phi (Y_r(x))dr\Big )\rho _0(x)dx\\[5pt] & = \int _{\mathbb{R}} \Big (\phi (Y_0(x))+\int _0^t \nabla \phi (Y_r(x)) v_r(Y_r(x))dr\Big )\rho _0(x)dx \\[5pt] & = \int _{\mathbb{R}} \phi (x) \rho _0(x)dx +\int _0^t\int _{\mathbb{R}} \nabla \phi (x) v_r(x)d\rho _r(x)dr. \end{align*}
Therefore,
$Y$
defines a unique flux
$u\in L^1([0,1]\times \mathbb{R},\mathbb{R})$
(
$u$
is
$L^1$
by Jensen inequality) by
$u_t(x)=v_t(x)\rho _t(x)$
with
$\mathrm{J}(u)=J(\partial _t Y)$
. Furthermore, writing
$T_t$
for the optimal transport map between
$\rho _0$
and
$\rho _t$
, we have for
$x\in \mathrm{Supp}\,(\rho _0)$
almost everywhere, the map
$t\mapsto T_t(x)$
is a bijection from
$[0,1]$
to
$[x,T(x)]$
and its differential at
$x$
equals
$v_t(T_t(x))$
. On the other hand, for
$\mathrm{v}(x)=\partial _tY_0(x)=\frac{x_0-x}{{toll}_{\mathrm{v}}(x)}$
we have that the left-hand side of (3.4) amounts to
\begin{align*} \mbox{LHS }(2.4) & = \limsup \limits _{\substack{\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\ \int \unicode{x1D7D9}_{\{Y_t(x) +\alpha _1\mathrm{v}(x)\lt x_0\lt Y_t(x)+\alpha _2\mathrm{v}(x)\}} \frac{\mathrm{v}(x)}{|\alpha _2-\alpha _1|\mathrm{v}(x)}\rho _0(x)dx\\[5pt] & = \limsup \limits _{\substack{\epsilon _1 \rightarrow 0 \\ \epsilon _2 \rightarrow 0}}\ \frac{1}{|\epsilon _2-\epsilon _1|}\int \unicode{x1D7D9}_{\{y +\epsilon _1\lt x_0\lt y+\epsilon _2\}} v_t(y)\rho _t(y)dy. \end{align*}
Therefore,
$u\in{\mathcal U}$
and we conclude that
$\inf \limits _{u\in{\mathcal U}} \mathrm{J}(u)\leq \min \limits _{Y \in{\mathcal Y}} J(\partial _t Y)$
.
For establishing the reverse direction, let be
$u\in{\mathcal U}$
and define
$T_t^u$
the optimal transport map between
$\rho _0$
and
$\rho _t^u$
. For
$F_t(x)=\int _{-\infty }^x \rho _t^u(y) dy$
, the cumulative distribution function of
$\rho _t^u$
, it is well known that
$T_t^u(x)=F_t^{-1}(F_0(x))$
, see [Reference Villani21, Chapter 1]. For
$x\in \mathrm{Supp}\,(\rho _0)$
, write
$f_x\;:\;[x,T(x)]\rightarrow [0,1]$
for the inverse in time of
$t\mapsto T_t^u(x)$
, i.e., for
$y\in [x,T(x)]$
,
$T_{f_x(y)}^u(x)=y$
. Since
$\forall t\in [0,1]$
we have
$F_t(F_t^{-1}(F_0(x)))=F_0(x)$
, we obtain for all
$\phi \in C_c^\infty ((0,1)\times \mathbb{R},\mathbb{R})$
,
\begin{align} \int _0^1\int _{\mathbb{R}}\partial _t \phi _t(x) F_t(F_t^{-1}(F_0(x))) dxdt &=\int _0^1\int _{\mathbb{R}}\partial _t \phi _t(x) F_0(x)dxdt\nonumber \\[5pt] \int _0^1\int _{\mathbb{R}}\partial _t \phi _t(x)\int _{\mathbb{R}} \unicode{x1D7D9}_{\{y\leq T_t^u(x)\}}\rho ^u_t(y)dy dxdt&=0. \end{align}
Furthermore, for
$x,y\in \mathbb{R}$
using integration by parts we have
\begin{align*} \int _0^1 \partial _t \phi _t(x) \unicode{x1D7D9}_{\{y\leq T_t^u(x)\}}\rho ^u_t(y)dt&=\int _0^1\partial _t \phi _t(x)\unicode{x1D7D9}_{\{f_x(y)\leq t\}}\rho ^u_t(y)dt\\[5pt] &=-\int _0^1\phi _t(x)\unicode{x1D7D9}_{\{f_x(y)\leq t\}}\partial _t \rho ^u_t(y)dt-\phi _{f_x(y)}(x)\rho ^u_{f_x(y)}(y), \end{align*}
so the left-hand side of (4.4) equals
\begin{align} -\int _{\mathbb{R}}\int _{\mathbb{R}}\left (\int _0^1\phi _t(x)\unicode{x1D7D9}_{\{y\leq T_t^u(x)\}}\partial _t \rho ^u_t(y)dt+\phi _{f_x(y)}(x)\rho ^u_{f_x(y)}(y)\right )dxdy. \end{align}
Through a change of variable
$s=f_x(y)$
and recalling that
$T^u_{f_x(y)}(x)=y$
, we obtain that
\begin{align*} \int _{\mathbb{R}}\phi _{f_x(y)}(x)\rho ^u_{f_x(y)}(y)dy=\int _0^1\phi _s(x)\rho ^u_s(T^u_s(x))\partial _tT^u_s(x)ds. \end{align*}
On the other hand, as
$(\rho _t^u,u_t)$
solves the continuity equation we have
\begin{align*} \int _{\mathbb{R}}\unicode{x1D7D9}_{\{y\leq T_t^u(x)\}}\partial _t \rho ^u_t(y)dy=-\int _{\mathbb{R}}\unicode{x1D7D9}_{\{y\leq T_t^u(x)\}} \nabla u_t(y)dy=-u_t(T_t^u(x)). \end{align*}
Then, we have that (4.5) equals
\begin{equation*}-\int _{\mathbb {R}}\int _0^1\phi _t(x)\big ({-}u_t(T_t^u(x))+\rho ^u_t(T^u_t(x))\partial _tT^u_t(x)\big )dtdx.\end{equation*}
Therefore, from (4.4) we deduce that
$(t,x)$
almost everywhere we have
\begin{equation*}\partial _tT^u_t(x)=\frac {u_t(T_t^u(x))}{\rho ^u_t(T^u_t(x))}.\end{equation*}
Therefore,
$T_t^u$
defines a map in
$\mathcal Y$
such that
\begin{align*} J(\partial _t T_t^u)&=\int _0^1\int _{\mathbb{R}}(\partial _t T_t^u(x))^2dt\rho _0(x)dx=\int _0^1\int _{\mathbb{R}}\left (\frac{u_t(T_t^u(x))}{\rho ^u_t(T^u_t(x))}\right )^2dt\rho _0(x)dx\\[5pt] &=\int _0^1\int _{\mathbb{R}}\frac{u_t(y)^2}{\rho ^u_t(y)}dtdy=\mathrm{J}(u). \end{align*}
Then, we deduce that
$\inf \limits _{u\in{\mathcal U}} \mathrm{J}(u)\geq \min \limits _{Y \in{\mathcal Y}} J(\partial _t Y)$
. Furthermore, as every
$y\in \mathrm{arg}\,\min _{Y \in{\mathcal Y}} J(\partial _t Y)$
defines a flux
$u\in \mathcal{U}$
with
$\mathrm{J}(u)\leq J(\partial _t y)$
, in particular, we have
\begin{equation*}\min \limits _{u\in {\mathcal U}} \mathrm {J}(u)= \min \limits _{Y \in {\mathcal Y}} J(\partial _t Y).\end{equation*}
Using the equivalence of Problems 1 and 2, we can now prove the uniqueness of the minimizer.
Theorem 1.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 1, Problem 2 (and so Problem
1
) admits a unique solution.
Proof. Suppose that we have
$u^1$
and
$u^2$
, two solutions of
$\min \limits _{u\in{\mathcal U}} \mathrm{J}(u)$
. For
$\lambda\in (0,1)$
,
$t\in [0,1]$
and
$x\in \mathbb{R}$
, by convexity of the map
$\mathbb{R}\times \mathbb{R}_{\gt 0} \ni (a,b)\mapsto \frac{a^2}{b}$
, we have that
\begin{equation} \frac{(\lambda u^1_t(x)+(1-\lambda)u^2_t(x))^2}{\lambda\rho ^{u^1}_t(x)+(1-\lambda)\rho ^{u^2}_t(x)}\leq\lambda\frac{u^1_t(x)^2}{\rho ^{u^1}_t(x)}+(1-\lambda)\frac{u^2_t(x)^2}{\rho ^{u^2}_t(x)}. \end{equation}
As
$u^1$
and
$u^2$
are both solutions, we have that
\begin{equation*}\lambda\mathrm {J}(u^1)+(1-\lambda)\mathrm {J}(u^2)=\min _{u\in \mathcal {U}}\mathrm {J}(u)\leq \mathrm {J}(\lambda u^1+(1-\lambda) u^2),\end{equation*}
so (4.6) is an equality almost everywhere. To lighten the notation, let us write
$a_1=u^1_t(x)$
,
$b_1=\rho _t^1(x)$
,
$a_2=u^2_t(x)$
and
$b_2=\rho _t^2(x)$
. Then, when (4.6) is an equality, we have that the polynomial
\begin{equation*}P(\lambda)=(\lambda a_1+(1-\lambda)a_2)^2-(\lambda b_1+(1-\lambda)b_2)(\lambda\frac {a_1^2}{b_1}+(1-\lambda)\frac {a_2^2}{b_2})\end{equation*}
is identically zero. One can prove that the polynomial
$P$
is identically zero iff
$\frac{a_1}{b_1}=\frac{a_2}{b_2}$
i.e.,
$\frac{u^1_t(x)}{\rho ^{u^1}_t(x)}=\frac{u^2_t(x)}{\rho ^{u^2}_t(x)}$
. In this case, we then have
$\partial _t T_t^{u^1}(T_t^{u^1}(x))=\partial _t T_t^{u^2}(T_t^{u^2}(x))$
for
$T_t^{u^i}$
the optimal transport map from
$\rho _0$
to
$\rho ^{u^i}_t$
with
$i=1,2$
. Then, as
$T_0^{u^1}= T_0^{u^2}=\mathrm{Id}$
, we deduce that
$\rho ^{u^1}=\rho ^{u^2}$
so
$u^1=u^2$
almost everywhere.
5. Properties and structural form of the solution under smoothness assumption
We are now in a position to build explicitly the solution
$\mathrm{v}^\star$
of Problem 1 in the case when
$\rho _0$
and
$\rho _1$
have additional smoothness assumptions. In the process of building the solution, we also the establish structural properties of the solution. Throughout this section, we will assume that
$\rho _0$
and
$\rho _1$
satisfy the following set of assumptions.
Assumptions 2.
The probability measures
$\rho _0$
and
$\rho _1$
satisfy the following:
-
• They are absolutely continuous with respect to the Lebesgue measure with probability density functions that are continuous, have bounded convex support, and are bounded from below on their support.
-
•
$\sup \mathrm{Supp}\,(\rho _0)\lt x_0 \lt \mathrm{Supp}\,(\rho _1)$
.
Under the stated assumptions on
$\rho _0,\rho _1$
, by using the closed-form expression for the optimal transport map
$T$
in dimension one [Reference Villani21, Chapter 1], it is immediate to see that
$T$
is
$C^1$
. For
$\mathrm{v}\;:\;\mathrm{Supp}\,(\rho _0)\rightarrow \mathbb{R}$
such thatFootnote 4
$x\mapsto{toll}_{\mathrm{v}}(x)= \frac{x_0-x}{\mathrm{v}(x)}$
is decreasing and bounded between 0 and 1 on
$\mathrm{Supp}\,(\rho _0)$
, the expression
\begin{equation*}C_y(\mathrm {v}) = \limsup \limits _{\substack {\alpha _1 \rightarrow 0 \\ \alpha _2 \rightarrow 0}}\ \frac {1}{|\alpha _2-\alpha _1|} \int \unicode {x1D7D9}_{\{({toll}_{\mathrm {v}}(y)+\alpha _1)\mathrm {v}(x)\lt x_0-x \lt ({toll}_{\mathrm {v}}(y)+\alpha _2)\mathrm {v}(x)\}} \rho _0(x)dx\end{equation*}
gives the value of the flux passing through the toll station when the mass initially at
$y$
is crossing. Let us first prove that from the additional assumptions on
$\rho _0$
and
$\rho _1$
, we have that the solution is continuous.
Proposition 5.1.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 2, the solution
$\mathrm{v}^\star \in L^2$
admits a continuous representative.
Proof. From Section 1, we know that the solution
$\mathrm{v}^\star \in L^2$
admits a representative such that the function
$x\mapsto{toll}_{\mathrm{v}^\star }(x)= \frac{x_0-x}{\mathrm{v}^\star (x)}$
is decreasing. Now by absurd, suppose that
$\mathrm{v}^\star$
is not continuous on the interior of
$\mathrm{Supp}\,(\rho _0)$
. Then, there exists
$y$
in the interior of
$\mathrm{Supp}\,(\rho _0)$
and
$\epsilon \gt 0$
such that
$\forall \delta \gt 0$
,
$\exists y_\delta \in \mathrm{Supp}\,(\rho _0)$
with
$|y-y_\delta |\lt \delta$
and
$|\mathrm{v}^\star (y)-\mathrm{v}^\star (y_\delta )|\gt \epsilon$
. Suppose that
$\forall \delta \gt 0$
,
$y_\delta -y\gt 0$
(the proof would be the same for
$y_\delta -y\lt 0$
). As
${toll}_{\mathrm{v}^\star }(x)= \frac{x_0-x}{\mathrm{v}^\star (x)}$
is not continuous in
$y$
and it is decreasing, we have that
\begin{equation*} \lim \limits _{\substack {x \rightarrow y \\ x\gt y}}\ {toll}_{\mathrm {v}^\star }(x)\lt {toll}_{\mathrm {v}^\star }(y). \end{equation*}
Let us define
$\alpha =T(y)-y-\mathrm{v}^\star (y)$
. Suppose first that
$\alpha \gt 0$
, then as
${toll}_{\mathrm{v}^\star }$
is decreasing we have for
$x\leq y$
,
\begin{align*} \mathrm{v}^\star (x)& =({toll}_{\mathrm{v}^\star }(x))^{-1}(x_0-x)\leq ({toll}_{\mathrm{v}^\star }(y))^{-1}(x_0-x)=\frac{x_0-x}{x_0-y} ( T(y)-y-\alpha )\\[5pt] &= T(x)-x -\alpha \frac{x_0-x}{x_0-y} + \frac{x_0-x}{x_0-y} ( T(y)-y)-T(x)-x. \end{align*}
Then, as
$T$
is continuous, we have that
$-\alpha \frac{x_0-x}{x_0-y} + \frac{x_0-x}{x_0-y} ( T(y)-y)-T(x)-x$
tends to
$-\alpha$
when
$x$
tends to
$y$
. We deduce that for
$\gamma\gt 0$
small enough,
\begin{equation*}\mathrm {v}^\star (x)+\gamma(T(x)-x) \leq T(x)-x\end{equation*}
for all
$ x \in (y-\gamma,y]$
. Then by strict convexity of
$J$
, the function
\begin{equation*} \mathrm {v}_2(x)=\mathrm {v}^\star (x)+\gamma \unicode {x1D7D9}_{\{x \in (y-\gamma,y]\}}(T(x)-x-\mathrm {v}^\star (x)) \end{equation*}
verifies that
\begin{align*} &J(\mathrm{v}^\star )-J(\mathrm{v}_2)\\[5pt] & =\gamma \int _{y-\delta }^y \Big ( (\mathrm{v}^\star (x)-T(x)-x)(x_0-x) + \frac{(T(x)-x_0)^2}{1-\frac{x_0-x}{\mathrm{v}^\star (x)}}-\frac{(T(x)-x_0)^2}{1-\frac{x_0-x}{T(x)-x}}\Big ) \rho _0(x)dx\\[5pt] &=\gamma \int _{y-\delta }^y \Big ( \mathrm{v}^\star (x)(x_0-x) + \frac{(T(x)-x_0)^2}{1-\frac{x_0-x}{\mathrm{v}^\star (x)}}-(T(x)-x)^2\Big ) \rho _0(x)dx\\[5pt] &\gt 0, \end{align*}
as the path of constant speed
$t\mapsto x+t(x-T(x))$
has a smaller total squared velocity than the path
$t\mapsto x+t\big (\mathrm{v}^\star (x)\unicode{x1D7D9}_{\{t\leq{toll}_Y(x)\}}+\frac{T(x)-x_0}{1-\frac{x_0-x}{\mathrm{v}^\star (x)}}\unicode{x1D7D9}_{\{t\gt{toll}_Y(x)\}}\big )$
. Furthermore for
$\mathcal Y$
small enough, we have that
$C_x(\mathrm{v}_2)\lt h$
for all
$x\in (y-\gamma,y)$
, as
$\rho _0$
is continuous and
${toll}_{\mathrm{v}^\star }$
is decreasing so
$C_x(\mathrm{v}^\star )\lt C_{y_\delta }(\mathrm{v}^\star )$
for
$\delta$
small enough. Therefore, we have that
$\mathrm{v}_2$
is a better solution to the problem.
If now
$\alpha \leq 0$
, then by continuity of
$T$
we have that for
$\gamma\gt 0$
small enough,
$\mathrm{v}^\star (x)+2\gamma \geq T(x)-x$
, for all
$ x \in (y,y+\gamma]$
. As previously we can find a better solution
$\mathrm{v}_2(x)=\mathrm{v}^\star (x)-\gamma \unicode{x1D7D9}_{\{x \in (y-\gamma,y]\}}(T(x)-x-\mathrm{v}^\star (x))$
to the problem which contradicts the fact that
$\mathrm{v}^\star$
is the minimizer.
The next proposition states that at the points where
$\mathrm{v}^\star$
does not saturate the constraint,
$\mathrm{v}^\star$
is equal to the unconstrained transport
$T-\mathrm{Id}$
.
Proposition 5.2.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 2, if there exists
$y\in \mathrm{Supp}\,(\rho _0)$
such that
$C_y(\mathrm{v}^\star ) \lt h$
, then we have
$\mathrm{v}^\star (y)=T(y)-y$
.
Proof. Suppose
$\exists y \in \mathrm{Supp}\,(\rho _0)$
such that
$C_y(\mathrm{v}^\star ) \lt h$
and
$\mathrm{v}^\star (y)\neq T(y)-y$
. Define
$g_\epsilon (x)=\unicode{x1D7D9}_{\{x \in (y-\epsilon,y+\epsilon )\}}\epsilon ^3\exp ({-}\frac{1}{\epsilon ^2-(x-y)^2}+\frac{1}{\epsilon ^2})$
. Then, there exist
$\epsilon \neq 0 \in \mathbb{R}$
and
$\delta \gt 0$
such that
$\forall x \in (y-\delta,y+\delta )$
we have
$|\mathrm{v}^\star (x)+g_\epsilon (x)-(T(x)-x)|\lt |\mathrm{v}^\star (x)-(T(x)-x)|$
and
$C_x(\mathrm{v}^\star +g_\epsilon ) \lt h$
, since
$g_\epsilon$
introduces a vanishingly small bump at a suitable location. Through the flow of
$\mathrm{v}^\star +g_\epsilon$
, the points in
$(y-\delta,y+\delta )$
travel with a velocity that is closer to the velocity of the path
$t\mapsto x+t(T(x)-x)$
. The velocity of the path
$t\mapsto x+t(T(x)-x)$
being constant, it is the one that is minimal for the cost of the total squared velocity. By strict convexity of
$J$
, we have that
$J(\mathrm{v}^\star )\gt J(\mathrm{v}^\star +g_\epsilon )$
. This contradicts the optimality of
$\mathrm{v}^\star$
.
We can now deduce some regularity of the function
$\mathrm{v}^\star$
.
Corollary 5.3.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 2
, the optimal solution
$\mathrm{v}^\star$
of Problem
1
is
$C^1$
almost everywhere.
Proof. As
$T$
is
$C^1$
, then
$\mathrm{v}^\star$
is also
$C^1$
at points
$y$
that lie in the interior of the closed set
$\{y\in \mathrm{Supp}\,(\rho _0)\ |\ \mathrm{v}^\star (y)=T(y)-y\}$
. Otherwise if for some
$y$
it holds that
$\mathrm{v}^\star (y)\neq T(y)-y$
, then
$\exists \delta \gt 0$
such that
$\forall x \in (y-\delta,y+\delta )$
,
$\mathrm{v}^\star (x)\neq T(x)-x$
which implies by Proposition 5.2 that
$C_x(\mathrm{v}^\star ) = h$
. Solve the ordinary differential equation
\begin{equation} \left \{\begin{array}{ll} \partial _x\mathrm{v}(x)=\frac{\mathrm{v}(x)^2\rho _0(x)-h\mathrm{v}(x)}{h(x_0-x)} \quad \quad \text{ for } y-\delta \leq x\leq y+\delta \\[5pt] \mathrm{v}(y+\delta )=\mathrm{v}^\star (y+\delta ) \end{array}\right . \end{equation}
for
$\mathrm{v}(x)$
. Note that this equation is solved backwards, starting from a terminal condition at
$y+\delta$
.
It can be shown that the function
$\mathrm{v}$
is well defined by establishing existence and uniqueness of the solution to (5.1) using the Cauchy-Lipschitz theorem and inherent boundedness. Indeed, if
\begin{equation*} \mathrm {v}(x)\gt \frac {h} {\inf \{\rho _0(y)\mid y\in \mathrm {Supp}\,(\rho _0)\}}, \end{equation*}
then
$\partial _x \mathrm{v}(x)\gt 0$
, and so
$\mathrm{v}$
is decreasing with decreasing value of its argument on a small interval
$[x-\epsilon,x]$
, i.e.,
$\tau \mapsto \mathrm{v}(x-\tau )$
is decreasing for
$\tau \in [0,\epsilon ]$
. Likewise, if
\begin{equation*} 0\lt \mathrm {v}(x)\lt \frac {h}{\sup \{\rho _0(y)\mid y\in \mathrm {Supp}\,(\rho _0)\}}, \end{equation*}
then
$\partial _x \mathrm{v}(x)\lt 0$
, and so
$\mathrm{v}$
is increasing (again with decreasing value of its argument) on a small interval
$[x-\epsilon,x]$
. Therefore, we can conclude that if
$\mathrm{v}$
exists, it is bounded on its interval of definition. Now, as
$\mathrm{v}^\star (y+\delta )\gt 0$
, and
$\mathrm{v}\mapsto \frac{\mathrm{v}^2\rho _0(x)-h\mathrm{v}}{h(x_0-x)}$
is Lipschitz on any compact set, we can apply the Cauchy-Lipschitz theorem to establish existence and uniqueness. We then have that
$\mathrm{v}$
is well defined as the unique solution of (5.1) on
$[y-\delta,y+\delta ]$
and is
$C^1$
on this interval. From the definition of
$\mathrm{v}$
, it follows that
$C_x(\mathrm{v})=h$
, and therefore
$\mathrm{v}$
has the same flux as
$\mathrm{v}^\star$
. By uniqueness,
$\mathrm{v}$
which is
$C^1$
on
$[y-\delta,y+\delta ]$
is optimal, i.e.,
$\mathrm{v}=\mathrm{v}^*$
. Finally as
$\mathrm{v}^\star$
is
$C^1$
on the interior of the set
$\{y\in \mathrm{Supp}\,(\rho _0)\ |\ \mathrm{v}^\star (y)=T(y)-y\}$
and is also
$C^1$
on the set
$\{y\in \mathrm{Supp}\,(\rho _0)\ |\ \mathrm{v}^\star (y)\neq T(y)-y\}$
, we deduce that
$\mathrm{v}^\star$
is
$C^1$
almost everywhere as the boundary of those two sets is at most countable. Note that the set
$\{y\in \mathrm{Supp}\,(\rho _0)\ |\ \mathrm{v}^\star (y)=T(y)-y\}$
might have an empty interior. However, it does not change the fact that the set of points where
$\mathrm{v}^\star$
is not
$C^1$
lies in the boundary of the set
$\{y\in \mathrm{Supp}\,(\rho _0)\ |\ \mathrm{v}^\star (y)\neq T(y)-y\}$
. As the cardinality of the boundary of this set is at most countable, we can still conclude that
$\mathrm{v}^\star$
is
$C^1$
almost everywhere.
Now that we have established that
$\mathrm{v}^\star$
is
$C^1$
a.e., we can write the constraint (3.4) for functions
$\mathrm{v}\in C^1(\mathrm{Supp}\,(\rho _0),\mathbb{R})$
as: for
$x\in \mathrm{Supp}(\rho _0)$
, a.e.
\begin{equation} C_x(\mathrm{v})=\frac{\mathrm{v}(x)\rho _0(x)}{1+\frac{x_0-x}{\mathrm{v}(x)}\partial _x\mathrm{v}(x)}\leq h. \end{equation}
We now define the class of candidate functions that we focus on in the present section.
Definition 5.4.
The class of functions
$V$
is defined as the set of maps
$\mathrm{v}\;:\;\mathrm{Supp}\,(\rho _0)\rightarrow \mathbb{R}$
, that are
$C^1$
a.e. and are such that
-
(i) the map
$x\mapsto \frac{x_0-x}{\mathrm{v}(x)}$
is decreasing and bounded between 0 and 1
-
(ii)
$\mathrm{v}$
verifies condition (5.2) a.e.
Note that from Corollary 5.3, we have that
$V$
is non-empty. For
$\mathrm{v}\;:\;\mathrm{Supp}\,(\rho _0)\rightarrow \mathbb{R}$
, define
\begin{equation*} J(\mathrm {v})=\int _{\mathbb {R}} \Big ( \mathrm {v}(x)(x_0-x) + \frac {(T(x)-x_0)^2}{1-\frac {x_0-x}{\mathrm {v}(x)}}\Big ) \rho _0(x)dx. \end{equation*}
We can then rewrite Problem 1 in the present case where
$\rho _0$
and
$\rho _1$
are continuous, have bounded convex support, and are bounded from below on the interior of their support, as follows.
Problem 3. Consider
\begin{equation} \min \limits _{\mathrm{v}\in V} J(\mathrm{v}) \end{equation}
over the class of functions
$V$
of Definition 5.4
. Determine existence, uniqueness, and a functional form for a minimizing solution
$\mathrm{v}$
.
To solve Problem 3, we define velocity fields
$\mathrm{v}$
on all of
$\mathbb{R}$
, even outside
$\mathrm{Supp}\,(\rho _0)$
, as this suitably defined extension of
$\mathrm{v}$
will be conveniently expressed as a solution of a differential equation. To this end, we note that the constraint (5.2) can be alternatively expressed in the form
\begin{equation} C_x^{\mathrm{alt}}({\mathrm{v}})\;:\!=\;\frac{\mathrm{v}(x)^2\rho _0(x)-h(x_0-x)\partial _x\mathrm{v}(x)}{\mathrm{v}(x)}\leq h. \end{equation}
This alternative formulation applies even for points
$x$
where
$\rho _0=0$
and will help define the sought extension for
$\mathrm{v}^\star$
.
Let us first extend on all of
$\mathbb{R}$
the optimal transport map between
$\rho _0$
and
$\rho _1$
. To this end, define
$\alpha _0= \inf \mathrm{Supp}\,(\rho _0),\beta _0= \sup \mathrm{Supp}\,(\rho _0)$
,
$\alpha _1= \inf \mathrm{Supp}\,(\rho _1),\beta _1= \sup \mathrm{Supp}\,(\rho _1)$
, and set
\begin{equation*} T^{\mathrm {+}}(x)=\left \{ \begin {array}{ll} T(x) & \mbox { when }x\in \mathrm{Supp}\,(\rho _0)\\[5pt] \beta _1 + x - \beta _0 & \mbox { when }x\geq \beta _0\\[5pt] \alpha _1 + x - \alpha _0 & \mbox { when }x \leq \alpha _0. \end {array}\right . \end{equation*}
Let
$\gamma_0,\gamma_1 \in \mathbb{R}$
be the uniquely defined points such that
$\frac{x_0-\alpha _0}{\mathrm{v}^\star (\alpha _0)}=\frac{x_0-\gamma_0}{T^+(\gamma_0)-\gamma_0}$
and
$\frac{x_0-\beta _0}{\mathrm{v}^\star (\beta _0)}=\frac{x_0-\gamma_1}{T^+(\gamma_1)-\gamma_1}$
. The point
$\gamma_1$
is the point that, when transported by
$T-\mathrm{Id}$
, crosses the toll at the same time and
$\beta _0$
crosses the toll when being transported by
$\mathrm{v}^\star$
. Note that we have
$\gamma_0\leq \alpha _0$
and
$\gamma_1\geq \beta _0$
. We also extend
$\mathrm{v}^\star$
on the whole
$\mathbb{R}$
as
\begin{equation*} \mathrm {v}^{\star +}(x)=\left \{ \begin {array}{ll} T(x)-x & \mbox { when }x\leq \gamma_0 \mbox { or } x\geq \beta _0\\[5pt] \mathrm {v}^\star (\alpha _0)\frac {x_0-x}{x_0-\alpha _0} & \mbox { when }\gamma_0\leq x \leq \alpha _0 \\[5pt] \mathrm {v}^\star (x) & \mbox { when }x \in \mathrm{Supp}\,(\rho _0)\\[5pt] \mathrm {v}^\star (\beta _0)\frac {x_0-x}{x_0-\beta _0} & \mbox { when }\beta _0\leq x \leq \gamma_1 \end {array}\right . \end{equation*}
For notational simplicity, in the sequel, we suppress the labelling on
$T^+$
,
$\mathrm{v}^{\star +}$
and use
$T$
,
$\mathrm{v}^\star$
instead for the extended versions as well. To build
$\mathrm{v}^\star$
, we first establish that on the points where
$T-\mathrm{Id}$
does not satisfy the constraint,
$\mathrm{v}^\star$
actually saturates the constraint. As an immediate consequence of Proposition 5.2, we have the following lemma:
Lemma 5.5.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 2, for all
$x\in \mathrm{Supp}\,(\rho _0)$
such that
$C_x(T-\mathrm{Id})\gt h$
we have
$C_x(\mathrm{v}^\star )= h$
.
We next characterize a leading segment of the distribution corresponding to points with velocity faster than that of the optimal unconstrained transport. It is essential that the leading edge ‘speeds up’ to allow the trailing portion to pass through and meet the time constraint. Specifically, we show that
$\mathrm{v}^\star$
is greater than
$T-\mathrm{Id}$
at the points to the right of points where
$T-\mathrm{Id}$
does not satisfy the constraint.
Lemma 5.6.
For
$\rho _0$
and
$\rho _1$
satisfying Assumptions 2, for
$x_1=\sup \{x\in \mathrm{Supp}\,(\rho _0)\ | \ C_x(T-\mathrm{Id})\gt h\}$
and
$y_1=\sup \{x \in \mathbb{R}\ | \ C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h\}$
we have that
$\forall x \in (x_1,y_1)$
,
$\mathrm{v}^\star (x)\geq T(x)-x$
.
Proof. First note that
$y_1\geq x_1$
by Lemma 5.5. Suppose that
\begin{equation*} \{\mathrm {v}^\star (x)\lt T(x)-x\}\cap (x_1,y_1)\neq \emptyset \end{equation*}
and let
$a=\sup \{x \in (x_1,y_1) \ | \ \mathrm{v}^\star (x)\lt T(x)-x\}$
. We consider separately the two cases
$\rho _0(a)=0$
and
$\rho _0(a)\gt 0$
below:
(i) If
$\rho _0(a)=0$
then
$\forall x\geq a,\ \rho _0(x)=0$
, so
\begin{equation*} \mathrm {v}^\star (x) = \frac {T(y_1)-y_1}{y_1-x_0}(x-x_0), \end{equation*}
as
$C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h$
for all x
$\in [a,y_1]$
. Furthermore,
$T(a)-a=\beta _1+a-\beta _0-a=T(y_1)-y_1$
and
$T(a)-a=\mathrm{v}^\star (a)$
so necessarily
$a=y_1$
and
$\mathrm{Supp}\,(\rho _0)=[\alpha _0,y_1]$
. Then,
$\exists z\in (x_1,y_1)$
such that,
$\rho _0(z)\gt 0$
,
$\mathrm{v}^\star (z)\lt T(z)-z$
, and
$\partial _x\mathrm{v}^{\star }(z)\gt T^\prime (z)-1$
.
(ii) If
$\rho _0(a)\gt 0$
, then by convexity of
$\mathrm{Supp}\,(\rho _0)$
we also have existence of that
$z\in (x_1,y_1)$
with the same properties. In both cases, we have
\begin{equation*} \frac {\mathrm {v}^\star (z)\rho _0(z)}{1+\frac {x_0-z}{\mathrm {v}^\star (z)}\partial _x\mathrm {v}^{\star }(z)}\lt \frac {(T(z)-z)\rho _0(z)}{1+\frac {x_0-z}{T(z)-z}(T^\prime (z)-1)} \leq h \end{equation*}
which contradicts the definition of
$y_1$
.
The following lemma states that if
$\mathrm{v}^\star$
saturates the constraint on a maximal interval (i.e., such that, the points just outside do not saturate the constraint), then either
$\mathrm{v}^\star =T-\mathrm{Id}$
throughout, or it is strictly greater than
$T-\mathrm{Id}$
on a portion of the interval and strictly less than
$T-\mathrm{Id}$
on another portion of the interval. This property is inherited by the convexity of the cost.
Lemma 5.7.
Suppose that
$\rho _0$
and
$\rho _1$
satisfy Assumptions 2 and let be
$[a,b] \subset \{x \in \mathbb{R}\ | \ C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h\}$
with
$[a,b]$
of maximal size. Then,
$[a,b]$
has the following properties:
-
• There exists
$x\in [a,b]$
such that
$\mathrm{v}^\star (x)\gt T(x)-x$
if and only if
$\exists y\in [a,b]$
such that
$\mathrm{v}^\star (y)\lt T(y)-y$
. -
• If for all
$\delta \gt 0$
, there exists
$y_1\in (a,a+\delta )$
such that
$\mathrm{v}^\star (y_1)\gt T(y_1)-y_1$
then for all
$\delta \gt 0$
, there also exists
$y_2\in (a,a+\delta )$
such that
$\mathrm{v}^\star (y_2)\lt T(y_2)-y_2$
. -
• If for all
$\delta \gt 0$
, there exists
$y_1\in (b-\delta,b)$
such that
$\mathrm{v}^\star (y_1)\lt T(y_1)-y_1$
then for all
$\delta \gt 0$
, there also exists
$y_2\in (b-\delta,b)$
such that
$ \mathrm{v}^\star (y_2)\gt T(y_2)-y_2$
.
Proof. Suppose that
$\forall x\in [a,b]$
, we have
$\mathrm{v}^\star (x)\geq T(x)-x$
and we do not have equality on the whole interval. Define
\begin{equation*}\Psi _a(\epsilon ) = \int _a^b \big ((x_0-x)(\mathrm {v}^\star (x)+\epsilon )+\frac {(T(x)-x_0)^2}{1-\frac {x_0-x}{\mathrm {v}^\star (x)+\epsilon }}\big )\rho _0(x)dx.\end{equation*}
Then, we have
$\partial _x\Psi _a(0) = \int _a^b (x_0-x)(1-\frac{(T(x)-x_0)^2}{(\mathrm{v}^\star (x)-(x_0-x))^2}\big )\rho _0(x)dx\gt 0.$
Let be
$c\lt a$
such that
$\partial _x\Psi _c(0)\gt 0$
and
$\exists \delta \gt 0$
with
$\frac{\mathrm{v}^\star (c)^2\rho _0(c)-h\mathrm{v}^\star (c)}{h(x_0-c)}-\partial _x\mathrm{v}^{\star }(c) = -\delta$
. Then, there exist
$d\in (c,a)$
such that
$\partial _x\Psi _d(0)\gt 0$
and
$\exists \delta \gt 0$
with
$\frac{\mathrm{v}^\star (d)^2\rho _0(d)-h\mathrm{v}^\star (d)}{h(x_0-d)}-\partial _x\mathrm{v}^{\star }(d) = -\delta/2$
. Let us define
$k_\epsilon$
as the function solving the ODE
\begin{equation*}\left \{\begin {array}{ll} \partial _xk_\epsilon (x) = -\partial _x\mathrm {v}^{\star }(x) + \frac {(\mathrm {v}^\star (x)+k_\epsilon )^2\rho _0(x)-h(\mathrm {v}^\star (x)+k_\epsilon (x))}{h(x_0-x)} \quad \quad \text { for } x\leq d,\\[5pt] k_\epsilon (d)=-\epsilon . \end {array}\right .\end{equation*}
Then for
$\epsilon \gt 0$
small enough, we have
$\partial _xk_\epsilon (x)\lt -\delta/4$
,
$\forall x\in (c,d)$
. Therefore, for
$\epsilon \gt 0$
small enough
$\exists y \in (c,d)$
such that
$k_\epsilon (y)=0$
. Define
\begin{equation*} \mathrm {v}_\epsilon (x) = \left \{ \begin {array}{ll} \mathrm {v}^\star (x) & \text {if } x\notin (y,b), \\[5pt] \mathrm {v}^\star (x)-\epsilon & \text {if } x\in (d,b), \\[5pt] \mathrm {v}^\star (x)+k_\epsilon (x) & \text {if } x\in (y,d]. \end {array} \right . \end{equation*}
Then for
$\epsilon \gt 0$
small enough,
$\mathrm{v}_\epsilon$
verifies the constraint and
$J(\mathrm{v}_\epsilon )\lt J(\mathrm{v}^\star )$
.
Furthermore, recalling that the speed of a particle at
$x\in \mathrm{Supp}\,(\rho _0)$
after having crossed the toll is
$\frac{T(x)-x_0}{1-\frac{x_0-x}{\mathrm{v}^\star (x)}}$
, then for
$\overline{v}^\star \;:\;\mathrm{Supp}\,(\rho _1)\rightarrow \mathbb{R}_{\lt 0}$
defined by
\begin{equation*} \overline {v}^\star (y)=\frac {x_0-y}{1-\frac {x_0-T^{-1}(y)}{\mathrm {v}^\star (T^{-1}(y))}}, \end{equation*}
we have that
$\overline{v}^\star$
is a solution to the problem of transfering between
$\rho _1$
and
$\rho _0$
. Therefore, applying the previous derivations to
$\overline{v}^\star$
, we deduce that for
$[T(a),T(b)] \subset \{x \in \mathbb{R}\ | \ C_x^{\mathrm{alt}}({\overline{v}^\star })= h\}$
with
$[T(a),T(b)]$
of maximal size, if there exists
$y_1\in [T(a),T(b)]$
with
$\overline{v}^\star (y_1)\lt T^{-1}(y_1)-y_1$
, then there exists
$y_2\in [T(a),T(b)]$
with
$\overline{v}^\star (x)\gt T^{-1}(y_2)-y_2$
. Now as we have the relation
$\mathrm{v}^\star (x)\lt T(x)-x$
iff
$\overline{v}^\star (T(x))\lt -(T(x)-x)$
, we deduce that if there exists
$x_1\in [a,b]$
such that
$\mathrm{v}^\star (x_1)\lt T(x_1)-y_1$
then there exists
$x_2\in [a,b]$
such that
$\mathrm{v}^\star (x_2)\lt T(x_2)-y_2$
.
Let us now prove the second and third point. Suppose that there exists
$\delta \gt 0$
and
$y_1\in (a,a+\delta )$
such that
$\mathrm{v}^\star (y_1)\gt T(y_1)-y_1$
and
$\forall x \in (a,a+\delta )$
, we have
$\mathrm{v}^\star (x)\geq T(x)-x$
. Then defining
\begin{equation*}\Psi _a(\epsilon ) = \int _a^{a+\delta } \big ((x_0-x)(\mathrm {v}^\star (x)+\epsilon )+\frac {(T(x)-x_0)^2}{1-\frac {x_0-x}{\mathrm {v}^\star (x)+\epsilon }}\big )\rho _0(x)dx,\end{equation*}
and carrying out the same derivation as previously we obtain that
$\mathrm{v}^\star$
is not optimal. Now applying the same reasoning to
$\overline{v}^\star$
, we obtain the third point.
We are now in a position to build explicitly
$\mathrm{v}^\star$
using the lemmas. The process of building
$\mathrm{v}^*$
consists of determining its value successively on intervals
$[z_{y_i},y_i]$
and
$[y_{i+1},z_{y_i}]$
, with
\begin{equation*} \ldots \gt y_i\gt z_{y_i} \gt y_{i+1}\gt z_{y_{i+1}}\gt \ldots \end{equation*}
such that
$\mathrm{v}^\star (x)\neq T(x)-x$
for
$x \in [z_{y_i},y_i]$
a.e., while
$\mathrm{v}^\star (x) = T(x) -x$
on the complement where
$x \notin \bigcup \limits _i [z_{y_i},y_i]$
. By Proposition 5.2, we know that
$C_x^{\mathrm{alt}}({\mathrm{v}^\star })=h$
on intervals
$[z_{y_i},y_i]$
, a fact that will help us determine
$\mathrm{v}^\star$
and the succession of points that define these intervals.
Figure 2. Density
$\rho _{0}(x)$
vs.
$x$
.
Figure 3. Flux
$\rho _{t}(x_0)v_{t}(x_0)$
at crossing.
We explain the process in Figures 2-4 with an example. This example presents a situation where the behaviour of the corresponding optimal solution
$\mathrm{v}^\star$
is characterized by two distinct intervals
$[z_{y_i},y_i]$
$i=1,2$
, where the constraint saturates. Thus, for this example, we identify three intervals of interest,
$[z_{y_2},y_2]$
,
$[y_2,z_{y_1}]$
, and
$[z_{y_1},y_1]$
. In the first and the last, the constraint saturates, whereas in the middle interval it does not. We proceed by working our way from right to left, always assuming that
$\mathrm{Supp}\,(\rho _0)$
is to the left of the toll, as in the figures.
In general, the process begins by first computing the optimal transport map
$T$
, without involving the constraint. Then, we identify
$x_1$
as the rightmost point where the throughput hits the limit set at
$x_0$
. Naturally, if the optimal transport map satisfies the throughput constraint, then it is the optimal map and specifies
$\mathrm{v}^*$
throughout. Assuming that
$x_1$
is finite, then a search to the right of
$x_1$
, that we explain later on, identifies
$y_1$
as the rightmost point where
$\mathrm{v}$
needs to be adjusted so as to abide by the throughput constraint while minimizing the transportation cost. In the example depicted in Figure 2,
$y_1$
is shown located to the right of
$\beta _0$
(
$=$
the supremum of the support of
$\rho _0$
), though this is not always the case, and depends on the terminal distribution
$\rho _1$
via the optimization problem that specifies
$y_1$
. We choose to explain this case, where
$y_1$
is to the right of
$\beta _0$
so as to highlight that this is indeed possible.
Figure 4. Illustration of the flow through the toll. The middle segment
$[y_2,z_{y_1}]$
transports through the toll unimpeded by the constraint towards the final destination, via the optimal transport map
$T$
, designed for unconstrained transport; each point in this interval maintains the same velocity before and after the toll. In contrast, the segments to the left and right,
$[z_{y_2},y_2]$
and
$[z_{y_1},y_1]$
, respectively, are adjusted accordingly so as to saturate the constraint. The exact position of their respective end points (that may even be outside the support of
$\rho _0$
, as a matter of computational simplicity, in which case they correspond to zero density) is computed via the solution of an optimization problem and depend on the terminal distribution
$\rho _1$
as well.
Continuing on with our specific example, for the interval
$[z_{y_1},y_1]$
, we have
$\mathrm{v}^\star =\mathrm{v}_{y_1}$
, with
$\mathrm{v}_y$
defined in equation (5.6) explained below, which ensures that
$C_x^{\mathrm{alt}}({\mathrm{v}})=h$
. Then, on
$[y_2,z_{y_1}]$
we have once again that the velocity is specified by the ‘unconstrained’ optimal map
$T$
, i.e, that
$\mathrm{v}^\star =T-\mathrm{Id}$
, and so
$C_x^{\mathrm{alt}}({\mathrm{v}})=C_x^{\mathrm{alt}}({T-\mathrm{Id}})$
. Finally on
$[z_{y_2},y_2]$
, we have
$\mathrm{v}^\star =\mathrm{v}_{y_2}$
as
$C_x^{\mathrm{alt}}({\mathrm{v}})=h$
. Note that in this specific example where
$y_1\geq \beta _0$
and
$z_{y_2}\leq \alpha _0$
, we have
$\forall x \in [z_{y_2},\alpha _0]$
,
$toll(x)=toll(\alpha _0)$
and
$\forall x \in [\beta _0,y_1]$
,
$toll(x)=toll(\beta _0)$
.
We now detail how to build explicitly
$\mathrm{v}^\star$
in the general case. As noted, if
$T-\mathrm{Id}$
verifies the constraint throughout, which can now be explicitly stated as in (5.2), then
$\mathrm{v}^*=T-\mathrm{Id}$
is the optimal solution. Otherwise define
$x_1=\sup \{x\in \mathrm{Supp}\,(\rho _0)\ | \ C_x(T-\mathrm{Id})\gt h\}$
, and thereby we determine
$y_1\in [x_1,x_0]$
(cf. Lemma 5.5) such that
\begin{equation} y_1=\sup \{x \in \mathbb{R}\ | \ C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h\}. \end{equation}
For any
$y\in \mathbb{R}$
with
$ x_1\leq y \lt x_0$
, define the velocity
$\mathrm{v}_y(x)$
as the solution of the differential equation
\begin{equation} \left \{\begin{array}{ll} \partial _x\mathrm{v}_y(x)=\frac{\mathrm{v}_y(x)^2\rho _0(x)-h\mathrm{v}_y(x)}{h(x_0-x)} \quad \quad \text{ for } x\leq y.\\[5pt] \mathrm{v}_y(y)=T(y)-y \end{array}\right . \end{equation}
Note that this equation is solved backwards, starting from a terminal condition at
$y$
. This value for the velocity ensures that the transport will saturate the constraint to left of
$y$
(i.e.,
$C_x^{\mathrm{alt}}({\mathrm{v}_y})= h$
will hold for
$x\leq y$
). The functional form of
$\mathrm{v}_y(x)$
will be used next to identify the first interval
$[z_{y_1},y_1]$
, where the velocity will depart from that of the unconstrained transport
$T$
, via solving a suitable optimization problem to determine
$y_1$
. Since we know that the equality
$C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h$
will be true on a certain interval
$[z_{y_1},y_1]$
, on that interval we will have
$\mathrm{v}^\star =v_{y_1}$
.
Let
$w_y^{x_1}=\inf \{x\leq x_1 \mid \forall s\in (x,x_1), \mathrm{v}_{y}(s)\geq T(s)-s\}$
(well defined by Lemma 5.6) and
\begin{equation} z_y^{x_1}= \inf \{x\leq w_y^{x_1}\ | \ \forall s\in (x,w_y^{x_1}), \ \mathrm{v}_{y}(s)\lt T(s)-s\}. \end{equation}
Then, we have that
$\mathrm{v}^\star (x)=\mathrm{v}_{y_1}(x)$
,
$\forall x \in (z_{y_1}^{x_1},x_1)$
by Lemma 5.7 and Proposition 5.2.
We now determine
$y_1$
by solving a suitable optimization problem. For
$x\leq y \lt x_0$
, define
\begin{align*} J_x(y) &= \int _{\mathbb{R}} \Big ((T(s)-s)^2 \unicode{x1D7D9}\{s\notin (z_y^{x},y)\}\\[5pt] & +((x_0-s)\mathrm{v}_{y}(s)+\frac{(T(s)-x_0)^2}{1-\frac{x_0-s}{\mathrm{v}_{y}(s)}})\unicode{x1D7D9}\{s\in (z_y^{x},y)\}\Big )\rho _0(s)ds. \end{align*}
We have
$J_x(y)=J(\mathrm{v}_y^{+})$
for the function
$\mathrm{v}_y^{+}$
such that
$\mathrm{v}_y^{+}=\mathrm{v}_y$
on
$[z_y^x,y]$
and
$\mathrm{v}_y^{+}=T-\mathrm{Id}$
on
$\mathbb{R}\setminus [z_y^x,y]$
. Then, the first step of the building process of
$\mathrm{v}^\star$
is to find
$y_1$
solution of
\begin{equation*} y_1= \mathop {\mathrm{arg\,min}} \limits _{y\geq x_1} J_{x_1}(y). \end{equation*}
Such a
$y_1$
is well defined as
$J_{x_1}$
is continuous on
$[x_1,x_0]$
. Once
$y_1$
has been determined, we define
$x_2=\sup \{x\lt z_{y_1} \ | \ C_x(T-\mathrm{Id})\gt h\}$
. If
$x_2$
is not defined then
\begin{equation*} \mathrm {v}^\star (x) = \left \{ \begin {array}{ll} \mathrm {v}_{y_1}(x) & \text {if } x\in (z_1,y_1), \\[5pt] T(x)-x & \text {if } x\notin (z_1,y_1), \end {array} \right . \end{equation*}
otherwise we start again the same process to determine
$y_2$
as
\begin{align*} y_2= \mathop{\mathrm{arg\, min}} \limits _{y\gt x_2} J_{x_2}(y). \end{align*}
If
$y_2\lt z_{y_1}$
, it suggests that there is an interval
$[y_2,z_{y_1}]$
where the transport follows the unconstrained map
$T$
, and we continue in the same way.
However, it is possible that the condition
$y_i\leq z_{y_{i-1}}$
fails at some point, for some
$i\geq 2$
. In that case, intervals where the velocity departs from being
$T(x)-x$
, will merge. For instance, if we obtain
$y_i\gt z_{y_{i-1}}$
then as
$(y,y^\prime )\mapsto J_{x_{i-1}}(y) + J_{x_{i}}(y^\prime )$
is convex on
$\{(y,y^\prime )\ | \ y^\prime \leq z_y\}$
, it means that
$C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h$
,
$\forall x \in (x_i,x_{i-1})$
, and therefore, we have to start the optimization again and determine
$y_{i-1}$
as
\begin{align*} y_{i-1}= \mathop{\mathrm{arg\, min}} \limits _{y\gt x_{i-1}} J_{x_i}(y). \end{align*}
If we obtain a value
$y_{i-1}\gt z_{y_{i-2}}$
, we reset
$x_{i-1}$
as being equal to
$x_i$
and, once again, we have to redetermine
\begin{equation*} y_{i-2}= \mathop {\mathrm{arg\, min}} \limits _{y\gt x_{i-2}} J_{x_{i-1}}(y). \end{equation*}
Otherwise, i.e., if we obtain a value
$y_{i-1}\leq z_{y_{i-2}}$
, we reset
$x_i$
as
$x_i=\sup \{x\lt z_{y_{i-1}} \ | \ C_x(T-\mathrm{Id})\gt h\}$
for this updated value
$y_{i-1}$
. Once again, if
$x_i$
is well defined we continue the process by finding
\begin{equation*} y_i= \mathop {\mathrm{arg\, min}} \limits _{y\gt x_i} J_{x_i}(y). \end{equation*}
We continue this iterative process until
$\mathrm{v}^\star$
is defined on all of the support of
$\rho _0$
. The construction process is summarized in Algorithm 1.
Algorithm 1. Building Process
To establish the correctness of this algorithm in constructing the solution
$\mathrm{v}^\star$
, we start with a key property of the function
$J_x$
Proposition 5.8.
Let be
$y\in \mathrm{Supp}\,(\rho _0)$
and
$x=\sup \{z\leq y| C_z(T-\mathrm{Id})\gt h\}$
. There exists
$y^\star \in [x,x_0]$
such that the function
$y\mapsto J_x(y)$
is non-increasing on
$[x,y^\star ]$
and then non-decreasing on
$[y^\star,x_0]$
. Furthermore, if
$C_z(T-Id)\lt h$
then
$\forall \epsilon \gt 0$
,
$y\mapsto J_x(y)$
is not constant on
$[z-\epsilon,z+\epsilon ]$
.
Proof. Let
$\mathrm{v}_y$
be the solution of (5.6) and its associated toll function
${toll}_y(x)=(x_0-x)/\mathrm{v}_y(x)$
. We have
\begin{align*} \partial _x{toll}_y(x)&=-\frac{1}{\mathrm{v}_y(x)}-\frac{x_0-x}{\mathrm{v}_y(x)^2}\partial _x \mathrm{v}_y=-\frac{1}{\mathrm{v}_y(x)}-\frac{1}{h}(\rho _0(x)-\frac{h}{\mathrm{v}_y(x)})=-\frac{\rho _0(x)}{h}, \end{align*}
so in particular for
$x\leq y$
we have
\begin{equation*}{toll}_y(x)={toll}(y)+\rho _0([x,y])/h,\end{equation*}
with
${toll}(y)=(x_0-y)/(T(y)-y).$
Then as
$\mathrm{v}_y(x)=(x_0-x)/{toll}_y(x)$
, we can rewrite
$J_x$
as
\begin{align*} J_x(y) &= \int _{\mathbb{R}} \Big ((T(s)-s)^2 \unicode{x1D7D9}\{s\notin (z_y^{x},y)\}\\[5pt] &\qquad +(\frac{(x_0-s)^2}{{toll}(y)+\rho _0([s,y])/h}+\frac{(T(s)-x_0)^2}{1-{toll}(y)-\rho _0([s,y])/h})\unicode{x1D7D9}\{s\in (z_y^{x},y)\}\Big )\rho _0(s)ds.\\[5pt] & = \int _{\mathbb{R}} \Big ((T(s)-s)^2 \unicode{x1D7D9}\{s\notin (z_y^{x},y)\}+(f_1(s,y)+f_2(s,y))\unicode{x1D7D9}\{s\in (z_y^{x},y)\}\Big )\rho _0(s)ds, \end{align*}
with
\begin{equation*}f_1(s,y)=\frac {(x_0-s)^2}{{toll}(y)+\rho _0([s,y])/h} \text { and } f_2(s,y)=\frac {(T(s)-x_0)^2}{1-{toll}(y)-\rho _0([s,y])/h}.\end{equation*}
Now as
$f_1(z_y^x,y)+f_2(z_y^x,y)=(T(z_y^x)-z_y^x)^2$
and
$f_1(y,y)+f_2(y,y)=(T(y)-y)^2$
, we deduce that
\begin{align*} \partial _y J_x(y) &= \int _{\mathbb{R}} \Big (\partial _y f_1(s,y)+\partial _y f_2(s,y)\}\Big )\unicode{x1D7D9}\{s\in (z_y^{x},y)\}\rho _0(s)ds\\[5pt] & = -\int _{\mathbb{R}} \Big (\left (\frac{(x_0-s)}{{toll}(y)+\rho _0([s,y])/h}\right )^2({toll}^{\prime}(y)+\rho _0(y)/h)\\[5pt] &\qquad -\left (\frac{(T(s)-x_0)}{1-{toll}(y)-\rho _0([s,y])/h}\right )^2({toll}^{\prime}(y)+\rho _0(y)/h)\Big )\unicode{x1D7D9}\{s\in (z_y^{x},y)\}\rho _0(s)ds\\[5pt] &=\int _{\mathbb{R}} \left (\left (\frac{(T(s)-x_0)}{1-{toll}(y)-\rho _0([s,y])/h}\right )^2-\left (\frac{(x_0-s)}{{toll}(y)+\rho _0([s,y])/h}\right )^2\right )\\[5pt] &\qquad \times ({toll}^{\prime}(y)+\rho _0(y)/h)\unicode{x1D7D9}\{s\in (z_y^{x},y)\}\rho _0(s)ds. \end{align*}
Furthermore, for
$s\leq y$
, the function
$y\mapsto{toll}(y)+\rho _0([s,y])/h={toll}_y(s)$
is non-increasing as all the points
$x\in (s,y)$
verify that
$C_x(\mathrm{v}_y)=h$
i.e., the flow rate is maximized between
$s$
and
$y$
. We can then conclude that
${toll}^{\prime}(y)+\rho _0(y)/h\leq 0$
and that the function
\begin{equation*}y\mapsto \left (\frac {(T(s)-x_0)}{1-{toll}(y)-\rho _0([s,y])/h}\right )^2-\left (\frac {(x_0-s)}{{toll}(y)+\rho _0([s,y])/h}\right )^2\end{equation*}
is non-negative and then non-positive, which gives the result.
Now if for
$z\geq x$
,
$C_z(T-\mathrm{Id})\lt h$
, then
${toll}^{\prime}(z)+\rho _0(z)/h\lt 0$
so
$J_x(y)$
is not constant around
$z$
.
Let now
\begin{equation} n=\sup \limits _{(x_i)_i} \sum _{i=1}^\infty \unicode{x1D7D9}_{\{C_{x_i}(T-Id)\gt h,C_{x_{i+1}}(T-id)\lt h\}}, \end{equation}
where the supremum is taken over all increasing sequence
$(x_i)_i\in \mathrm{Supp}\,(\rho _0)^{\mathbb{N}}$
. It corresponds to the number of times the function
$x\mapsto C_x(T-\mathrm{Id})$
oscillates around the value
$h$
. We are going to prove that the problem is reduced to finding the intervals where
$C_x(\mathrm{v}^\star )=h$
. To this end, let us define a class of candidate minimizers that are characterized by the intervals where they saturate the constraint.
Definition 5.9.
For
$N\in \mathbb{N}$
, the class of functions
$V_N$
is defined as the set of maps
$\mathrm{v}^{(z_i,y_i)_i}\;:\;\mathrm{Supp}\,(\rho _0)\rightarrow \mathbb{R}$
such that
-
i) there exists a sequence of disjoints intervals
$(z_i,y_i)\subset \mathrm{Supp}\,(\rho _0)$
$i=1,\ldots,N$
with
\begin{equation*}\mathrm {v}^{(z_i,y_i)_i}(x)=\sum _i \unicode {x1D7D9}\{x\in (z_i,y_i)\}v_{y_i}(x)+\unicode {x1D7D9}\{x\notin \bigcup _i (z_i,y_i)\}(T(x)-x),\end{equation*}
-
ii) for all
$x\notin \bigcup _i (z_i,y_i)$
, we have
$C_x(T-Id)\leq h$
, -
iii) for all
$i\in \{1,\ldots,N\}$
there exists
$x\in (z_i,y_i)$
such that
$C_{x}(T-\mathrm{Id})\gt h$
.
Let us prove that the solution
$v^\star$
belongs to a certain class
$V_N$
for
$N\leq n+1$
.
Lemma 5.10.
Suppose that
$\rho _0$
and
$\rho _1$
satisfy Assumptions 2 and that n defined in (5.8) is finite. There exists
$N\ \in \{0,\ldots,n+1\}$
such that Problem 3 is equivalent to
$\inf _{v\in V_N} J(v)$
and the infimum is attained.
Proof. First note that we have that
$\inf _{v\in V_N} J(v)\geq \min \limits _{\mathrm{v}\in V} J(\mathrm{v})$
as every candidate in
$V_N$
defines a candidate in
$V$
. Let be
\begin{equation*}E=\{x\in \mathrm {Supp}\,(\rho _0)|\ C_x(T-Id)\gt h\}.\end{equation*}
Then as
$E$
is open, it can be written as a union of disjoint intervals :
$E=\bigcup _{k\geq 1}(a_k,b_k).$
For all
$k\geq 1$
, let be
\begin{equation*}c_k=\sup \{x\leq a_k|\ C_x(T-Id)\lt h\} \text { and }d_k=\inf \{x\geq b_k|\ C_x(T-Id)\lt h\}. \end{equation*}
Then, the set
\begin{equation*}A= \bigcup _{k\geq 1}(c_k,d_k),\end{equation*}
can actually be written as a finite union:
\begin{equation*}A=\bigcup _{k=1}^{m}(\alpha _k,\beta _k),\end{equation*}
with
$m\leq n+1$
and
$\alpha _k,\beta _k$
points belonging to
$\partial \{x\in \mathrm{Supp}\,(\rho _0)|\ C_x(T-Id)\lt h\}$
. Then for all
$k\in \{1,\ldots,m\}$
and
$x\in (\alpha _k,\beta _k)$
, we have
$C_x(\mathrm{v}^\star )=h$
so in particular,
$\mathrm{v}^\star =\mathrm{v}_{\beta _k}$
on
$(\alpha _k,\beta _k)$
. Let be
$Y_k=\sup \{x\geq \beta _k| \forall y \in (\alpha _k,x), \mathrm{v}^\star (y)=\mathrm{v}^\star _x(y)\}$
and
$(y_k)_{k=1,\ldots,N}$
(with
$N\leq m$
) the decreasing sequence such that
$\{y_k | \ k=1,\ldots,N\}=\{Y_k | \ k=1,\ldots,m\}$
. Likewise, define
$Z_k=\inf \{x\leq \alpha _k| \forall y \in (x,\beta _k), \mathrm{v}^\star (y)=\mathrm{v}^\star _{\beta _k}(y)\}$
and
$(z_k)_{k=1,\ldots,N}$
the decreasing sequence such that
$\{z_k | \ k=1,\ldots,N\}=\{Z_k | \ k=1,\ldots,m\}$
. We have by construction that
$\mathrm{v}^\star =\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,N}}$
and that
$\mathrm{v}^\star$
belongs to
$V_N$
.
Using this result, we can now prove that when
$n$
is finite, Algorithm 1 builds the solution
$\mathrm{v}^\star$
.
Theorem 2.
Suppose that
$\rho _0$
and
$\rho _1$
satisfy Assumptions 2 and that n defined in (5.8) is finite. There exist
$N\in \mathbb{N}$
and a sequence of disjoints intervals
$\big ((z_i,y_i)\big )_i\subset \mathrm{Supp}\,(\rho _0)^N$
such that for all
$i\in \{1,\ldots,N\}$
we have the following properties.
-
(a) For
$x\in [z_i,y_i]$
, we have
$\mathrm{v}^\star (x)=\mathrm{v}_{y_i}(x)$
(defined in (5.6)) and
$C_x^{\mathrm{alt}}({\mathrm{v}^\star })= h$
. -
(b) There exists
$ w_i\in (z_{y_i},y_i)$
such that
$\forall y \in [w_i,y_i)$
,
$\mathrm{v}^\star (y)\geq T(y)-y$
and
$\forall y \in (z_{y_i},w_i]$
,
$\mathrm{v}^\star (y)\leq$
$T(y)-y$
. -
(c) For all
$ x \notin \bigcup _{i=1}^N[z_i,y_i]$
,
$\mathrm{v}^\star (x)= T(x)-x$
. -
(d) The sequence
$\big ((z_i,y_i)\big )_i$
is the output of Algorithm
1
.
Proof. We first build the intervals satisfying the points
$(a)$
,
$(b)$
and
$(c)$
. Let be
$(Z_k,Y_k)_{k=1,\ldots,N}$
the disjoint intervals given by Lemma 5.10 such that
$\mathrm{v}^\star =\mathrm{v}^{(Z_k,Y_k)_{k=1,\ldots,N}}$
. From the definition of
$\mathrm{v}^{(Z_k,Y_k)_{k=1,\ldots,N}}$
, we know that
$(Z_k,Y_k)_{k=1,\ldots,N}$
satisfy the points
$(a)$
and
$(c)$
. Let us show that we can subdivide each interval
$(Z_k,Y_k)$
into a finite numbers of sub-intervals satisfying
$(b)$
. Define for all
$k\in \{1,\ldots,N\},$
\begin{equation*}\beta _k=\sup \{x\leq Y_k| C_x(T-\mathrm {Id})\gt h\} \text { and } \alpha _k=\inf \{x\geq Z_k| C_x(T-\mathrm {Id})\gt h\}.\end{equation*}
We first argue that we actually have
$\beta _k\lt Y_K$
. Suppose to the contrary that is not true, i.e., that
$\beta _k= Y_K$
. Then from the third point of Lemma 5.7, the function
$\mathrm{v}^\star -(T-\mathrm{Id})$
is either strictly positive on an interval
$(Y_k-\delta,Y_k)$
or it oscillates around
$0$
. If it oscillates around
$0$
, then there exists
$x\in (Y_k-\delta,Y_k)$
such that
$\mathrm{v}^\star (x)\gt T(x)-x$
and
$\partial _x\mathrm{v}^\star (x)\lt T^{\prime}(x)-1$
. Therefore, we have that
\begin{align} \frac{\mathrm{v}(x)\rho _0(x)}{1+\frac{x_0-x}{\mathrm{v}(x)}\partial _x\mathrm{v}(x)}\gt \frac{(T(x)-x)\rho _0(x)}{1+\frac{x_0-x}{T(x)-x}(T^{\prime}(x)-1)}\geq h, \end{align}
which is impossible, so we deduce that
$\mathrm{v}^\star -(T-\mathrm{Id})$
is strictly positive on an interval
$(Y_k-\delta,Y_k)$
. But again, as
$\mathrm{v}^\star (Y_k)=T(Y_k)-Y_K$
, we deduce that there exists
$x\in (Y_k-\delta,Y_k)$
such that
$\partial _x\mathrm{v}^\star (x)\lt T^{\prime}(x)-1$
, which implies that
$\mathrm{v}^\star$
does not satisfies the constraint at
$x$
. As this is not possible, we deduce that
$\beta _k\lt Y_k$
. Then, we also deduce from Lemma 5.6 that
$\mathrm{v}^\star (x)\geq T(x)-x$
for all
$x\in (\beta _k,Y_k)$
. In the same way, we can prove that
$\alpha _{k}\gt Z_k$
and
$\mathrm{v}^\star \leq T-\mathrm{Id}$
on
$(Z_k,\alpha _k)$
.
Therefore, the interval
$(Z_k,Y_K)$
can be subdivided into a finite number of intervals
$(z_{k,i},y_{k,i})_{i=1,\ldots,n_k}$
that verify
$(a)$
and
$(b)$
of the theorem. The number of sub-intervals is finite as the function
$x\mapsto v^\star (x)-T(x)-x$
cannot oscillate around
$0$
at the point where
$C_x(T-\mathrm{Id})\geq h$
(same arguments as (5.9)). For points where
$C_x(T-\mathrm{Id})\lt h$
, there exists
$\delta \gt 0$
such that for all
$y\in (x-\delta,x+\delta )$
we have
$C_y(T-\mathrm{Id})\lt h$
, so
$x\mapsto v^\star (x)-T-x$
cannot oscillate around
$0$
, otherwise there would be points where
$C_y(\mathrm{v}^\star )\lt h$
which is not possible as
$\mathrm{v}^\star$
saturates the constraint on the interval. Now the sequence of intervals
$(z_{k,i},y_{k,i})_{i=1,\ldots,n_k,k=1,\ldots,N}$
is our desired sequence that verifies
$(a),(b)$
and
$(c)$
of the theorem.
Let us now prove
$(d)$
by induction. For
$a,b\in \mathrm{Supp}\,(\rho )$
, define
$P_{a,b}$
the solution to Problem 3 but for the measure
$\rho _{0|_{[a,b]}}$
and
$ \rho _{1|_{[T(a),T(b)]}}$
. We prove that each time Algorithm 1 checks the condition of the ‘while loop’ at line 4, the current solution
$(z_k,y_k)_{k=1,\ldots,i-1}$
in the memory of the algorithm is optimal on the interval
$[z_{i-1},x_0]$
(i.e.,
$\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,i-1}}=P_{z_{i-1},x_0}$
). This is true at the first iteration as
$i=1$
and
$z_0=x_0$
.
Now fix
$i\geq 2$
and suppose that after a number of iterations of the ‘while loop’ at line
$4$
, for each
$m\in \{1,\ldots,i\}$
, the solution
$(z_k,y_k)_{k=1,\ldots,m-1}$
is optimal on the interval
$[z_{m-1},x_0]$
(i.e.,
$\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,m-1}}=P_{z_{m-1},x_0}$
). Compute line 5:
$y_i = \mathrm{arg\, min}_{y\geq x_i}J_{x_i}(y)$
and suppose that
$y_i\lt z_{i-1}$
. We have
\begin{align} J(P_{z_i,x_0}) &= \min _{j=0,\ldots,N} \min _{\substack{(\tau _k,\delta _k)_{k=1,\ldots,j}}} \left \{ J(\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,j}})\mid C_x(\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,j}})\leq h,\;\; x \in (z_i,x_0) \right \} \end{align}
\begin{align} & \geq \min _{\substack{j=0,\ldots,N\\ l=0,\ldots,j-1}}\min _{\substack{(\tau _{k},\delta _k)_{k=1,\ldots,j}\\ x_i\in (\tau _{l},\delta _l)}} \left \{ J(\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,j}})\left | \begin{array}{ll} C_x(\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,l}})\leq h,\;\; x \in (z_{i-1},x_0)\\[5pt] C_x(\mathrm{v}^{(\tau _k,\delta _k)_{k=l+1,\ldots,j}})\leq h,\;\; x \in (z_{i},\delta _{l+1}) \end{array} \right . \right \} . \end{align}
The first equality is given by Lemma 5.10. Then, the inequality is due to the fact that every candidate minimizer
$\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,j}}$
to (5.10) is a candidate minimizer to (5.11). As the solution to (5.11) is
$\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,i}}$
which actually verifies
$C_x(\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,i}})\leq h, \forall x \in (z_{i},x_0)$
, we then deduce that
$\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,i}}$
is equal to
$P_{z_i,x_0}$
.
Let us now treat the case where
$y_i\geq z_{i-1}$
. We prove that the solution
$P_{z_i,x_0}$
verifies that
$C_{x}(P_{z_i,x_0})=h$
for all
$x\in (x_i,z_{i-1})$
. By contradiction, suppose that it is not the case and let be
$\alpha =\sup \{x\geq x_i| C_x(P_{z_i,x_0})=h\}$
. Then, there exists
$\beta \in (\alpha,z_{i-1})$
such that
$C_\beta (P_{z_i,x_0})\lt h$
. From Proposition 5.8, we have that as
$y_i$
is the minimum of
$J_{x_i}$
and that
$\beta \lt y_i$
, then
$y\mapsto J_{x_i}(y)$
is decreasing at
$\beta$
. Therefore, as
$\alpha \lt \beta$
we deduce that there exists
$\gamma \in (\beta,y_i)$
such that the function
$y\mapsto P_{z_i,x_0}(y)\unicode{x1D7D9}_{\{y\notin (\alpha,\gamma)\}}+v_\gamma(y)\unicode{x1D7D9}_{\{y\in (\alpha,\gamma)\}}$
would be a better minimizer than
$P_{z_i,x_0}$
, which should not be possible. We therefore have
\begin{align*} P_{z_i,x_0}\in \mathrm{arg\, min}_{j=1,\ldots,i-1} \min _{\substack{(\tau _k,\delta _k)_{k=1,\ldots,j}\\ (x_i,z_{i-1})\subset (\tau _{j},\delta _{j})}} \{\ J(\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,j}})\mid C_x(\mathrm{v}^{(\tau _k,\delta _k)_{k=1,\ldots,j}})\leq h \}. \end{align*}
We now compute the line 7 of the algorithm:
$y_{i-1} = \mathrm{arg\, min}_{y\geq x_{i-1}}J_{x_i}(y)$
. We can apply the same reasoning whether
$y_{i-1}\gt z_{i-2}$
or not and obtain by induction that once line 12 of the algorithm has been executed, we indeed have
$P_{z_i,x_0}=\mathrm{v}^{(z_k,y_k)_{k=1,\ldots,i}}$
.
Next, we treat the case
$n=\infty$
. We first prove a stability result with respect to the constant
$h$
.
Lemma 5.11.
Suppose that
$\rho _0$
and
$\rho _1$
satisfy Assumptions 2. Then, there exists a constant
$C\gt (h-1)^{-1}$
such that for all
$\epsilon \in (0,C^{-1})$
, writing
$\mathrm{v}^\star _\epsilon$
the solution to Problem 3 for the flux constraint at
$h-\epsilon$
, we have
\begin{equation*}J(\mathrm {v}^\star _\epsilon )\leq J(\mathrm {v}^\star )+C\epsilon .\end{equation*}
Proof. Writing
$\delta =\sup _{x\in \mathrm{Supp}\,(\rho _0)}{toll}_{\mathrm{v}^\star }(x)$
, as
$\mathrm{v}^\star$
is the solution to Problem 3, we have that
$\delta \lt 1$
. Suppose that
\begin{equation*}\epsilon \leq \min \{\frac {h(1-\delta )}{2},h-1\}\end{equation*}
and define
$v_\epsilon =(1-\frac{\epsilon }{h})\mathrm{v}^\star$
. Then we have for all
$x\in \mathrm{Supp}\,(\rho _0),$
\begin{align*} C_x(v_\epsilon )=(1-\frac{\epsilon }{h}) C_x(\mathrm{v}^\star )\leq h-\epsilon, \end{align*}
so
$v_\epsilon$
is a candidate solution to the problem with constraint
$h-\epsilon$
. Furthermore,
\begin{align*} J(v_\epsilon )& = \int _{\mathbb{R}} \Big ( (1-\frac{\epsilon }{h})\mathrm{v}^\star (x)(x_0-x) + \frac{(T(x)-x_0)^2}{1-\frac{x_0-x}{(1-\frac{\epsilon }{h})\mathrm{v}^\star (x)}}\Big ) \rho _0(x)dx\\[5pt] & \leq J(\mathrm{v}^\star )+ \frac{\epsilon }{h}\int _{\mathbb{R}} \frac{(T(x)-x_0)^2(1-\frac{\epsilon }{h})\mathrm{v}^\star (x)}{((1-\frac{\epsilon }{h})\mathrm{v}^\star (x) -(x_0-x))(\mathrm{v}^\star (x) -(x_0-x))} \rho _0(x)dx.\\[5pt] & \leq J(\mathrm{v}^\star )+ \frac{\epsilon }{h} \left (\frac{1-\delta }{2\delta }(x_0-\sup \mathrm{Supp}\,(\rho _0))\right )^{-1}\int _{\mathbb{R}} \frac{(T(x)-x_0)^2(1-\frac{\epsilon }{h})\mathrm{v}^\star (x)}{\mathrm{v}^\star (x) -(x_0-x)} \rho _0(x)dx.\\[5pt] & \leq J(\mathrm{v}^\star )+ C\epsilon . \end{align*}
Now if
$n=\infty$
, it implies that the map
$x\mapsto C_{x}(T-\mathrm{Id})$
oscillates indefinitely around
$h$
. For
$\epsilon \gt 0$
, take
$U$
a uniform random variable on
$[0,\epsilon ]$
. As
$x\mapsto C_{x}(T-\mathrm{Id})$
cannot oscillate around more than a countable number of values, we have that with probability 1,
$x\mapsto C_{x}(T-\mathrm{Id})$
oscillates only a finite number of times around
$U$
. Therefore, we can solve Problem 3 with the flux constraint
$h-U$
using Theorem 2. For
$v_U$
the solution given by Algorithm 1, we have that for all
$x\in \mathrm{Supp}\,(\rho _0)$
,
\begin{equation*}C_x(v_U)\leq h-U\leq h,\end{equation*}
and by Lemma 5.11,
\begin{equation*}J(v_U)\leq J(\mathrm {v}^\star )+C\epsilon .\end{equation*}
6. Numerical example
We provide an example to highlight the departure of the optimal transport plan through a toll with a bound on the flux, from the ideal unconstrained transport
$T$
. The example we have selected is basic, with uniform probability densities
$\rho _0(x) = \unicode{x1D7D9}\{x \in [0,1]\}$
,
$\rho _1(x) = \unicode{x1D7D9}\{x \in [2,3]\}$
, and a toll at
$x_0=3/2$
with a bound
$h$
on the flux, with
$1\lt h\leq 2$
. The stringent constraint on the flux, which necessitates varying velocities so as to redistribute the mass flow as it traverses the toll, is clearly seen in the succession of distributions
$Y_{t\sharp \rho _0}$
displayed in Figure 5. Evidently, these readily contrast with the unconstrained transport that pushes forward
$\rho _0$
with constant speed giving
$\rho _t(x)=\rho _0(x-2t)$
.
Figure 5. Example of transporting a uniform distribution through a constriction (with
$h=1.5$
) to a similar uniform terminal distribution. While the optimal unconstrained transport will preserve the shape of marginals at each time
$t$
, the flux constraint necessitates an optimal velocity that changes with
$x$
, stretching the leading edge of the distribution as it approaches the toll. Note that the snapshots of the transported distributions
$Y_{t\sharp \rho _0}$
‘squeeze’ while crossing the toll, and that the flow is symmetric with time.
Specifically, with the flux constraint in place, we obtain that the optimal transport is effected by
\begin{equation*} Y_t(x)=\left \{\begin {array}{lll} x +t\mathrm {v}(x) &\mbox { for }&t\leq {toll}(x)=\frac {3/2-x}{\mathrm {v}(x)},\\[5pt] 3/2 +(t-{toll}(x))g(x) &\mbox { for }&t\geq {toll}(x). \end {array}\right . \end{equation*}
Then, the constraint (5.2) gives that
$\mathrm{v}$
solves the ODE
\begin{equation*} \frac {\mathrm {v}(x)}{1+\frac {3/2-x}{\mathrm {v}(x)} \partial _x\mathrm {v}(x)} =h. \end{equation*}
It follows that
$\mathrm{v}(x) = \frac{h(2x-3)}{2x-3+\alpha }$
for a certain value
$\alpha \in \mathbb{R}$
. Using the fact that the optimal solution must be symmetric in time
$(\mathrm{v}(x)=g(1-x))$
and that
$g(x) = \frac{x+0.5}{1-{toll}(x)}$
, we finally obtain that
$\mathrm{v}(x) = \frac{h(2x-3)}{2x-1-h}$
. Snapshots of the flow along the path from
$\rho _0$
to
$\rho _1$
are depicted in Figure 5.
7. Discussion and conclusion
We have presented theory for the most basic optimal transport problem in
$\mathbb R$
, through a constriction where a throughput constraint is imposed. We modelled the formulation after the standard Monge-Kantorovich optimal transport with a quadratic cost. We have shown that an optimal transport exists and is unique under general assumptions. Under some suitable assumptions on the densities to be transported to one another, we have shown explicitly how to construct the transport plan. Moreover, we have highlighted natural properties of the transport plan.
More generally, in the case where
$\rho _0$
and
$\rho _1$
are densities on
$\mathbb{R}^d$
and that all the trajectories have to pass through a single point
$x_0\in \mathbb{R}^d$
, we can readily extend the result presented as follows. For
$\lambda_{\alpha S^{d-1}}$
, the Lebesgue measure on the sphere of radius
$\alpha$
and centre
$x_0$
is defined as
\begin{equation*} \nu ^0(\alpha )= \int _{\alpha S^{d-1}}\rho _0(x)d\lambda_{\alpha S^{d-1}}(x) \end{equation*}
and
$\nu ^1$
the same way. Then, the problem in
$\mathbb{R}^d$
is equivalent to solving the problem in dimension 1 between the measure
$\nu ^0,\nu ^1$
defined as
$\nu ^0(x)=\unicode{x1D7D9}\{x\lt 0\} \nu ^0({-}x)$
and
$\nu ^1(x)=\unicode{x1D7D9}\{x\gt 0\} \nu ^1(x)$
.
A significant departure from the current setting arises in the case of multiple tolls, or of a continuum of tolls, where the flux rate is bounded on a curve, surface, etc. The case where a sequence of tolls, possibly even zero-dimensional (points), where mass has to flow through all in succession, is of particular interest in engineering applications. Indeed, in the modern information age, knowledge of obstructions ‘down the road’ can undoubtedly be used to optimize transportation cost upstream. On the other hand, the paradigm of multiple alternative tolls that one can choose to cross is expected to have a more combinatorial flavour. Lastly, one could generalize the problem presented in this paper to transport of densities in dimension
$d$
, with a flux constraint on a measurable set with respect to the
$p$
-dimensional Hausdorff measure
$\mathcal{H}^p$
(with
$p\leq d$
). For instance, an analogous flux constraint on a measurable set
$A\subset \mathbb{R}^d$
with
$0\lt \mathcal{H}^p(A)\lt \infty$
can be cast as
$\forall B\subset A$
measurable with
$\mathcal{H}^p(B)\gt 0$
and
$t\in (0,1)$
\begin{equation*} \forall \alpha _1,\alpha _2\in \mathbb {R}, \quad \frac {\mathcal {H}^p(A)}{\mathcal {H}^p(B)} \int \unicode {x1D7D9}_{\{\exists \tau \in (t+\alpha _1,t+\alpha _2)\ |\ Y_\tau (x)\in B\}} \rho _0(x)dx \leq h|\alpha _2-\alpha _1|. \end{equation*}
The proof of existence and uniqueness of a solution should follow using similar arguments. However, to completely characterize the behaviour of the solution as in the simpler case treated herein is expected to be considerably more challenging; one would need a finer description of how the mass distributes while traversing the toll.
Transport problems with a throughput restriction are quite natural in a variety of scientific disciplines. Of course, transportation through tolls on highways represents perhaps the most rudimentary paradigm in an engineering setting. Likewise, throughput through servers with a throughput bound is common in queuing systems. A continuum theory as envisioned herein, in higher dimensions and with multiple serial tolls, may produce useful practical insights. Finally, while fluid flow, passing through constrictions or porous media, though not directly abiding by the rigid setting of bounded throughput, could provide an idealized pertinent model in certain situations. Evidently, for an accurate model for fluid past constrictions, besides distinguishing between compressible and incompressible, throughput must be dictated by pressure, which in turn may be introduced in a suitable cost functional to be optimized for a further broadening of the general programme.
Financial support
The research has been supported in part by the AFOSR under grant FA9550-23-1-0096 and ARO under W911NF-22-1-0292.
Competing interests
The author(s) declare none.
Open access
