Let $\mathcal P_n = \{P \in \mathbb R^n_{\geq 0}: P^T \mathbb I = 1 \}$, where $\mathbb I = (1,...,1)^T \in \mathbb R^n$ and $f: \mathcal P_n \to \mathbb R$ a convex and differentiable function (or it can be as smooth as you like). Given $Q \in \mathcal P_n$ and the parameter $c > 0$, I'm interested in the following problem: \begin{align*} \min_{P \in \mathcal P_n} \;\; & f(P) \\ \text{s.t.} \;\; & W_p(P,Q) \leq c \end{align*}
Here I consider the following discrete transport: $$W_p(P,Q) = \min_{\pi \in \Pi(P,Q)} \langle D,\pi \rangle$$ where:
- $\Pi(P,Q) = \{ \pi \in \mathbb R^{n \times n}_{\geq 0}: \pi \mathbb I = P, \pi^T \mathbb I = Q \}$.
- $D \in \mathbb R^{n \times n}_{\geq 0}$ with $D_{ij} = |i-j|^p$, for $p \in [1, \infty]$.
I have $3$ questions:
Are there any efficient numerical methods to solve this problem?
Should it be easier/more difficult (numerically) for the different values of $p$?
If, instead, we use the discrete regularised transport: $$W_p^{\epsilon}(P,Q) = \min_{\pi \in \Pi(P,Q)} \langle D,\pi \rangle - \epsilon H(\pi)$$ where $H(\pi) = - \sum_{i,j} \pi_{ij} (\ln(\pi_{ij} - 1))$ and $\epsilon > 0$. Regarding this regularised optimisation problem,
Is it easier/more difficult (numerically) than the original problem?
If $\epsilon \to 0$, does its optimal solution converge to that of the original problem?