Electronic Journal of Differential Equations, Vol. 2023 (2023), No. 22, pp. 1–24.

ISSN: 1072-6691. URL: https://ejde.math.txstate.edu or https://ejde.math.unt.edu

AN OPTIMAL TRANSPORT PROBLEM WITH STORAGE FEES

MOHIT BANSIL, JUN KITAGAWA

Communicated by Nestor Guillen

Abstract. We establish basic properties of a variant of the semi-discrete op-

timal transport problem in a relatively general setting. In this problem, one is
given an absolutely continuous source measure and cost function, along with a

finite set which will be the support of the target measure, and a “storage fee”

function. The goal is to find a map for which the total transport cost plus the
storage fee evaluated on the masses of the pushforward of the source measure

is minimized. We prove existence and uniqueness for the problem, derive a

dual problem for which strong duality holds, and give a characterization of
dual maximizers and primal minimizers. Additionally, we find some stability

results for minimizers and a Γ-convergence result as the target set becomes
denser and denser in a continuum domain.

1. Introduction

Semi-discrete optimal transport. We begin by recalling the classical optimal
transport problem. Suppose X, Y are Polish spaces, c : X × Y → R is a Borel
measurable cost function, and µ, ν are Borel probability measures on X and Y
respectively. Then the optimal transport problem or Monge problem transporting
µ to ν is to find a Borel measurable mapping T : X → Y such that T#µ = ν
(here recall the pushforward measure is defined by T#µ(E) = µ(T−1(E)) for any
measurable E ⊂ Y ), and T satisfies∫

X

c(x, T (x)) dµ(x) = min
S#µ=ν

∫
X

c(x, S(x)) dµ(x). (1.1)

If ν is a finite linear combination of delta measures, the above is usually referred
to as the semi-discrete optimal transport problem.

We will now be interested in the following variant of the semi-discrete optimal
transport problem, where we introduce a “storage fee.” Fix a finite collection of
N points, Y := {yj}Nj=1 and a function F : RN → R, and assume µ is a Borel
probability measure on a Polish space X. This variant is to find a pair (T, λ) where
λ = (λ1, . . . , λN ) ∈ RN and T : X → Y is Borel measurable satisfying

T#µ =

N∑
j=1

λjδyj

2020 Mathematics Subject Classification. 49J45, 49K40, 49Q22.
Key words and phrases. Optimal transport; gamma convergence; storage fees;
queue penalization.
©2023. This work is licensed under a CC BY 4.0 license.
Submitted June 22, 2022. Published March 2, 2023.

1



2 M. BANSIL, J. KITAGAWA EJDE-2023/22

such that∫
X

c(x, T (x)) dµ(x) + F (λ) = min
λ̃∈RN , T̃#µ=

∑N
j=1 λ̃

jδyj

∫
X

c(x, T̃ (x)) dµ(x) + F (λ̃).

(1.2)
Note here that the vector λ is actually uniquely determined by the map T . We will
consider a relaxation of this problem which we will refer to as the primal problem
for the remainder of the paper. To define this relaxation, we write Π(µ, ν) to
denote the space of probability measures on X × Y whose left and right marginals
are µ and ν respectively. Then, we wish to find a pair (γ, λ) where λ ∈ RN and

γ ∈ Π(µ,
∑N
j=1 λ

jδyj ), satisfying∫
X×Y

c dγ + F (λ) = min
λ̃∈RN , γ̃∈Π(µ,

∑N
j=1 λ̃

jδyj )

∫
X×Y

c dγ̃ + F (λ̃). (1.3)

The above relaxation is the analogue of relaxing the Monge problem (1.1) in classical
optimal transport to the Kantorovich problem, which we recall is (fixing Borel
probability measures µ and ν on any two topological spaces X and Y ) the problem
of finding a measure γ ∈ Π(µ, ν) satisfying∫

X×Y
c dγ = min

γ̃∈Π(µ,ν)

∫
X×Y

c dγ̃. (1.4)

Once a minimizing pair in the above primal problem (1.3) is found, it is clear
the measure γ is a solution in the Kantorovich problem (1.4) with the choice ν =∑N
j=1 λ

jδyj . Hence under standard conditions on the cost function and µ, it is

easily seen that a solution of (1.3) gives rise to a solution of the Monge version of
the problem (1.2). For more details see Remark 4.3.

Previous results. The paper [6] considers the problem presented here in the spe-
cific case of cost function given by c(x, y) = |x − y|p with p ≥ 1, and storage fee

function of the form F (λ) =
∑N
j=1 λ

jhj(λ
j) for some functions hj (note however,

the authors mention their results can be extended to more general cost functions
satisfying the condition (4.2)). This previous result gives conditions for optimiz-
ers, but does not introduce the dual problem or show stability properties as we do
here. We are careful to mention our characterization from Section 4 matches the
characterization of optimizers given in [6]: however our methods differ as we use
a proof based on the dual formulation, while [6] relies on both the specific form of
their function F and an assumption of differentiability. Finally, we mention that
[6] also analyzes an associated but different variational problem which we do not
discuss, our problem is equivalent to what Crippa, Jimenez, and Pratelli refer to as
finding an “optimum,” while the above reference deals with the additional problem
of finding an “equilibrium.”

There are also a number of results in the literature dealing with the so-called
bilevel location problem using the framework of optimal transport: this can be
viewed as a two level problem in which there is a “lower level problem” equivalent
to the problem discussed in this manuscript, followed by a second “upper level
problem” consisting of minimizing over the locations {yj}Nj=1 in the target domain.
The paper [8], analyzes the case when the lower level problem corresponds to our
problem with c(x, y) = |x − y|2 in R2 × R2 and F (λ) = 〈a, λ〉 for a fixed vector
a, and shows existence and uniqueness under certain conditions. The result [5]



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 3

views the problem in an economic context, their lower level problem is related to
a partial optimal transport problem with an associated storage fee; note however
that their problem is not exactly an optimal transport problem as it arises from the
problem of monopolistic pricing, and involves an extra nonlinearity in the definition
of Laguerre cells. We emphasize that we do not deal with the “upper level problem”,
while the above two references also analyze that problem as well.

Contributions of this article. We show the existence of minimizers of the opti-
mal transport problem with storage fees, exhibit a dual problem with strong duality
(along with existence of dual maximizers) for a wide class of storage fees F and c,
show a sharp characterization of dual and primal extremizers, and produce some
stability results. One novelty of our results is that both existence and the charac-
terization of minimizers do not require any assumption of differentiability of F , in
contrast with previous results such as [6]. The class of functions is wide enough to
allow for storage fee functions which may take the value ∞ at some points in the
standard simplex. Additionally, the simple characterization of extremizers can be
exploited to form a provably convergent numerical approximation scheme based on
a damped Newton method, which the authors have explored in [1].

We also mention the following economics interpretation of the problem with stor-
age fees. A manufacturer has a distribution of factories µ, all producing the same
product, and is leasing a finite number of warehouses at the locations yj . At the
end of each production cycle, the manufacturer must ship all of their product to be
stored at some combination of the warehouses. The manufacturer can choose how
many units of their product is to be stored at each warehouse, but the leasing com-
pany will charge a storage fee given by F based on the capacity used. Additionally,
there is a cost associated to the transportation itself given by c, and the goal is to
minimize the total cost of transport plus storage.

We conclude by mentioning that even in the restricted cases treated in previous
work, there is no mention of the associated dual problem, which we have shown
has strong duality. The dual problem we exhibit here has a very natural interpre-
tation in terms of the economic analogy mentioned above. Namely, for the classical
optimal transport problem (see [12, p. 53]), the dual problem can be interpreted
as contracting a third party shipping company: a pair of dual potentials repre-
sents a price schedule (the amount the company would charge to pick up and drop
off goods at given source and target locations) and the dual functional would be
the total price charged for a given distribution of source and target goods. In our
dual problem with storage fee (see Theorem 3.3 for precise statement), the dual pair
(ϕ,ψ) again represents a price schedule for pickup and drop off, but the term F ∗(ψ)
indicates that the third party company will build into their prices the added step
of optimizing how to distribute the target mass, accounting for the storage fee that
will be charged. While the classical optimal transport problem has a well-known
canonical dual problem, as a general optimization our primal problem may have
many possible associated dual problems; this interpretation in terms of shipping
suggests the particular dual problem presented here represents a canonical choice.

Remark 1.1. The minimization problem with storage fees has potential applica-
tions in supervised data clustering. If µ is a distribution of data points known to
fall into N clusters, and y1, . . . , yN are representative data points from each cluster,
solving the optimal transport problem with a storage fee is a method of cluster-
ing the data, where the size of each cluster is penalized according to the storage



4 M. BANSIL, J. KITAGAWA EJDE-2023/22

fee function F . The theory developed is flexible enough to allow for combining a
convex function to penalize large cluster size, with a hard size constraint (F ≡ ∞
when the capacity at a point exceeds a certain threshold) in such a data clustering
problem.

As a toy example, one could consider testing whether a handwritten document
conforms well to Benford’s law of leading digits. It is empirically observed that
the probability the digit d occurs as a leading digit in a document tends to follow
Benford’s law:

P (d) ≈ log10(1 +
1

d
), d = 1, . . . , 9.

This has been suggested as a potential method to detect whether numerical figures
are unnaturally generated, for example in accounting fraud or fabrication of scien-
tific data. Now consider a handwritten document containing many numbers. Then
each leading digit can be considered as a grey scale image, which can be described
as a vector in some Rn, suppose the distribution µ describes this collection of dig-
its. Let Y = {y1, . . . , y9} where each yi is one representative for the handwritten
digit j. Finally suppose some cost function c(x, yj) is given which is a measure of
affinity between a handwritten digit x and the representative digit yj . Now define
the storage fee function F : R9 → R by

F (λ) :=

9∑
j=1

