# Optimization problem restricted to a smaller field?

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!

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