1
$\begingroup$

Let the population on some region $\Omega\subset\mathbb R^d$ be modeled by a density function $\rho:\Omega\to (0,+\infty)$. Provided $n\ge 1$ food trucks labeled by their capacity $p_1,\ldots, p_n\in (0,\infty)$, where

$$\sum_{i=1}^n p_i ~~=~~ \int_{\Omega} \rho(x)dx ~~=~~ 1.$$

We pursue the "best distribution" of the trucks. Namely, if the trucks are located at $y_1,\ldots, y_n\in\Omega$, then the distance in average between the inhabitants and the source (food) is quantified by the Wasserstein distance $W_2$, i.e.

$$F(Y)~~:=~~W_2^2\big(\mu_Y,\nu\big),$$

where the discrete measure $\mu_Y:=\sum_{i=1}^np_i\delta_{y_i}(dx)$ stands for the distribution of the trucks, with $Y:=(y_1,\ldots, y_n)$, and $\nu$ is the probability measure with density $\rho$, i.e. $\nu(dx):=\rho(x)dx$. My concern is to investigate the regularity of $F$ on $\Omega^n$, i.e. $\nabla F$, and the minimization problem $\inf_{Y\in\Omega^n}F(Y)$. Any ideas or comments are highly appreciated!

Some thoughts: If $\Omega$ is assumed to be compact, then the minimizer for $F$ must exist. Also, it follows by definition that $Y\mapsto F(Y)$ is Lipschitz, as

$$\big|W_2(\mu_Y,\nu)-W_2(\mu_Y',\nu)\big|~~\le~~W_2(\mu_Y,\mu_Y')~~\le~~\sum_{i=1}^n|y_i-y_i'|,$$

where the first inequality follow from the triangle inequality and the second one from the dual formulation of $W_2$.

$\endgroup$
3
  • $\begingroup$ Some questions: What is the ground metric on $\mathbb{R}^d$ for the Wasserstein distance? If $F(Y)$ is the square of the Wasserstein 2 distance, how do your thoughts show Lipschitz continuity (your inequality is without the square)? $\endgroup$ – Steve May 1 '19 at 8:49
  • $\begingroup$ @Steve Indeed, I am always assuming the case of compact $\Omega$. Then for any $Y\in\Omega^n$, $W(\mu_Y,\nu)=\inf_{\lambda}\big(\int_{\Omega}\lambda d\mu_Y-\int_{\Omega}\lambda d\nu \big) \le 2(C+1)$, where the inf is taken overall $1-$Lipschitz functions $\lambda:\Omega\to\mathbb R$, and $C$ in the second inequality denotes a upper bound of $\Omega$, i.e. $\sup_{x\in\Omega} |x|\le C$. $\endgroup$ – Neymar May 1 '19 at 11:17
  • $\begingroup$ @Neymar: Then your notations are confusing. Your definition above $\inf_\lambda$ is the 1- Wasserstein distance $W_1(\mu,\nu)$ (also known as 'earth mover' or 'bounded-Lipschitz). The notation $W_2$ should rather stand for the quadratic Wasserstein distance with cost function $c(x,y)=|x-y^2$. So write $W_1$ everywhere. $\endgroup$ – leo monsaingeon May 9 '19 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.