f(λj − log10(1 +
1

j
)),

where f : R→ R is a strictly increasing, convex function with f(0); note that F is a
convex function hence (modulo conditions on c) all of our results in this article will
be applicable. Then a minimizer in (1.3) with this choice of F will give a clustering
of the leading digits appearing in the distribution µ, and the value of the functional
associated to this minimizer can represent a measure of divergence of the document
from Benford’s law.

Notation and conventions. We will fix some notation and conventions to be used
in the remainder of the paper. We fix positive integers N and n and a collection
Y := {yj}Nj=1 (however, in Subsection 5.1 we will consider an arbitrary bounded
metric space Y , not necessarily finite). We also denote the standard N -simplex by

Λ := {λ ∈ RN :

N∑
j=1

λj = 1, λj ≥ 0},

and given a vector λ ∈ Λ we write νλ :=
∑N
j=1 λ

jδyj . We reserve the boldface

notation 1 for the vector in RN whose components are all 1. The space of Borel
probability measures on a metric space X will be denoted P(X). The subset of
P(X × Y ) consisting of measures with left and right marginals equal to µ ∈ P(X)
and ν ∈ P(Y ) respectively will be written as Π(µ, ν), and Π(µ) will be the subset
of P(X×Y ) consisting of measures with left marginal µ. Projection from X×Y to
X and Y will be written πX and πY . We will write Cb(S) for the set of bounded,
continuous functions on a metric space S. As is standard practice, we will refer
to weak ∗ convergence of probability measures in duality with Cb(S) as “weak
convergence.”

We will also identify any real valued function on Y with a vector in RN in the
obvious way, and always assume that X is separable.



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 5

Also given a convex function f : RN → R∪{∞}, we write dom(f) := {x : f(x) <
∞} to denote its effective domain. The function F will be assumed to be lower
semicontinuous on RN for Section 2, while for Sections 3 and 4 we assume F is a
proper, closed, convex function, with dom(F ) ⊂ Λ.

Finally we use |·| to denote either the Euclidean norm of a vector, or the Lebesgue
measure of a set, which usage should be clear to the reader from context.

Outline. In Section 2 we show existence of minimizers for the relaxed problem
(1.3) when F and c are lower semicontinuous. In Subsection 3 we show strong
duality when F is convex, and existence of dual maximizers when c is uniformly
continuous and bounded (Proposition 3.5). We also provide an estimate on the
duality gap when F is not convex which is sharp (Remark 3.6 and Proposition 3.7).
In Subsection 3.1 we show some relationships between our dual problem and the
classical Kantorovich dual problem. In Section 4, under additional assumptions on c
and µ we show the existence of solutions of the primal problem exist in the “Monge”
sense of (1.2) along with a sharp characterization of dual and primal extremizers.
Finally we show two stability results in Section 5: the first for minimizers under
perturbations of the storage fee function, and the second a Γ-convergence result as
one takes a sequence of finite target sets that become dense in some domain. Ap-
pendix 6 contains the proof of the sharp duality gap Proposition 3.7 while appendix
7 presents an example where a maximizer in the classical Kantorovich problem is
not a maximizer in our dual problem.

2. Existence of minimizers

In this section we prove the existence of minimizers for problem (1.3). First we
recall some elementary definitions and results.

Definition 2.1. A collection of Γ ⊂ P(X) is said to be tight if for any ε > 0, there
exists a compact set K ⊂ X such that µ(K) > 1− ε for every µ ∈ Γ.

Lemma 2.2. Fix µ ∈ P(X), then Π(µ) is tight.

Proof. Since X is separable, the collection {µ} is tight. Now let ε > 0 be given.
Choose K ⊂ X, compact so that µ(K) > 1− ε. Note that since Y is finite, K × Y
is also compact. Then for any γ ∈ Π(µ), we find γ(K × Y ) = µ(K) > 1− ε, hence
Π(µ) is tight. �

As a corollary we see that Π(µ) is relatively weakly compact by Prokhorov’s
Theorem (see [2, Theorem 5.1]). With this compactness in hand, existence of a
minimizer follows easily.

Theorem 2.3. Suppose c(·, yj) : X → (−∞,∞] is lower semicontinuous for each
j, there exists some upper semicontinuous a ∈ L1(µ) with a : X → [−∞,∞) such
that minj c(x, yj) ≥ a(x) for all x ∈ X, and F is lower semicontinuous. Then there
exist minimizers of the primal problem (1.3).

Proof. Replacing each c(·, yj) with c(·, yj) − a, we may assume c(·, yj) ≥ 0 and is
lower semicontinuous for each j.

Let {(γk, λk)}∞k=1 be a minimizing sequence for (1.3): that is a sequence with
γk ∈ Π(µ) such that

∫
X×Y c dγk + F (λk) approaches the minimum value in (1.3),

where νλk is the right marginal of γk. By the above remark Π(µ) is compact and
so there is a subsequence of γk, which we do not relabel, that converges weakly to



6 M. BANSIL, J. KITAGAWA EJDE-2023/22

some γmin ∈ Π(µ). We will show that γmin is actually a minimizer. Let λmin be the
vector in RN so that νλmin is the right marginal of γmin.

For ϕ ∈ Cb(Y ) = RN ,

lim
k→∞

∫
Y

ϕdνλk = lim
k→∞

∫
X×Y

(ϕ ◦ πY ) dγk =

∫
X×Y

(ϕ ◦ πY ) dγmin =

∫
Y

ϕdνλmin
,

meaning νλk converges weakly to νλmin
, hence in particular since 1X×{yj} ∈ Cb(X×

Y ), we have

lim
k→∞

λjk = lim
k→∞

γk(X × {yj}) = γmin(X × {yj}) = λjmin. (2.1)

By [12, Lemma 4.3], the functional γ 7→
∫
X×Y c dγ is weakly lower semicontinuous.

Since F is lower semicontinuous, we thus obtain∫
X×Y

c dγmin + F (λmin) ≤ lim inf
k→∞

(∫
X×Y

c dγk + F (λk)
)

showing (γmin, λmin) is a minimizer. �

3. Dual problem

Our first goal in this section will be to deduce a dual problem associated to our
primal problem (1.3). For the following Sections 3 and 4, we will assume that F is
a proper, closed, convex function, with dom(F ) ⊂ Λ.

Strong duality. To state the dual problem, we first recall a basic concept from
convex analysis.

Definition 3.1. Let E be a Banach space. If G : E → R∪{∞} is a proper function
(i.e., it is not identically∞), its Legendre-Fenchel transform is the (proper, convex)
function G∗ : E∗ → R ∪ {∞} defined for any y ∈ E∗ by

G∗(y) := sup
x∈E

(〈y, x〉 − F (x)),

where 〈y, x〉 is the duality pairing between elements of E∗ and E.
If E = E∗ = RN , the Legendre-Fenchel transform is called the Legendre trans-

form.

Since Λ is compact, we see that F is bounded from below everywhere, as any
affine function supporting F from below will be bounded on dom(F ). Thus, since
F is proper we see that F ∗ is actually finitely valued everywhere on RN by the
definition of Legendre transform.

It is also convenient at this point to introduce the notion of c and c∗-transforms,
and c-convexity. Note carefully that, since we are in the semi-discrete case the c-
transform of a function defined on X will be a vector in RN , while the c∗-transform
of a vector in RN will be a function whose domain is X.

Definition 3.2. If ϕ : X → R ∪ {∞} (which is not identically ∞) and ψ ∈ RN ,
their c- and c∗-transforms are a vector ϕc ∈ RN and a function ψc

∗
: X → R∪{∞}

respectively, defined by

(ϕc)j := sup
x∈X

(−c(x, yj)− ϕ(x)), (ψc
∗
)(x) := max

1≤j≤N
(−c(x, yj)− ψj).

If ϕ : X → R ∪ {∞} is the c∗-transform of some vector in RN , we say ϕ is a
c-convex function. A pair (ϕ,ψ) with ϕ : X → R ∪ {∞} and ψ ∈ RN is is called a
c-conjugate pair if ϕ = ψc

∗
and ψ = ψc

∗c = ϕc.



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 7

Note that from the definition, if −ϕ − ψ ≤ c, then −ϕ(x) ≤ −ψc∗(x) and
−ψj ≤ −(ϕc)j for all x ∈ X and 1 ≤ j ≤ N , while −ϕ− (ϕc) ≤ c, −(ψc

∗
)− ψ ≤ c

always holds.

Theorem 3.3 (Strong duality). Suppose c satisfies the same conditions as Theorem
2.3 and F is a proper, closed, convex function, with dom(F ) ⊂ Λ, then there is
strong duality, i.e.,

min
λ∈Λ, γ∈Π(µ,νλ)

∫
X×Y

c dγ + F (λ)

= sup
{
−
∫
X

ϕdµ− F ∗(ψ) : (ϕ,ψ) ∈ L1(µ)× RN ,

− ϕ(x)− ψj ≤ c(x, yj), ∀yj ∈ Y, µ-a.e. x ∈ X
}
.

(3.1)

Moreover, it is possible to replace L1(µ) by Cb(X) in the right hand side above.

Proof. Since Cb(X) ⊂ L1(µ), the supremum of the dual problem with Cb(X) is a
lower bound for the one with L1(µ). On the other hand, for any γ ∈ Π(µ, νλ) for
some λ ∈ Λ and (ϕ,ψ) ∈ L1(µ)×RN which is admissible in (3.1), by the definition
of F ∗ (see [9, p.105, Fenchel’s inequality]),

−
∫
X

ϕdµ− F ∗(ψ) ≤ −
∫
X

ϕdµ− 〈λ, ψ〉+ F (λ)

=

∫
X×Y

(−ϕ(x)− ψ(y)) dγ(x, y) + F (λ)

≤
∫
X×Y

c dγ + F (λ).

Thus it is sufficient to prove that

