# Optimisation under constraint of Wasserstein distance

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?

• I'm not saying it is efficient, but what one can always do is to optimize directly over $\pi \in \Pi(P, Q)$ satisfying $\langle D,\pi \rangle \leq c$. Since $\pi \mapsto P$ is linear, you obtain an objective function which is as nice as previously, and with a linear inequality constraint. Standard solvers will be able to solve it given $n$ is small enough. Further, there is of course a bunch of literature for when $f$ is linear, i.e. $f(P) = \int g \,dP$ in the Wasserstein "distributionally robust optimization" literature. – Steve Apr 11 '19 at 17:31
• @Steve: thanks for your comment. I will try your suggestion and compare with the methods in the answer below. – SiXUlm Apr 11 '19 at 20:19
• Consider the particular case where $f$ is linear, i.e $f(P) = \mathbb E_P[Z] = \sum_{i=1}^np_iz_i$, for some $z_1,\ldots,z_n \in \mathbb R$. Then $$\min_{P \in \Delta_n \mid W_1(P,Q) \le c}f(P) = \min_{P \in \Delta_n\mid W_1(P,Q) \le c}E_P[Z] = \max_{ \lambda > 0}-\lambda c + \sum_{i=1}^n p_i f_i^\lambda,$$ where $f_i^\lambda := \inf_{z_i'} \lambda d(z_i', z_i)-z_i'$. – dohmatob Apr 12 '19 at 12:39

Too long to comment.

Note that for a given P and Q, $$W_p(P,Q) = \min_{\pi \in \Pi(P,Q)} \langle D,\pi \rangle \leq c$$ if and only if there exists a $$\pi \in \Pi(P,Q)$$ such that $$\mbox{Tr}(D^\top \pi) = \langle D, \pi \rangle \leq c$$. With that preamble, and the assumption that $$f$$ depends explicitly only on $$P$$, consider the following optimization problem: \begin{align*} \min_{P \in R_+^{n}, ~~\pi\in R_+^{n\times n}} \;\; & f(P) \\ \text{s.t.} \;\; & \mbox{Tr}(D^\top \pi) \leq c\\ & \pi \mathbb I = P, ~\pi^T \mathbb I = Q. \end{align*} Note that a solution $$(P^*,\pi^*)$$ to the above convex program (LP is one considers a linear cost functional), will be a feasible point for the original optimization problem. Similarly, it is also not hard to argue that a solution to the original optimization problem would be a feasible point for the above convex program.

The two points together imply that the optima of the original problem can be achieved in polynomial time.

Hope this suggestion helps.

• It is really simple as that. Also, the case of regularization is the same (just adapt the new $\leq c$ constraint). – Dirk May 6 at 10:35