# Why is it difficult to solve the Monge problem directly?

I'm trying to understand something about the Monge problem. The Monge problem is:

Let $$c(x,y): \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}^d$$ and $$\mathcal{T}(\mu_1,\mu_2) = \{ T: \mathbb{R}^d \rightarrow \mathbb{R}^d | \text{ Borel maps with condition} \, \, T\#\mu_1 = \mu_2 \}$$ where $$\mu_1$$ and $$\mu_2$$ are given, compactly supported measures which are absolutely continuous with respect to Lebesgue measure. The Monge problem is to find: $$\inf_{T\in\mathcal{T}(\mu_1,\mu_2)}C_M[T] = \int_{\mathbb{R}^d}c(x,Tx) \mu_1(dx)$$

A book I am reading provides the following discussion on why finding a minimizer directly using "usual" methods (ie taking a minimizing sequence) is tough:

Usually, what one does is the following: take a minimizing sequence $$T_n$$, find a bound on it giving compactness in some topology (here, if the support of $$\mu_2$$ is compact, the maps $$T_n$$ take value in a common bounded set $$\text{spt}\mu_2$$, and so one can get compactness of $$T_n$$ in the weak-* $$L^{\infty}$$ convergence), take a limit $$T_n \rightharpoonup T$$, and prove that $$T$$ is a minimizer. This requires semicontinuity of the functional $$C_M$$ with respect to this convergence (which is true in many cases, for instance, if $$c$$ is convex in its second variable): we need $$T_n \rightharpoonup T \implies \liminf_nC_M[T_n] \geq C_M[T]$$, but we also need that the limit $$T$$ still satisfies the constraint. Yet, the nonlinearity of the pushforward condition prevents us from proving this stability when we only have weak convergence.

Loosely, this all makes sense to me: but I'm getting turned around working the details.

1. Explicitly: Suppose $$\text{spt}\mu_2$$ is compact, why does $$T_n \rightarrow T$$ weak-* in $$L^{\infty}$$.

2. Explicitly: what are the sufficient conditions on $$C_M[T]$$ to ensure the implication in the above statement $$T_n \rightharpoonup T \implies \liminf_nC_M[T_n] \geq C_M[T]$$ Do I just need to say $$C_M[T]$$ is weakly lower semicontinuous and bounded from below? (i.e. I think this is the same as convexity)

3. Suppose I show that a minimizer of $$C_M[T]$$ exists. How do I see that minimizing sequence isn't preserving the pushforward condition in the limit? Apprently "non-linearity" is preventing this -- but I don't see how.

EDIT:

The statement: Let $$C_M[T]: L^{\infty} \rightarrow \mathbb{R}$$ be weak-* lower semicontinous and bounded from below. Then $$C_M[T]$$ has a minimizer.

Pf: $$C_M[T]$$ is bounded from below so $$\inf C_M[T]$$ exists. Let $$T_n \in L^{\infty}$$ be a minimizing sequence and let $$T$$ denote the minimizer. Consider a closed ball in the weak-* topology of positive radius centered at $$T$$. This ball is compact in weak-* topology by banach-aloglu - so there exists a subsequence of $$T_n$$, call it $$T_{n_k} \rightarrow T$$. This gives us $$\liminf C_M[T_{n_k}] \leq C_M[T_i] \quad \forall T_i \in L^{\infty}$$ -- in particular $$\liminf C_M[T_{n_k}] \leq C_M[T]$$. Weak-* LSC gives the other inequality, so $$C_M[T]$$ achieves its min.

for 3

It doesn't make sense to write: $$(aT_1+bT_2)_{\#}\mu = a(T{_1}_{\#}\mu) + b(T{_2}_{\#}\mu)$$ Let $$a=b=1$$, $$T_1 = 2x$$, $$T_2 = x^2$$, $$\mu$$ to be leb msr, and consider a set $$A = [0,-1]$$. Then $$(x^2 + 2x)_{\#}\mu\big([0,-1]\big) = \mu \bigg((x^2+2x)^{-1}\big([0,-1]\big)\bigg)$$ But $$(x^2+2x)^{-1}[0,-1]$$ can be $$[0,1]$$ or $$[1,2]$$ so LHS of such a statement is not well defined. So in what sense is the push forward non linear?

1. It is not true that $$T_n\to T$$ in any sense. However, since $$L^\infty=(L^1)^*$$, the unit ball in $$L^\infty$$ is weak* compact by Banach-Alaogu theorem. Hence, one can extract from $$T_n$$ a weak* convergent subsequence.
3. For $$d=1$$, let $$\mu_1$$ be the restriction of Lebesgue measure to $$[0,1]$$, and $$\mu_2$$ the sum of $$1/2$$-point masses at $$-1$$ and $$1$$. Let $$T_n(t):=\text{sgn}\sin(2\pi n t)$$. Then, clearly, $$T_n\sharp\mu_1=\mu_2$$ for all $$n$$. But $$T_n\to T\equiv 0$$ in the weak* topology and $$T$$ maps the Lebesgue measure to the point mass at $$0$$.
• My follow ups are too long, so I edited the orginal post -- for context see question edits. 1. Is this statement/proof correct? 2. So compact support of $\mu_2$ wasn't essential? That statement in the highlighted passage made me first investigate using Uniform Boundedness Principle - was this a misleading statement then? Or is there another of showing a minimizer using this statement? Jun 7, 2019 at 18:12
• 3. Okay, so if I find some $C_M[T]$ such that $T_n$ is given as you state, I can use your observation to show the pushforward is not preserved. The passage states "non-linearity" culprit. In what way is the pushforward non-linear? (again for context, see above edit) Jun 7, 2019 at 18:13
• No, your proof is wrong, you cannot prove the existence of a minimiser starting with "let $T$ denote the minimiser". Rather, you have to assume that all $T_n$ belong to some ball in $L^\infty$, this is where you use that $\mu_2$ has compact support. As for nonlinearity, it just means that if for two maps you have $T_{1,2}\sharp \mu_1=\mu_2$, then $T_1+T_2$ usually does not have this property. Since the weak* topology is defined by linear functionals, it is usually difficult to prove that a non-linear (and non-convex) condition is weak*-closed - and indeed in our case it is not. Jun 7, 2019 at 18:55