min
λ∈Λ, γ∈Π(µ,νλ)

∫
X×Y

c dγ + F (λ)

≤ sup
{
−
∫
X

ϕdµ− F ∗(ψ) : (ϕ,ψ) ∈ Cb(X)× RN ,

− ϕ(x)− ψj ≤ c(x, yj), ∀(x, yj) ∈ X × Y }.

(3.2)

First assume X is compact and each c(·, yj) is continuous; by subtracting a
constant we may assume c ≥ 0. We first prove the duality statement with Cb(X)
in place of L1(µ). Let E = C(X × Y ) = Cb(X × Y ) (by compactness of X) and
note its dual is given by E∗ =M(X ×Y ), the space of Radon measures on X ×Y .
Then define Θ, Ξ : E → R ∪ {∞} by

Θ(u) :=

{
0, if u(x, y) ≥ −c(x, y), ∀(x, y) ∈ X × Y
∞, otherwise

Ξ(u) :=


−
∫
X
ϕdµ+ F ∗(−ψ),

∃(ϕ,ψ) ∈ Cb(X)× RN s.t. u(x, yj) = −ϕ(x)− ψj , ∀(x, yj) ∈ X × Y,

∞, otherwise,

(we will write u = −ϕ − ψ as shorthand for the condition in the first case of
Ξ above). It is now necessary to check that Ξ as above is well-defined. Indeed,

if u(x, yj) = −ϕ1(x) − ψj1 = −ϕ2(x) − ψj2 for all (x, yj) ∈ X × Y , we can see



8 M. BANSIL, J. KITAGAWA EJDE-2023/22

there exists some r ∈ R such that ϕ1 = −r + ϕ2, and ψ1 = ψ2 + r1. Since Λ is
contained in a plane orthogonal to 1 and F = ∞ outside of this plane, a direct
verification of the definition implies that for any λ ∈ dom(F ) and ψ ∈ RN such
that 〈·−λ, ψ〉+F (λ) ≤ F on RN , we have 〈·−λ, ψ+r1〉+F (λ) ≤ F on RN for any
r ∈ R as well. Since F ∗ is finite everywhere, by [9, Theorem 23.4] there exists some
λ which must be in Λ, such that 〈· − (−ψ2), λ〉+ F ∗(−ψ2) ≤ F ∗ on RN . Hence by
[9, Theorem 23.5],

F ∗(−ψ1) = F ∗(−ψ2 − r1) = −〈ψ2, λ〉 − r〈1, λ〉 − F (λ) = −r + F ∗(−ψ2). (3.3)

Since µ is a probability measure, this shows Ξ is well-defined. It is immediate to see
that Θ and Ξ are convex, and that for u ≡ 1, Θ(u), Ξ(u) <∞ and Θ is continuous
at u.

We now compute

Θ∗(−γ) = sup
u≥−c

(
−
∫
X×Y

u dγ
)

=

{∫
X×Y c dγ, γ ≥ 0

∞, otherwise

and

Ξ∗(γ) = sup
(ϕ,ψ)∈Cb(X)×RN

(∫
X×Y

(−ϕ(x)− ψ) dγ +

∫
X

ϕdµ− F ∗(−ψ)
)

=

{
supψ

(
〈−ψ, λ〉 − F ∗(−ψ)

)
= F ∗∗(λ) = F (λ), (πX)#γ = µ, (πY )#γ = νλ

∞, otherwise

where we used convexity of F in the last line above.
Next we find (where by an abuse of notation we will write −ϕ−ψ ≤ c to denote

−ϕ(x)− ψj ≤ c(x, yj) for all x ∈ X and 1 ≤ j ≤ N)

inf
z∈E

(Θ(z) + Ξ(z)) = inf
ϕ̃+ψ̃≤c

(
−
∫
X

ϕ̃ dµ+ F ∗(−ψ̃)
)

= − sup
−ϕ−ψ≤c

(∫
X

(−ϕ) dµ− F ∗(ψ)
)
.

Hence by the Fenchel-Rockafellar theorem (see [11, Theorem 1.9]) we have

sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− F ∗(ψ)
)

= − inf
z∈E

(Θ(z) + Ξ(z))

= min
λ∈Λ,γ∈Π(µ,νλ)

(∫
X×Y

c dγ + F (λ)
)

proving (3.2) in this case.
Next assume X is a general Polish space, but c ∈ Cb(X × Y ) is uniformly

continuous; again we may assume c ≥ 0. Fix ε ∈ (0, 1), then by Ulam’s lemma
there exists a compact K ⊂ X such that µ(K) > 1−ε > 0. Let us define µ̃ := 1Kµ

µ(K) ,

then by Theorem 2.3 there is a minimizer (γ̃, λ) of (1.3) with µ̃ and the restriction
of c to K × Y replacing µ and c. Then we can apply the first case above to find
(ϕ̃, ψ̃) ∈ Cb(K)× RN , admissible in (3.1), satisfying

−
∫
X

ϕ̃ dµ̃− F ∗(ψ̃) ≥
∫
K×Y

c dγ̃ + F (λ)− ε ≥ min
Λ
F − ε = −F ∗(0)− ε,

where by an abuse of notation we identify the discrete measure (πY )#γ with its
vector of weights in Λ, and we have used [9, Theorem 27.1] to obtain the final



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 9

equality. In particular, this shows that for some x0 ∈ K, we have −ϕ̃(x0)−F ∗(ψ̃) ≥
−F ∗(0)−1, then by adding a constant to ϕ̃ and subtracting the same multiple of 1

from ψ̃, by (3.3) we may assume min
(
− ϕ̃(x0),−F ∗(ψ̃)

)
≥ −F

∗(0)+1
2 . Then for any

index j, we have ψ̃j ≥ −c(x0, yj)− ϕ̃(x0) ≥ − sup |c|− F∗(0)+1
2 . On the other hand,

since F is proper, there exists at least one λ0 ∈ Λ for which F (λ0) < ∞, thus we

have F ∗(rλ0) ≥ 〈rλ0, λ0〉 − F (λ0) → ∞ as r → ∞. Since F ∗(ψ̃) is bounded from

above, this shows that 〈ψ̃, λ0〉 has an upper bound, independent of ε. Combined
with the previous line, there exists some fixed index j and M > 0 independent of
ε such that |ψ̃j | ≤ M . In turn, this shows supX |ψ̃c

∗ | ≤ supX×Y |c| + M , and we
calculate

−
∫
X

ψ̃c
∗
dµ− F ∗(ψ̃)

= −µ(K)

∫
K

ψ̃c
∗
dµ̃−

∫
X\K

ψ̃c
∗
dµ− F ∗(ψ̃)

≥ −µ(K)

∫
K

ϕ̃ dµ̃− µ(X \K) sup
X
|ψ̃c
∗
| − F ∗(ψ̃)

≥ (1− ε)
(∫

K×Y
c dγ̃ + F (λ)

)
− ε(1 + sup

X×Y
|c|+M +

F ∗(0) + 1

2
).

(3.4)

Now define γ := µ(K)γ̃+ (µ⊗νλ)1(X\K)×Y . For A ⊂ X and B ⊂ Y Borel we have

γ(A× Y ) = µ(K)γ̃(A× Y ) + µ(A \K) = µ(A ∩K) + µ(A \K) = µ(A),

γ(X ×B) = µ(K)γ̃(X ×B) + µ(X \K)νλ(B)

= µ(K)νλ(B) + µ(X \K)νλ(B) = νλ(B),

thus γ ∈ Π(µ, νλ). Then∫
X×Y

c dγ + F (λ) = µ(K)

∫
X×Y

c dγ̃ +

∫
(X\K)×Y

c d(µ⊗ νλ) + F (λ)

≤
∫
K×Y

c dγ̃ + F (λ) + µ(X \K) sup
X×Y

|c|

≤
∫
K×Y

c dγ̃ + F (λ) + ε sup
X×Y

|c|,

hence combining with (3.4) and taking ε→ 0 shows (3.2) in this case.
Finally, suppose c is lower semicontinuous, considering c − a we can assume

c ≥ 0. By [4, Corollary 1.34], c is the limit of an increasing sequence of ck ∈
Cb(X × Y ) which are uniformly continuous, by Theorem 2.3 there exist a sequence
of minimizers (γk, λk) to the associated primal problems (1.3). By Lemma 2.2
and arguing as in (2.1), we extract a subsequence where λk → λ ∈ Λ and γk
converges weakly to γ ∈ Π(µ, νλ). Arguing as in Step 3 of the proof of [11, Theorem
1.3] and using the lower semicontinuity of F , we find that

∫
X×Y c dγ + F (λ) ≤

lim infk→∞(
∫
X×Y ck dγk + F (λk)). We may then apply (3.2) for each ck, and use

that dual pairs admissible for ck are admissible for c (since ck ≤ c) to obtain (3.2)
for c, finishing the proof. �

We will now show the existence of maximizers for the dual problem (3.1). As
in the classical optimal transport case (see, for example [10, Proposition 1.11]), we
utilize the c- and c∗-transforms of functions to obtain compactness.



10 M. BANSIL, J. KITAGAWA EJDE-2023/22

Remark 3.4. It turns out a dual maximizing pair in (3.1) is maximizing in the
classical optimal transport problem where the target measure is the minimizer in
the primal problem (1.3). However this fact is not obvious because of the presence
of the term −F ∗(ψ) in the dual problem, we will obtain this as a consequence of
Lemma 3.10 in Subsection 3.1 below. We also warn the reader, a maximizer in the
classical dual problem (3.5) between µ and a minimizing measure νλ in the primal
problem may not be a maximizer in our dual problem 3.1, as illustrated in Example
7.1 in the appendix.

Finally, unlike Theorem 3.3, it is not clear how to extend existence of dual
maximizers to more general (for example, lower semicontinuous) c. In the classical
Kantorovich duality one can use an argument based on c-cyclical monotonicity
as in [12, Theorem 5.10 (iii)], however this approach fails as there is a lack of
information of F and F ∗. Additionally, for more general c it could be possible
that the potential function defined on Y takes the values ∞ in the classical dual
problem, which corresponds in our problem to ψ having components equal to∞, in
this case it is not clear what the meaning of F ∗(ψ) should be. We hope to explore
this question in a future work.

Proposition 3.5. (1) If c(·, yj) is lower semicontinuous for each j and (ϕ,ψ) ∈
Cb(X)× RN is any maximizing pair in (3.1), then ϕ ≡ ψc∗ on sptµ.

(2) If c(·, yj) is uniformly continuous and bounded for each j, then there exists
at least one maximizer in Cb(X) × RN of the dual problem (3.1) that is a
c-conjugate pair.

Proof. (1) Let (ϕmax, ψmax) be a maximizing pair. Recall that −ϕmax ≤ −ψc
∗

max on
X. Since −ψc∗max can be written as a finite minimum of lower semicontinous func-
tions, it is also lower semicontinuous, then the set {−ϕmax < −ψc

∗

max} is open; in
particular if the inequality −ϕmax < −ψc

∗

max is strict at any point in sptµ, it holds
on a neighborhood relatively open in X. Then we would have −

∫
X
ϕmax dµ −

F ∗(ψmax) < −
∫
X
ψc
∗

max dµ− F ∗(ψmax), contradicting that (ϕmax, ψmax) is a maxi-

mizing pair. Thus we must have ϕmax ≡ ψc
∗

max on sptµ.
(2) Suppose c(·, yj) is uniformly continuous and bounded for each j and let

(ϕk, ψk) ∈ L1(µ) × RN be an admissible, maximizing sequence for (3.1). We may
assume ϕk = ψc

∗

k and ψk = ψc
∗c
k for this sequence as −

∫
X
ϕk dµ ≤ −

∫
X
ψc
∗

k dµ and

−F ∗(ψk) = inf
λ∈dom(F )

(〈λ,−ψk〉+ F (λ))

≤ inf
λ∈dom(F )

(〈λ,−(ψc
∗c
k )〉+ F (λ))

= −F ∗(ψc
∗c
k ),

using that λj ≥ 0 for all λ ∈ dom(F ) and −ψk ≤ −ψc
∗c
k componentwise; in partic-

ular we may assume each ϕk ∈ Cb(X). Since (ψk + r1)c
∗
(x) = ψc

∗

k (x) − r for any

r, the above along with (3.3) implies that replacing ψk by (ψk + r1)c
∗c and taking

ϕk = (ψk + r1)c
∗

does not reduce the values of −
∫
X
ϕk dµ − F ∗(ψk) for each k,

hence we may assume ϕk(x0) = 0 for all k, for some fixed x0 ∈ X. It can then
be seen that boundedness and uniform continuity of the c(·, yj) are enough to ob-
tain boundedness and equicontinuity of {ϕk}∞k=1 as in the proof of [10, Proposition
1.11] hence we can conclude existence of a subsequence, that we do not relabel, of
(ϕk, ψk) that converges (ϕk uniformly on X and ψk in RN ) to some (ϕmax, ψmax).



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 11

Since −F ∗ is a concave function, finite on all of RN by compactness of dom(F ), it is
continuous on RN , hence we obtain that (ϕmax, ψmax) is a maximizer in (3.1). We
can replace the pair by (ψc

∗

max, ψ
c∗c
max) which only increases the value of the associated

functional, hence there exists at least one c-conjugate maximizing pair. �

Remark 3.6. If F is lower semicontinuous but not convex, we may not ob-
tain strong duality, however it is easy to see that the duality gap is bounded by
‖F − F ∗∗‖L∞(dom(F )∪dom(F∗∗)), when the minimal value is finite and c is lower
semicontinuous. Let mF and mF∗∗ denote the minimal values in (1.3) with stor-
age fee functions F and F ∗∗ respectively, assume mF < ∞, and MF denote the
supremum in the dual problem (3.1) associated to F . Since F ∗∗ ≤ F , we also have
mF∗∗ < ∞. Then by strong duality combined with Proposition 5.1 below, we see
(since F ∗ = F ∗∗∗)

0 ≤ mF −MF = mF −MF∗∗ = mF −mF∗∗ ≤ ‖F − F ∗∗‖L∞(dom(F )∪dom(F∗∗)).

This bound is essentially sharp, as the following proposition (whose proof we defer
to the appendix) illustrates.

Proposition 3.7. Suppose F : Λ → R is L-Lipschitz. Then for each Y =
{yj}Nj=1 ⊂ Rn satisfying mini 6=j |yi−yj | > 2

√
L, there exists a µ ∈ P(Rn) such that

mF −MF = ‖F − F ∗∗‖L∞(Λ), where we take the cost function c(x, y) = |x− y|2.

3.1. Relationship with classical Kantorovich duality. The dual problem (3.1)
bears many similarities to Kantorovich’s dual problem for the classical optimal
transport problem, and it is natural to explore relationships between maximizers of
the two problems; we do so in this subsection. We recall the classical dual problem
here for clarity.

Definition 3.8 ([11, Theorem 1.3]). If µ, ν are Borel probability measures on X
and Y respectively and c a Borel measurable cost on X × Y , Kantorovich’s dual
problem is to find

sup
{
−
∫
X

ϕdµ−
∫
Y

ψdν : (ϕ,ψ) ∈ L1(µ)× L1(ν),

− ϕ(x)− ψ(y) ≤ c(x, y), ∀(x, y) ∈ X × Y
}
.

(3.5)

First recall the definition.

Definition 3.9 ([9, Section 23]). If F : RN → R ∪ {∞} is a convex function, its
subdifferential at a point λ0 ∈ RN is defined as

∂F (λ0) := {ψ ∈ RN : F (λ) ≥ F (λ0) + 〈λ− λ0, ψ〉,∀λ ∈ RN}.

Next, we prove a key lemma.

Lemma 3.10. Suppose c is lower semicontinuous, there exists a real valued up-
per semicontinuous function a ∈ L1(µ) with c(x, yj) ≥ a(x) for all x and j, and
(γmin, λmin) ∈ Π(µ, νλmin) × Λ are a minimizing pair in the primal problem (1.3).
Then if there exists a (ϕmax, ψmax) ∈ L1(µ) × RN which is a maximizing pair in
the dual problem (3.1), we must have F (λmax) <∞ and

−F ∗(ψmax) = −〈λmin, ψmax〉+ F (λmin)

or equivalently by [9, Theorem 23.5], ψmax ∈ ∂F (λmin).



12 M. BANSIL, J. KITAGAWA EJDE-2023/22

Proof. Let (γmin, λmin) and (ϕmax, ψmax) respectively be minimizing and maximiz-
ing pairs in the primal problem (1.3) and dual problem (3.1). By definition of the
Legendre transform, we have

−F ∗(ψmax) = inf
λ∈Λ

(−〈λ, ψmax〉+ F (λ)) ≤ −〈λmin, ψmax〉+ F (λmin).

For the opposite inequality, using Theorem 3.3 we have∫
X×Y

c dγmin + F (λmin) = sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− F ∗(ψ)
)

= sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ+ inf
λ∈Λ

(−〈λ, ψ〉+ F (λ))
)

