3
$\begingroup$

Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le i\le n, 1\le j\le n}$, consdier the optimization problem:

\begin{eqnarray} &&P(\alpha,\beta)~~:=~~\sup_{p=(p_{i,j})_{1\le i\le n, 1\le j\le n}\in\mathcal M(\alpha,\beta)}~\sum_{i=1}^n\sum_{j=1}^n p_{i,j}c_{i,j}, \\ \end{eqnarray} where $\mathcal M(\alpha,\beta)$ contains all $p=(p_{i,j})_{1\le i\le n, 1\le j\le n}$ s.t. \begin{eqnarray} &&\sum_{j=1}^np_{i,j}~=~\alpha_i,~ \forall 1\le i\le n;~~~~~\sum_{i=1}^np_{i,j}~=~\beta_j,~ \forall 1\le j\le n; \\ &&p_{i,j}~\ge~0,~ \forall 1\le i\le n, 1\le j\le n;~~~~~ \sum_{j=1}^np_{i,j}x_j~=~\alpha_ix_i,~ \forall 1\le i\le n. \end{eqnarray} Indeed, this is an optimal transport problem under additional constraints. Could we find some continuous function $f:\mathbb R^n\times \mathbb R^n\longrightarrow \mathbb R_+$ with $f(0,0)=0$ s.t. $$\big|P(\alpha,\beta)-P(\alpha',\beta')\big|\le f\big(\alpha-\alpha', \beta-\beta'\big) \mbox{ for all } (\alpha,\beta),~ (\alpha',\beta') \mbox{ s.t.}$$ $\mathcal M(\alpha,\beta)\neq \emptyset$ and $\mathcal M(\alpha',\beta')\neq \emptyset$? Any references, ideas and comments are highly appreciated! Thanks!

PS: There is a sufficient and necessary condition for $\mathcal M(\alpha,\beta)\neq\emptyset$.

Improve this question
$\endgroup$
6
  • $\begingroup$ If there is no constraint $\sum_{j=1}^np_{i,j}x_j=\alpha_ix_i$, $\forall 1\le i\le n$, then it is well known that this estimation can be obtained via the duality of classical optimal transport. $\endgroup$
    – CodeGolf
    Commented Nov 21, 2016 at 14:56
  • $\begingroup$ What do you get, when you work out the duality under the additional constraints? Also: Doesn't the estimate depend a lot on the $c_{i,j}$ and don't you need some conditions on these? $\endgroup$
    – Dirk
    Commented Nov 21, 2016 at 18:18
  • $\begingroup$ @Dirk Thanks for the reply. Indeed, the duality under the additional constraints is derived. But the optimizers for the dual problem can not be restricted to a class of Lipschitz functions, and that's why the duality can not yield directly the estimation. The matrix $c$ is given and fixed, and of course the function $f$ depend on $c$. $\endgroup$
    – CodeGolf
    Commented Nov 21, 2016 at 19:03
  • $\begingroup$ So if you talk about Lipschitz functions in the dual, you probably have fixed $c_{i,j} = d(i,j)$, i.e. $c$ encodes a metric? And isn't $W_1$ actually the same as $P$ if the additional constraints are not there? How does the function $f$ looks like for other $c$ that $c_{i,j} = d(i,j)$? I have to admit that the question is both too vague and not properly worked out. $\endgroup$
    – Dirk
    Commented Nov 21, 2016 at 19:07
  • $\begingroup$ @Dirk $c$ is just a matrix. Here we consider the discrete case, so both $I$ and $c$ are fixed, we just make $(\alpha, \beta)$ vary, and wanna study how $P(\alpha, \beta)$ vary w.r.t $(\alpha, \beta)$. $\endgroup$
    – CodeGolf
    Commented Nov 21, 2016 at 19:28

0

Reset to default

You must log in to answer this question.