Let $c:\mathbb R^2\to\mathbb R$ be a Lipschitz and bounded function (which can be supposed as "nice" as possible). Let $\mu$ and $\nu$ be two probability measures on $\mathbb R$ with finite first moment, i.e.

$$\int_{\mathbb R}|x|d\mu(x),~ \int_{\mathbb R}|x|d\nu(x)~~<~~+\infty.$$

Denote by $\mathcal m\equiv \mathcal m(\mathbb R)$ and $\mathcal C_{Lip}\equiv\mathcal C_{Lip}(\mathbb R)$ the spaces of measurable functions and Lipschitz functions. Consider the following optimization problem:

$$D(\mu,\nu)~~:=~~\inf\left\{\int\varphi d\mu~+~\int\psi d\nu:~~ \exists~ (\varphi, \psi, h)\in \mathcal C_{Lip}\times \mathcal C_{Lip}\times \mathcal m~ \mbox{ s.t. }~ \varphi(x)~+~\psi(y)~+~h(x)(y-x)~ \ge~ c(x,y) \mbox{ for all } (x,y)\in\mathbb R^2\right\}.~~~~~~~~~~~~~~~~~~ (\ast)$$

My question is whether we may solve this optimization by problem by searching only $(\varphi, \psi, h)\in \mathcal C_{Lip, L}\times \mathcal C_{Lip,L}\times \mathcal m$ for some $L>0$, where $\mathcal C_{Lip, L}\subset \mathcal C_{Lip}$ denotes the subset of $L-$Lipschitz functions.

The following are my thoughts:

For any $(\varphi, \psi, h)\in \mathcal C_{Lip}\times \mathcal C_{Lip}\times \mathcal m$ satisfying the inequality of $(\ast)$, one has

$$\varphi(x)~+~h(x)(y-x)~ \ge~ c(x,y) ~-~ \psi(y) \mbox{ for all } y\in\mathbb R,~~~~~~~ (\star)$$

and thus

$$\varphi(x)~+~h(x)(y-x)~ \ge~ c_{\psi}(x,y) \mbox{ for all } y\in\mathbb R,$$

where $c_{\psi}(x,\cdot)$ denotes the concave envelope of $c(x,\cdot)- \psi(\cdot)$ (since the l.h.s. of $(\star)$ is affine on $y$). Taking in particular $y=x$ one has

$$\varphi(x) ~ \ge~ c_{\psi}(x,x) \mbox{ for all } x\in\mathbb R.$$

Moreover, it follows by the concavity of $c_{\psi}(x,\cdot)$ that

$$c_{\psi}(x,x)~+~\partial_yc_{\psi}(x,x)(y-x)~ \ge~ c_{\psi}(x,y) \mbox{ for all } (x,y)\in\mathbb R^2.$$

Finally the above optimization problem $(*)$ can be written as

$$D(\mu,\nu)~~=~~\inf\left\{\int_{\mathbb R}c_{\psi}(x,x) d\mu(x)~+~\int_{\mathbb R}\psi(x) d\nu(x):~~ \psi\in \mathcal C_{Lip}\right\}.$$

So my question can be formulated as below: could we find some $L>0$ s.t.

$$D(\mu,\nu)~~=~~\inf\left\{\int_{\mathbb R}c_{\psi}(x,x) d\mu(x)~+~\int_{\mathbb R}\psi(x) d\nu(x):~~ \psi\in \mathcal C_{Lip,L}\right\}?$$

Any comments or insights are welcome! Thanks so much!

  • $\begingroup$ Clearly, the answer depends essentially on the structure of $(\mu,\nu)$. So I'd like to know under which condtions on $(\mu,\nu)$. $\endgroup$
    – CodeGolf
    Nov 8, 2016 at 12:35

1 Answer 1


You are facing the classical optimal transport problem, on which there is a huge literature. Here is a recent comprehensive treatise by Cédric Villani (Warning: 1K pages).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.