≤ sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− 〈λmin, ψ〉
)

+ F (λmin)

≤
∫
X×Y

c dγmin + F (λmin).

Thus we have

−
∫
X

ϕmax dµ− F ∗(ψmax) = sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− F ∗(ψ)
)

= sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− 〈λmin, ψ〉+ F (λmin)
)

≥ −
∫
X

ϕmax dµ− 〈λmin, ψmax〉+ F (λmin),

since ϕmax ∈ L1(µ), this yields −F ∗(ψmax) = −〈λmin, ψmax〉 + F (λmin). Since F ∗

is finite everywhere, we have F (λmax) <∞. �

Corollary 3.11. Assume the same conditions on c as Lemma 3.10. Then:

(1) If (γmin, λmin) ∈ Π(µ, νλmin
)× Λ are a minimizing pair in the primal prob-

lem (1.3), then any maximizer of (3.1) is a maximizer in the classical
Kantorovich dual problem with source measure µ and target measure νλmin

.

(2) If there is a λmin ∈ Λ such that (ϕ̂max, ψ̂max) is a maximizer in the classical
Kantorovich dual problem with source measure µ and target measure νλmin

and ψ̂max ∈ ∂F (λmin), then (ϕ̂max, ψ̂max) is also a maximizer in the dual
problem (3.1). Moreover, if γmin is a minimizer of the classical Kantorovich
problem (1.4) between µ and νλmin , then (γmin, λmin) is a minimizer in (1.3).

Proof. (1) Let (γmin, λmin) ∈ Π(µ, νλmin
) × Λ be a minimizing pair in the primal

problem (1.3) and (ϕmax, ψmax) be a maximizer of (3.1). Then by Theorem 3.3 and
Lemma 3.10,

∫
X×Y c dγmin+F (λmin) = −

∫
X
ϕmax dµ−F ∗(ψmax) = −

∫
X
ϕmax dµ−

〈λmin, ψmax〉+ F (λmin), proving the first claim.

(2) Now suppose λmin ∈ RN and (ϕ̂max, ψ̂max) are as in claim (2) above; by [12,
Theorem 4.1] there exists γmin ∈ Π(µ, νλmin) minimizing (1.4). By [12, Theorem
5.10 (i)] and [9, Theorem 23.5],∫

X×Y
c dγmin + F (λmin) = −

∫
X

ϕ̂max dµ− 〈λmin, ψ̂max〉+ F (λmin)

= −
∫
X

ϕ̂max dµ− F ∗(ψ̂max),



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 13

