Skip to main content
deleted 65 characters in body
Source Link
CodeGolf
  • 1.8k
  • 11
  • 16

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_+^2\longrightarrow \mathbb R_+$$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(W_1(\alpha,\alpha'), W_1(\beta,\beta')\big) \mbox{ for all } (\alpha,\beta),~ (\alpha',\beta') \mbox{ 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$? Here $W_1(\cdot,\cdots)$ denotes the first order Wasserstein distance. Any references, ideas and comments are highly appreciated! Thanks!

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

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_+^2\longrightarrow \mathbb R_+$ with $f(0,0)=0$ s.t. $$\big|P(\alpha,\beta)-P(\alpha',\beta')\big|\le f\big(W_1(\alpha,\alpha'), W_1(\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$? Here $W_1(\cdot,\cdots)$ denotes the first order Wasserstein distance. Any references, ideas and comments are highly appreciated! Thanks!

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

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$.

Source Link
CodeGolf
  • 1.8k
  • 11
  • 16

Dependence of optimization problem on the linear constraints

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_+^2\longrightarrow \mathbb R_+$ with $f(0,0)=0$ s.t. $$\big|P(\alpha,\beta)-P(\alpha',\beta')\big|\le f\big(W_1(\alpha,\alpha'), W_1(\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$? Here $W_1(\cdot,\cdots)$ denotes the first order Wasserstein distance. Any references, ideas and comments are highly appreciated! Thanks!

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