hence (ϕ̂max, ψ̂max) maximizes (3.1). Theorem 3.3 then shows (γmin, λmin) is a
minimizer in (1.3). �

4. Relationship between dual and primal optimizers

In this section we work towards a sharp first order condition characterizing op-
timizers in (3.1) and (1.3), along with uniqueness of minimizers under some mild
conditions.

Proposition 4.1. Suppose c is lower semicontinuous, there exists a real valued
upper semicontinuous function a ∈ L1(µ) with c(x, yj) ≥ a(x) for all x and j. Also
let (γmin, λmin) ∈ Π(µ, νλmin) × Λ and (ϕmax, ψmax) ∈ L1(µ) × RN be extremizers

respectively in (1.3) and (3.1). If λjmin > 0 for some 1 ≤ j ≤ N , then we must have(
ψc
∗c

max

)j
= ψjmax for that index j.

Proof. Suppose λjmin > 0 for some 1 ≤ j ≤ N . Recall that by Proposition 3.5 (1) we

must have ϕmax ≡ ψc
∗

max on sptµ, and ψkmax ≥ (ψc
∗c

max)k for all 1 ≤ k ≤ N . Suppose
by contradiction there is a strict inequality for the index j. Since (ψc

∗

max, ψ
c∗c
max) is

also a maximizer in (3.1) we would then obtain

−F ∗(ψc
∗c

max) = −〈λmin, ψ
c∗c
max〉+ F (λmin)

= −
∑
k 6=j

(ψc
∗c

max)kλkmin − (ψc
∗c

max)jλjmin + F (λmin)

> −
∑
k 6=j

ψkmaxλ
k
min − ψjmaxλ

j
min + F (λmin)

= −〈λmin, ψmax〉+ F (λmin) = −F ∗(ψmax).

However, this contradicts that (ϕmax, ψmax) is a maximizer, thus we must have
ψmax = (ψc

∗c
max). �

Next we aim to start with a maximizer in the dual problem and construct a
minimizer in the primal problem. To do so, we need an assumption about when
minimizers in the classical Kantorovich problem (1.4) can be written as solutions
to the Monge problem (1.1).

Definition 4.2. If µ ∈ P(X), we say the cost function c satisfies the condition
(µ-Twist) if for each 1 ≤ j ≤ N , the function c(·, yj) ∈ L1(µ) is lower semicon-
tinuous, there exists a real valued upper semicontinuous function a ∈ L1(µ) with
c(x, yj) ≥ a(x) for all x ∈ X, and for any u ∈ R, and each j 6= k, we have

µ({x ∈ X : c(x, yj) = c(x, yk) + u}) = 0. (µ-Twist)

Remark 4.3. If c satisfies (µ-Twist) then we can apply [12, Theorem 5.30] to
find the Kantorovich problem (1.4) has a unique solution for any choice of ν = νλ,
λ ∈ Λ, which can be written in the form (Id×T )#µ where T is a mapping defined
µ-a.e., that is in turn a solution to the Monge problem (1.1). In particular, under
these conditions, a solution γ of (1.4) must be supported on the graph of a mapping
from X to Y that is single valued µ-a.e. We note that when X is a subset of a
smooth Riemannian manifold and µ is absolutely continuous with respect to the
Riemannian volume, (µ-Twist) holds under what is usually referred to as the “twist”
or “bi-twist” condition (see [12, p. 234]).



14 M. BANSIL, J. KITAGAWA EJDE-2023/22

Now let ψ ∈ RN and define λ ∈ RN by

λj = µ
(
{x ∈ X : ψc

∗
(x) = −c(x, yj)− ψj}

)
for each j. When c satisfies (µ-Twist), it is clear that for j1 6= j2,

µ({x ∈ X : ψc
∗
(x) = −c(x, yj1)− ψj1} ∩ {x ∈ X : ψc

∗
(x) = −c(x, yj2)− ψj2})

≤ µ({x ∈ X : −c(x, yj1)− ψj1 = −c(x, yj2)− ψj2}) = 0,

thus in particular λ ∈ Λ, and for µ-a.e. x there is a unique index j such that
ψc
∗
(x) = −c(x, yj) − ψj . Defining Tψ : X → Y by Tψ(x) = yj whenever j is the

unique index associated to x, it is clear that (Tψ)#µ = νλ, hence by [12, Remark
5.13], we can see that γλ := (Id×Tψ)#µ is a solution to the Kantorovich problem
(1.4) with ν = νλ.

Proposition 4.4. Suppose c satisfies (µ-Twist). Also suppose (ϕ̂, ψ̂) is a maxi-

mizing pair in the dual problem (3.1), define λ̃ ∈ Λ by

λ̃j := µ
(
{x ∈ X : ϕ̂(x) = −c(x, yj)− ψ̂j}

)
,

and take γmin ∈ Π(µ, νλ̃) to be the (unique) solution of the classical Kantorovich

problem (1.4) with ν = νλ̃. Then (γmin, λ̃) is a minimizing pair in the primal
problem (1.3).

Proof. Let (ϕ̂, ψ̂) be a maximizing pair in the dual problem. By Proposition 3.5

we see that ϕ̂ ≡ ψ̂c∗ , and we easily see that replacing ψ̂ with ψ̂c
∗c does not change

the vector λ̃, so we make this replacement.

Since −ϕ̂(x)− ψ̂j ≤ c(x, yj) for all x, j, by Kantorovich duality in the classical
optimal transport problem [11, Theorem 1.3], we have for any λ ∈ Λ that

`(λ) := −
∫
X

ϕ̂ dµ− 〈λ, ψ̂〉 ≤ min
γ∈Π(µ,νλ)

∫
X×Y

c dγ =: C(λ) <∞,

where finiteness comes from c(·, yj) ∈ L1(µ) for each j. At the same time by strong
duality, Theorem 3.3,

inf
λ∈Λ

[F (λ) + `(λ)] = −
∫
X

ϕ̂ dµ+ inf
λ∈Λ

[F (λ)− 〈λ, ψ̂〉]

= −
∫
X

ϕ̂ dµ− F ∗(ψ̂)

= min
λ∈Λ, γ∈Π(µ,νλ)

(∫
X×Y

c dγ + F (λ)
)

= min
λ∈Λ

[F (λ) + C(λ)].

Thus we obtain that F + ` ≤ F + C pointwise everywhere on Λ, and the above
calculation shows that F + ` attains its minimum value over Λ, at the same point
as F + C; say this point is λmin.

Arguing as in the proof of [10, Proposition 7.19] (which can be carried out under
the assumption (µ-Twist), note the exact form of the cost function is immaterial),

we find that C is strictly convex on Λ. By Remark 4.3 and the choice of λ̃, we have
C(λ̃) = `(λ̃), hence for any t ∈ [0, 1] we must have

`((1− t)λmin + tλ̃) ≤ C((1− t)λmin + tλ̃)



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 15

≤ (1− t)C(λmin) + tC(λ̃)

= (1− t)`(λmin) + t`(λ̃)

= `((1− t)λmin + tλ̃),

i.e., ` ≡ C on the segment [λmin, λ̃].
However the only way for the strictly convex function C to equal an affine function

on [λmin, λ̃] is if λmin = λ̃. It is then clear that (γ̃, λ̃) is a minimizer in the primal
problem (1.3). �

The strict convexity of C demonstrated in the above proof immediately yields
the following corollary.

Corollary 4.5. If c satisfies (µ-Twist), minimizers in the primal problem (1.3)
are unique.

Using the above properties of dual and primal optimizers, we obtain a charac-
terization for optimizers in both problems.

Theorem 4.6. Assume c satisfies (µ-Twist). If (ϕ̂, ψ̂) is a maximizing pair in the

dual problem (3.1) and (γ̃, λ̃) is a minimizer in the primal problem (1.3), ψ̂ and λ̃
satisfy the conditions:

(i) ψ̂ ∈ ∂F (λ̃)

(ii) λ̃j = µ
(
{x ∈ X : −c(x, yj)− ψ̂j = ψ̂c

∗
(x)}

)
.

Furthermore, if λ̃j > 0 for some 1 ≤ j ≤ N , we have

(iii) ψ̂j =
(
ψ̂c
∗c
)j

.

Conversely, if λ̃ ∈ Λ and ψ̂ ∈ RN are such that conditions (i) and (ii) hold,

then defining Tψ̂ as in Remark 4.3, the pairs (ψ̂c
∗
, ψ̂) and ((Id×Tψ̂)#µ, λ̃) are

maximizing and minimizing pairs in the dual and primal problem respectively.

Proof. Under the hypotheses above “conversely”, conditions (i) and (ii) follow from
Lemma 3.10, Proposition 4.4, and Corollary 4.5. Condition (iii) follows from Propo-
sition 4.1.

Now suppose ψ̂ ∈ RN , λ̃ ∈ Λ satisfy (i) and (ii). Then

sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− F ∗(ψ)
)
≥ −

∫
X

ψ̂c
∗
dµ− F ∗(ψ̂)

= −
∫
X

ψ̂c
∗
dµ− 〈λ̃, ψ̂〉+ F (λ̃)

(4.1)

where this last equality follows from condition (i) and [9, Theorem 23.5]. Let Tψ̂
be defined as in Remark 4.3, by condition (ii), we see that γ̃ := (Id×Tψ̂)#µ is

a minimizer in the classical Kantorovich problem (1.4) with ν = νλ̃. Let x ∈
X be such that Tψ̂(x) is well-defined. By definition, this means that ψ̂c

∗
(x) +

ψ̂j = −c(x, yj) where yj = Tψ̂(x). Since (see Remark 4.3) the set of such x has

full µ measure, the union of (x, Tψ̂(x)) over such x has full γ̃ measure. Thus

by [12, Theorem 5.10 and Remark 5.13], we have that (ψ̂c
∗
, ψ̂) is a maximizer in

the classical Kantorovich dual problem, and in particular −
∫
X
ψ̂c
∗
dµ − 〈λ̃, ψ̂〉 =



16 M. BANSIL, J. KITAGAWA EJDE-2023/22

infγ∈Π(µ,νλ̃)

( ∫
X×Y c dγ

)
. Thus we can calculate,

−
∫
X

ψ̂c
∗
dµ− 〈λ̃, ψ̂〉+ F (λ̃) = inf

γ∈Π(µ,νλ̃)

(∫
X×Y

c dγ
)

+ F (λ̃)

≥ inf
λ∈Λ, γ∈Π(µ,νλ)

(∫
X×Y

c dγ + F (λ)
)

≥ sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− F ∗(ψ)
)
.

Combining this with (4.1), we have∫
X×Y

cdγ̃ + F (λ̃) = inf
γ∈Π(µ,νλ̃)

(∫
X×Y

c dγ
)

+ F (λ̃)

= inf
λ∈Λ,γ∈Π(µ,νλ)

(∫
X×Y

c dγ + F (λ)
)

hence (γ̃, λ̃) is a minimizing pair in the primal problem. The above calculations
also yield

sup
−ϕ−ψ≤c

(
−
∫
X

ϕdµ− F ∗(ψ)
)

= −
∫
X

ψ̂c
∗
dµ− F ∗(ψ̂),

thus (ψ̂c
∗
, ψ̂) is a maximizing pair in the dual problem. �

5. Stability of F

In this section we show two kinds of stability for our primal problem (1.3). The
first is stability of minimizers under perturbations of the storage fee function F
when the finite target set Y is fixed. The second is Γ-convergence of a sequence
of objective functionals obtained when one takes a sequence of target sets Yk that
become suitably dense in some continuous domain Y .

5.1. Stability for a fixed finite target. First we estimate the change in the
minimum value of the problem.

Proposition 5.1. Let F1 and F2 : RN → R ∪ {∞} be lower semicontinuous and
proper, c be lower semicontinuous and bounded, and write mFi for the minimum
value attained in (1.3) with some fixed measure µ and the choice F = Fi, i = 1 or
i = 2. Then if both of mFi are finite,

‖mF1
−mF2

| ≤ ‖F1 − F2‖L∞(dom(F1)∪dom(F2))

Proof. Let the pair (γ̃2, λ̃2) achieve the minimum value in mF2
, which exists by

Theorem 2.3. Then both
∫
X×Y cdγ̃2 and F2(λ̃2) are finite. If F1(λ̃2) =∞ we have

‖F1 − F2‖L∞(dom(F1)∪dom(F2)) = ∞ and the desired inequality is trivial, thus we

may assume F1(λ̃2) is finite. Then

mF1
−mF2

≤
(∫

X×Y
cdγ̃2 + F1(λ̃2)

)
−
(∫

X×Y
cdγ̃2 + F2(λ̃2)

)
= F1(λ̃2)− F2(λ̃2)

≤ ‖F1 − F2‖L∞(dom(F1)∪dom(F2)).

The same argument reversing the roles of F1 and F2 completes the proof. �



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 17

The above statement shows that if Fk converges to F uniformly, then mFk con-
verges to mF . Next we prove that the minimizing plans weakly converge to a
minimizer of the original problem.

Theorem 5.2. Suppose c satisfies (µ-Twist). Let (γ̃, λ̃) and (γ̃k, λ̃k) minimize
(1.3) with storage fee functions F and Fk for each k respectively, where F , Fk are
all proper, convex functions with compact essential domains contained in Λ. If

lim
k→∞

‖Fk − F‖L∞(dom(Fk)∪dom(F )) = 0,

then λ̃k converges to λ̃, and γ̃k converges weakly to γ̃.

Proof. Let CF (λ) = infγ∈Π(µ,νλ)

∫
X×Y c dγ + F (λ) and define CFk(λ) analogously.

By the proof of Proposition 4.4 and Corollary 4.5, we see that CF and CFk are

strictly convex functions on Λ each of which have unique minimizers, given by λ̃
and λ̃k respectively. By (µ-Twist) and the properness of F and Fk, all CFk(λ̃k) and

CF (λ̃) are finite, then by Proposition 5.1,∣∣CF (λ̃k)− CF (λ̃)
∣∣ ≤ |CFk(λ̃k)− CF (λ̃)|+ |CFk(λ̃k)− CF (λ̃k)|

= |mFk −mF |+ |Fk(λ̃k)− F (λ̃k)|
≤ 2‖Fk − F‖L∞(dom(Fk)∪dom(F )) → 0, k →∞.

By the compactness of Λ, any subsequence of {λ̃k}∞k=1 has a convergent subse-
quence, by the above calculation and strict convexity of CF on Λ all of these sub-
sequential limits must be λ̃, hence we must have limk→∞ λ̃k = λ̃.

Now suppose by contradiction that γ̃k does not converge weakly to γ̃. Since Π(µ)
is weakly compact by Lemma 2.2, we can extract a subsequence (which we do not
relabel) which converges weakly to some limiting measure that is not γ̃, say γ̂. By

the above paragraph combined with (2.1) we have λ̃ = limk→∞ λ̃k = λ̂ where λ̂ is
such that the right marginal of γ̂ is νλ̂. We then have∫

cdγ̂ + F (λ̂)

=

∫
cdγ̃k + Fk(λ̃k) +

(
F (λ̂)− F (λ̃k)

)
+
(
F (λ̃k)− Fk(λ̃k)

)
+
(∫

cdγ̂ −
∫
cdγ̃k

)
≤ mFk +

(
F (λ̂)− F (λ̃k)

)
+ ‖Fk − F‖L∞(dom(Fk)∪dom(F )) +

(∫
cdγ̂ −

∫
cdγ̃k

)
.

Letting k go to infinity we see that
∫
cdγ̂ + F (λ̂) ≤ mF by Proposition 5.1, the

lower semicontinuity of F , and the fact that γ̃k converges weakly to γ̂. Hence γ̂ is
a minimizer and by Corollary 4.5 we see that γ̂ = γ̃ as desired. �

Γ-convergence. We now turn to Γ-convergence. For this subsection, we assume
(X, dX) is a Polish space which may not be compact, and we will suppose (Y, dY )
is a bounded Polish space, not necessarily finite.

Definition 5.3. Recall that if Ω is a first countable topological space and Gk : Ω→
R∪{±∞} is a sequence of functions, we say the Gk Γ-converge to G : Ω→ R∪{±∞}
if

(1) G(ω) ≤ lim infk→∞Gk(ωk) whenever limk→∞ ωk = ω.



18 M. BANSIL, J. KITAGAWA EJDE-2023/22

(2) For any ω ∈ Ω, there exists a recovery sequence {ωk}∞k=1 s.t. limk→∞ ωk =
ω and
G(ω) ≥ lim supk→∞Gk(ωk).

Before stating our second stability result, we recall some classical definitions in
optimal transport theory.

Definition 5.4. If (X, dX) is a Polish space, we write for the set of probability
measures with finite moment,

P1(X) := {µ ∈ P(X) : ∃x0 ∈ X with

∫
X

dX(x, x0) dµ(x) <∞}.

Also for µ1, µ2 ∈ P1(X), we write

W dX
1 (µ1, µ2) := inf

γ∈Π(µ1,µ2)

∫
X×X

dX(x1, x2) dγ(x1, x2).

It is well known that W dX
1 is a metric on P1 (see [12, Chapter 6]).

Our second stability result is as follows.

Theorem 5.5. Suppose there is a sequence of cost functions ck ∈ Cb(X × Y )
converging uniformly to some c ∈ Cb(X × Y ), and F : P(Y ) → R ∪ {±∞} is
sequentially weakly continuous. Also suppose for each k ∈ N, the finite set Yk :=
{yk,j}Nkj=1 ⊂ Y is an εk-net of Y (i.e., for any y ∈ Y there is a yk,j such that

dY (y, yk,j) < εk) with εk ↘ 0, and define the sets

Πk(µ) := {γ ∈ Π(µ) : spt((πY )#γ) ⊂ Yk}.
Also define the functionals Ck, C : P(X × Y )→ R ∪ {±∞} by

Ck(γ) :=

{∫
X×Y ck dγ + F((πY )#γ), γ ∈ Πk(µ),

∞, otherwise

C(γ) :=

{∫
X×Y c dγ + F((πY )#γ), γ ∈ Π(µ),

∞, otherwise

Then

(1) Ck Γ-converges to C, where the underlying topology on P(X × Y ) is that of
weak convergence of measures.

(2) Suppose {µk}∞k=1 ⊂ P1(X) converges in W dX
1 to µ ∈ P1(X). Then if each

Πk(µ) is replaced by Πk(µk) in the definition of Ck, again Ck Γ-converges
to C.

Remark 5.6. At first glance, the condition of weak continuity of F may seem
restrictive. However, by [4, Remark 1.25 and Proposition 1.28], if Ck Γ-converges
to C, we must have that F is weakly lower semicontinuous. At the same time,
considering the example where F is 0 for some fixed measure which is not discrete,
and 1 otherwise shows that weak lower semicontinuity is not enough to produce
a recovery sequence to obtain Γ-convergence. Essentially, one would need that for
any measure ν, there is a sequence of discrete measures weakly converging to ν
along which F is continuous, which is not so far off from simply requiring weak
continuity.

Before giving the proof, we recall a form of disintegration of measures which
follows from [7, Chapter III-70 and 72].



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 19

Theorem 5.7 (Disintegration of measures). If X1, X2 are Polish spaces, for any
ρ ∈ P(X1 ×X2) there is a map X1 3 x 7→ ρx ∈ P(X2), defined uniquely (πX1)#ρ-
a.e., such that for any bounded or nonnegative Borel function ϕ on X1 ×X2, the
map X1 3 x1 7→

∫
X2
ϕ(x1, x2)dρx1(x2) is Borel, and∫

X1×X2

ϕdρ =

∫
X1

∫
X2

ϕ(x1, x2)dρx1(x2)d((πX1)#ρ)(x1).

Proof of Theorem 5.5. First suppose a sequence γk weakly converges to some γ ∈
P(X × Y ). If (πX)#γ 6= µ, since the sequence of left marginals (πX)#γk converge
weakly to (πX)#γ, we must have that (πX)#γk 6= µ (or 6= µk in case (2)) for all k
sufficiently large. Thus in this case we have

lim inf
k→∞

Ck(γk) =∞ ≥ C(γ).

If (πX)#γ = µ, since the sequence of right marginals (πY )#γk converge weakly to
(πY )#γ,

lim inf
k→∞

Ck(γk) = lim inf
k→∞

(∫
X×Y

ck dγk + F((πY )#γk)
)

≥
∫
X×Y

c dγ + F((πY )#γ) = C(γ).

Next we fix a γ ∈ P(X × Y ), we aim to produce a recovery sequence. If the left
marginal of γ is not µ, we have C(γ) = ∞ and we can take the constant sequence
{γ} as the recovery sequence, thus assume (πX)#γ = µ. For each k ∈ N and

1 ≤ j ≤ Nk, we define K̃k,j as the Voronoi cell associated with yk,j , that is,

K̃k,j := {y ∈ Y : dY (y, yk,j) ≤ min1≤i≤Nk dY (y, yk,i)}. Then, we define

Kk,1 := K̃k,1, Kk,j := K̃k,j \ ∪j−1
i=1Kk,i, 2 ≤ j ≤ Nk,

and the maps ϕk : Y → Yk by ϕk(x) := yk,j whenever x ∈ Kk,j , this map is

well-defined by the disjointness of the collection {Kk,j}Nkj=1 for each fixed k.

We will first consider case (1). Define γk := (πX×(ϕk◦πY ))#γ ∈ P(X×Y ). Then
(πX)#γk = (πX)#γ = µ for each k, and since the range of ϕk is contained in Yk, it
is clear that spt((πY )#γk) ⊂ Yk hence γk ∈ Πk(µ). Now suppose ϕ ∈ Cb(X × Y ) is
L-Lipschitz for some L > 0, and fix y ∈ Y with y ∈ Ki,j1(k) for some index j1(k).
Since Yk is an εk net of Y , for some yi,j2(k) ∈ Yk we have dY (y, yi,j2(k)) ≤ εk. Hence
for any x ∈ X,

|ϕ(x, ϕk(y))− ϕ(x, y)| ≤ LdY (y, ϕk(y)) = LdY (y, yi,j1(k))

≤ LdY (y, yi,j2(k)) < Lεk,
(5.1)

which proves limk→∞ ϕ(x, ϕk(y)) = ϕ(x, y) for all (x, y) ∈ X × Y where the con-
vergence is uniform over X × Y . Since γ is a probability measure, we have

lim
k→∞

∫
X×Y

ϕ(x, y) dγk(x, y) = lim
k→∞

∫
X×Y

ϕ(x, ϕk(y)) dγ(x, y) =

∫
X×Y

ϕdγ.

As it is sufficient to test for convergence against bounded, Lipschitz functions (see
[3, Remark 8.3.1]) this proves weak convergence of γk to γ; in particular it also
proves weak convergence of the (πY )#γk to (πY )#γ. Thus the uniform convergence
of the ck and weak continuity of F gives that

lim sup
k→∞

Ck(γk) = lim sup
k→∞

(∫
X×Y

ck dγk + F((πY )#γk)
)
≤ C(γ).



20 M. BANSIL, J. KITAGAWA EJDE-2023/22

Now we consider case (2). Since µ and all µk have finite first moments, there exist

σk ∈ Π(µ, µk) which achieve the minimum in the definition of W dX
1 (µ, µk) (say, by

[12, Theorem 4.1]). It is clear that the unique minimizer achieving W dX
1 (µ, µ) = 0

is (Id× Id)#µ, while for some x0 ∈ X,

sup
k

∫
X×X

dX(x1, x2) dσk(x1, x2) ≤ sup
k

∫
X

dX(x, x0) dµk(x)+

∫
X

dX(x, x0) dµ(x) <∞,

hence by [12, Theorem 5.20] we see σk converges weakly to (Id× Id)#µ. Now if σxk
and γx are the disintegrations of σk and γ respectively, with respect to their left
marginals (both µ) as given in Theorem 5.7, we define a linear functional γk acting
on bounded Borel functions ϕ on X × Y by

γk(ϕ) :=

∫
X

∫
Y

∫
X

ϕ(z, y) dσxk(z)d((ϕk)#γ
x)(y) dµ(x).

We claim that γk ∈ P(X × Y ). Fix ε > 0. If ψ ∈ Cb(Y ) is L-Lipschitz, by (5.1)
we have

∣∣ ∫
Y
ψd((ϕk ◦ πY )#γ) −

∫
Y
ψd((πY )#γ)

∣∣ ≤ Lεk, and again by [3, Remark
8.3.1] we see (ϕk ◦πY )#γ weakly converges to (πY )#γ. Since {µk}∞i=1 is also weakly
convergent, for any ε > 0, by Prokhorov’s theorem there are compact sets K1 ⊂ X
and K2 ⊂ Y such that µk(X \ K1) < ε and (ϕk ◦ πY )#γ(Y \ K2) < ε for all k.
Then, if ϕ ∈ Cb(X × Y ) is identically zero on the compact set K := K1 ×K2, we
have

γk(ϕ) ≤ sup |ϕ|
∫
X

∫
Y \K2

∫
X\K1

dσxk(z)d((ϕk)#γ
x)(y) dµ(x)

= sup |ϕ|
∫
X

σxk(X \K1)γx(ϕ−1
k (Y \K2)) dµ(x)

≤ sup |ϕ|
(∫

X

σxk(X \K1)2 dµ(x)
)1/2(∫

X

γx(ϕ−1
k (Y \K2))2 dµ(x)

)1/2

≤ sup |ϕ|
(∫

X

σxk(X \K1) dµ(x)
)1/2(∫

X

γx(ϕ−1
k (Y \K2)) dµ(x)

)1/2

= sup |ϕ|
√
σk(X × (X \K1))

√
γ(X × ϕ−1

k (Y \K2))

= sup |ϕ|
√
µk(X \K1)

√
((ϕk ◦ πY )#γ)(Y \K2)

≤ ε sup |ϕ|,
where we have used Hölder’s inequality for the third line, and that σxk and γx

are probability measures to obtain the inequality in the fourth line. Hence by [3,
Theorem 7.10.6], γk is a Radon measure on X ×Y , and it is clear that γk ≥ 0 with
γk(X × Y ) = 1, hence the claim is proved. Next, for any Borel ψ : X → [0,∞] we
have ∫

X×Y
ψ(x) dγk(x, y) =

∫
X

∫
Y

∫
X

ψ(z) dσxk(z)d((ϕk)#γ
x)(y) dµ(x)

=

∫
X

∫
X

ψ(z) dσxk(z) dµ(x)

=

∫
X×X

ψ(x2) dσk(x1, x2)

=

∫
X

ψ(x) dµk(x),



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 21

hence the left marginal of γk is µk and we have γk ∈ Πk(µk), in particular Ck(γk)
is finite. Finally suppose ϕ ∈ Cb(X × Y ) is L-Lipschitz. Then by (5.1),

∣∣ ∫
X×Y

ϕdγk −
∫
X×Y

ϕdγ
∣∣

≤
∣∣∣ ∫
X

∫
Y

∫
X

ϕ(z, ϕk(y)) dσxk(z) dγx(y) dµ(x)

−
∫
X

∫
Y

∫
X

ϕ(z, y) dσxk(z) dγx(y) dµ(x)
∣∣∣

+
∣∣∣ ∫
X

∫
Y

∫
X

ϕ(z, y) dσxk(z) dγx(y) dµ(x)−
∫
X

∫
Y

ϕ(x, y) dγx(y) dµ(x)
∣∣∣

≤
∫
X

∫
Y

∫
X

|ϕ(z, ϕk(y))− ϕ(z, y)| dσxk(z) dγx(y) dµ(x)

+

∫
X

∫
Y

∫
X

|ϕ(z, y)− ϕ(x, y)| dσxk(z) dγx(y) dµ(x)

≤ Lεk + L

∫
X

∫
Y

∫
X

dX(z, x) dσxk(z) dγx(y) dµ(x)

= L(εk +

∫
X×X

dX(z, x) dσk(z, x))

= L(εk +W dX
1 (µk, µ))→ 0

as k →∞. Thus as in case (1), we see γk weakly converges to γ. A similar argument
yields lim supk→∞ Ck(γk) ≤ C(γ). This completes the proof of Γ-convergence in
both cases. �

6. Appendix

Proof of Proposition 3.7. Let us write R := mini6=j |yi − yj |. Let λ∞ ∈ Λ be such
that F (λ∞)− F ∗∗(λ∞) = ‖F − F ∗∗‖L∞(Λ), and define

µ =

N∑
i=1

λi∞1BR
4

(yi)(x)

|BR
4

(yi)|
dx.

Now suppose the pair (T̃ , λ̃) achieves the minimum in (1.2) with c(x, y) = |x− y|2,
storage fee function F , and this µ; since c satisfies (µ-Twist) such a pair exists

by Theorem 2.3 combined with Remark 4.3. We claim that λ̃ = λ∞. Let us
write Bi := BR/4(yi) for brevity, clearly the Bi are disjoint hence the map T
defined by T (x) = yi whenever x ∈ Bi is well-defined µ-a.e. We also see that

T#µ =
∑N
i=1 λ

i
∞δyi . Let us also write L̃i := T̃−1({yi}) which form a partition

up to sets of µ-measure zero. Then if x ∈ Bi with T̃ (x) = yj and i 6= j, we see

|x − T̃ (x)| ≥ |T (x) − T̃ (x)| − |x − T (x)| ≥ 3R/4, while for any j, λ̃j = µ(L̃j) =



22 M. BANSIL, J. KITAGAWA EJDE-2023/22∑N
i=1

λi∞|Bi∩L̃j |
|Bi| . Hence∫

(|x− T̃ (x)|2 − |x− T (x)|2) dµ(x)

=

N∑
i=1

λi∞
|Bi|

∑
j 6=i

∫
Bi∩L̃j

(|x− T̃ (x)|2 − |x− T (x)|2)dx

≥ R2

2

N∑
i=1

∑
j 6=i

λi∞|Bi ∩ L̃j |
|Bi|

=
R2

2

( N∑
i=1

N∑
j=1

λi∞|Bi ∩ L̃j |
|Bi|

−
N∑
i=1

λi∞|Bi ∩ L̃i|
|Bi|

)

=
R2

2

( N∑
j=1

λ̃j −
N∑
i=1

λi∞|Bi ∩ L̃i|
|Bi|

)

=
R2

2

(
1−

N∑
i=1

λi∞|Bi ∩ L̃i|
|Bi|

)
.

(6.1)

On the other hand,

|λ̃− λ∞|1 :=

N∑
j=1

|λ̃j − λj∞| =
N∑
j=1

∣∣∣ N∑
i=1

λi∞|Bi ∩ L̃j |
|Bi|

− λj∞
∣∣∣

=

N∑
j=1

∣∣∣∑
i 6=j

λi∞|Bi ∩ L̃j |
|Bi|

+ λj∞

( |Bj ∩ L̃j |
|Bj |

− 1
)∣∣∣

≤
N∑
j=1

∑
i6=j

λi∞|Bi ∩ L̃j |
|Bi|

+

N∑
j=1

λj∞

(
1− |Bj ∩ L̃j |

|Bj |

)

=

N∑
j=1

N∑
i=1

λi∞|Bi ∩ L̃j |
|Bi|

+ 1− 2

N∑
j=1

λj∞|Bj ∩ L̃j |
|Bj |

= 2
(

1−
N∑
j=1

λj∞|Bj ∩ L̃j |
|Bj |

)
.

Thus combining this with (6.1) we have

|λ̃− λ∞|1 ≤
4

R2

∫
(|x− T̃ (x)|2 − |x− T (x)|2) dµ(x)

≤ 4

R2
(F (λ∞)− F (λ̃))

≤ 4L

R2
|λ̃− λ∞| ≤ |λ̃− λ∞|.

(6.2)

In turn this implies that for at most one index i, we can have |λ̃i − λi∞| 6= 0.

However, since 1 =
∑
i λ̃

i =
∑
i λ

i
∞, this actually implies λ̃ = λ∞ as claimed. By

the uniqueness in Remark 4.3, this also shows T̃ ≡ T µ-a.e.
By [9, Corollary 13.3.3] and since F ∗∗∗ = F ∗, we see that F ∗∗ also has Lipschitz

constant L, then a calculation similar to (6.2) with F ∗∗ replacing F shows that the



EJDE-2023/22 AN OPTIMAL TRANSPORT PROBLEM 23

pair (T, λ∞) minimizes (1.2) with storage fee function F ∗∗. Thus, by the strong
duality Theorem 3.3 we have

mF −MF = mF −mF∗∗ = F (λ∞)− F ∗∗(λ∞) = ‖F − F ∗∗‖L∞(Λ).

�

7. Classical dual maximizers may not be dual maximizers

Example 7.1. Let X = R, N = 2, y1 = −1, y2 = 1, µ = 1[−1,−1/2]∪[1/2,1](x)dx,

and c(x, y) = |x−y|2/2. Also suppose F (λ1, λ2) = f(λ1) on Λ, where f is a smooth,
convex function with a strict minimum at 1/2, satisfying f(1 − λ) = f(λ) for all
λ ∈ [0, 1]. By Theorem 2.3 there is a minimizer (γ, λ) of (1.3), and by [11, Remark
2.19 (iv)], γ must be given by (Id×Tλ)#µ for some increasing map Tλ : R → R,
defined by

Tλ(x) =

{
−1, x ≤ −1 + λ1,

1, x > −1 + λ1,
if λ1 ≤

1

2
,

and

Tλ(x) =

{
−1, x ≤ λ1,

1, x > λ1,
if λ1 >

1

2
.

Then, if λ1 ≤ 1/2,∫
R
c(x, Tλ(x)) dµ(x) + F (λ)

=
1

2

(∫ −1+λ1

−1

(x+ 1)2dx+

∫ −1/2

−1+λ1

(x− 1)2dx+

∫ 1

1
2

(x− 1)2dx
)

+ f(λ1)

= f(λ1) +
λ2

1

3
− 2λ1

3
+

19

24
,

which is minimized at λ1 = 1/2. By symmetry the case λ1 ≥ 1/2 has a minimum
when λ1 = 1/2, hence λ = (1/2, 1/2), and the optimal map T := T(1/2,1/2) satisfies

T ([−1,−1/2]) = −1, T ([1/2, 1]) = 1. For ψ := (ψ1, ψ2) ∈ R2, let

ϕψ := max
(
− |x+ 1|2

2
− ψ1,−|x− 1|2

2
− ψ2

)
.

If ψ2−ψ1 ∈ [−1, 1], then − |x+1|2
2 −ψ1 ≥ − |x−1|2

2 −ψ2 on [−1,−1/2] and vice versa
on [1/2, 1]. Thus

−ϕψ(x)− ψ1 = c(x, T (x)), ∀x ∈ [−1,−1

2
],

−ϕψ(x)− ψ2 = c(x, T (x)), ∀x ∈ [
1

2
, 1],

and by [12, Remark 5.13], for all such ψ the pair (ϕψ, ψ) is a maximizer in the
classical dual problem from µ to 1

2 (δ−1 + δ1) (identifying ψ ∈ R2 with a function in

L1( 1
2 (δ−1 + δ1))).

By the choice of F , we see that ∂F (1/2, 1/2) = {(r, r) : r ∈ R}, which does not
contain all ψ as above. Hence by Lemma 3.10, not all classical dual maximizers are
maximizers in (3.1).



24 M. BANSIL, J. KITAGAWA EJDE-2023/22

Acknowledgments. J. Kitagawa was supported by the National Science Founda-
tion grants DMS-1700094 and DMS-2000128. Part of this research was performed
while J. Kitagawa was visiting the Institute for Mathematical and Statistical In-
novation (IMSI), while supported by the National Science Foundation (Grant No.
DMS-1929348). M. Bansil was supported by the National Science Foundation Grad-
uate Research Fellowship under Grant No. DGE-1650604.

References

[1] Mohit Bansil, Jun Kitagawa; A Newton Algorithm for Semidiscrete Optimal Transport with

Storage Fees, SIAM J. Optim. 31 (2021), no. 4, 2586–2613. MR 4329988

[2] Patrick Billingsley; Convergence of probability measures, second ed., Wiley Series in Proba-
bility and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999,

A Wiley-Interscience Publication. MR 1700749

[3] V. I. Bogachev; Measure theory. Vol. I, II, Springer-Verlag, Berlin, 2007. MR 2267655
[4] Andrea Braides; Γ-convergence for beginners, Oxford Lecture Series in Mathematics and its

Applications, vol. 22, Oxford University Press, Oxford, 2002. MR 1968440
[5] Guillaume Carlier, Lina Mallozzi; Optimal monopoly pricing with congestion and random

utility via partial mass transport, J. Math. Anal. Appl. 457 (2018), no. 2, 1218–1231.

MR 3705351
[6] Gianluca Crippa, Chloé Jimenez, Aldo Pratelli; Optimum and equilibrium in a transport

problem with queue penalization effect, Adv. Calc. Var. 2 (2009), no. 3, 207–246. MR 2537021

[7] Claude Dellacherie, Paul-André Meyer; Probabilities and potential, North-Holland Mathemat-
ics Studies, vol. 29, North-Holland Publishing Co., Amsterdam-New York, 1978. MR 521810

[8] Lina Mallozzi, Antonia Passarelli di Napoli; Optimal transport and a bilevel location-

allocation problem, J. Global Optim. 67 (2017), no. 1-2, 207–221. MR 3596835
[9] R. Tyrrell Rockafellar; Convex analysis, Princeton University Press, 1970.

[10] Filippo Santambrogio; Optimal transport for applied mathematicians, Progress in Nonlinear

Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015,
Calculus of variations, PDEs, and modeling. MR 3409718

[11] Cédric Villani; Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58,
American Mathematical Society, Providence, RI, 2003. MR 1964483 (2004e:90003)

[12] Cédric Villani; Optimal transport: Old and new, Grundlehren der Mathematischen Wis-

senschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag,
Berlin, 2009. MR 2459454 (2010f:49001)

Mohit Bansil

Department of Mathematics, University of California, Los Angeles, CA 90095, USA

Email address: mbansil@math.ucla.edu

Jun Kitagawa
Department of Mathematics, Michigan State University, 619 Red Cedar Road, C212
Wells Hall, East Lansing, MI 48824, USA

Email address: kitagawa@math.msu.edu


	1. Introduction
	Semi-discrete optimal transport
	Previous results
	Contributions of this article
	Notation and conventions
	Outline

	2. Existence of minimizers
	3. Dual problem
	Strong duality
	3.1. Relationship with classical Kantorovich duality

	4. Relationship between dual and primal optimizers
	5. Stability of F
	5.1. Stability for a fixed finite target
	-convergence

	6. Appendix
	7. Classical dual maximizers may not be dual maximizers
	Acknowledgments

	References