Finite-metric transport duality and complementary slackness

For any $\pi \in \mathrm{\Gamma }(p,q)$ and any $f\in {\mathbb{R}}^m$ with $f_1=0$ and $\mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le d(x_i,x_j)$, the marginal equations give ${\sum }_i(p_i-q_i)f_i={\sum }_{i,j}{\pi }_{ij}(f_i-f_j)\le {\sum }_{i,j}{\pi }_{ij}d(x_i,x_j)$. The inequality uses ${\pi }_{ij}\ge 0$ and $f_i-f_j\le \mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le d(x_i,x_j)$. Thus every feasible dual value is at most every feasible primal cost.

Write $d_{ij}=d(x_i,x_j)$, and for $i=1,\dots ,m$ let $e_i\in {\mathbb{R}}^m$ have value $1$ at library coordinate $k=i-1$ and $0$ at every other coordinate. For alphabet-indexed tuples $u=(u_i{)}_{i=1}^m$ and $v=(v_j{)}_{j=1}^m$, identify $(u,v,t)$ with the vector in ${\mathbb{R}}^{2m+1}$ whose coordinate $k<m$ is $u_{k+1}$, whose coordinate $m+k$ is $v_{k+1}$, and whose coordinate $2m$ is $t$. Let $K$ be the nonnegative span of $(e_i,e_j,d_{ij})$ for all $i,j$, together with $(0,0,1)$. By [F7], $K$ is closed and closed under nonnegative linear combinations. For $x,y\in K$ and $s\in [0,1]$, [F7] gives $sx+(1-s)y\in K$, so [F11] makes $K$ convex; the zero representation gives $0\in K$. Put $c_{\ast }=W_1(p,q)$, which is finite and attained by [F6]. For every $\epsilon >0$, the vector $y_{\epsilon }=(p,q,c_{\ast }-\epsilon )$ under this identification is outside $K$: if it had a representation with coefficients ${\lambda }_{ij}\ge 0$ and $t\ge 0$, its first two coordinate blocks would make $\lambda \in \mathrm{\Gamma }(p,q)$ and its last coordinate would give $c_{\ast }-\epsilon ={\sum }_{i,j}{d}_{ij}{\lambda }_{ij}+t\ge c_{\ast }$, contradicting minimality.

Apply [F8] to $K$ and $y_{\epsilon }$. It gives a vector $h$ and threshold $\beta$ with $⟨h,z⟩\le \beta <⟨h,y_{\epsilon }⟩$ for all $z\in K$. Since $0\in K$, $\beta \ge 0$. By [F7], $sz\in K$ for every $z\in K$ and $s\ge 0$. If $c:=⟨h,z⟩>0$ for some $z\in K$, take $s=(\beta +1)\mathrm{/}c>0$; then $sz\in K$ but $⟨h,sz⟩=\beta +1>\beta$, a contradiction. Hence $⟨h,z⟩\le 0$ for every $z\in K$, while $⟨h,y_{\epsilon }⟩>0$.

Decompose $h=(a,b,g)$ with $a,b\in {\mathbb{R}}^m$ and $g\in \mathbb{R}$. By [F10], pairing with $(0,0,1)\in K$ gives $g\le 0$. If $g=0$, pairing with every $(e_i,e_j,d_{ij})$ gives $a_i+b_j\le 0$. Multiplying by $p_i{q}_j\ge 0$ and summing yields ${\sum }_i{p}_i{a}_i+{\sum }_j{q}_j{b}_j={\sum }_{i,j}{p}_i{q}_j(a_i+b_j)\le 0$. When $g=0$ this left-hand side is $⟨h,y_{\epsilon }⟩$, contrary to step 2.1. Therefore $g<0$.

Define $u_i=a_i\mathrm{/}(-g)$ and $v_j=b_j\mathrm{/}(-g)$. The generator inequalities and $g<0$ give $u_i+v_j\le d_{ij}$ for all $i,j$. Dividing the strict point inequality by $-g>0$ gives ${\sum }_i{p}_i{u}_i+{\sum }_j{q}_j{v}_j>c_{\ast }-\epsilon$.

Set $f_i={\min }_{1\le j\le m}(d_{ij}-v_j)$, whose minimum is attained by [F9]. From $u_i+v_j\le d_{ij}$ we have $u_i\le f_i$. For any $i,k,j$, the triangle inequality gives $d_{ij}-v_j\le d_{ik}+d_{kj}-v_j$; taking finite minima yields $f_i\le d_{ik}+f_k$, and symmetry gives $\mathrm{\mid }{f}_i-f_k\mathrm{\mid }\le d_{ik}$. Also $f_j\le d_{jj}-v_j=-v_j$, so $-f_j\ge v_j$. Since $p,q$ are nonnegative, ${\sum }_i(p_i-q_i)f_i\ge {\sum }_i{p}_i{u}_i+{\sum }_j{q}_j{v}_j>c_{\ast }-\epsilon$. Replacing $f_i$ by $f_i-f_1$ preserves all Lipschitz inequalities and the objective because ${\sum }_i{p}_i={\sum }_i{q}_i=1$; the resulting vector is normalized with first coordinate zero.

Let $D$ be the attained maximum in [F6]. Step 5.1 shows $D>c_{\ast }-\epsilon$ for every $\epsilon >0$, so $D\ge c_{\ast }$; otherwise $\epsilon =(c_{\ast }-D)\mathrm{/}2$ contradicts that inequality. Step 1.1 gives $D\le c_{\ast }$. Hence $D=c_{\ast }=W_1(p,q)$, and both extrema are attained by [F6].

Let $\pi$ be any minimizing coupling and $f$ any maximizing normalized potential. By the marginal equations and optimal-value equality, $0=c_{\ast }-{\sum }_i(p_i-q_i)f_i={\sum }_{i,j}{\pi }_{ij}(d_{ij}-(f_i-f_j))$. Each summand is nonnegative by feasibility. A finite sum of nonnegative reals can be zero only if each term is zero: if one term were positive, adding the other nonnegative terms would keep the total positive. Thus if ${\pi }_{ij}>0$, its factor $d_{ij}-(f_i-f_j)$ is zero, proving $f_i-f_j=d_{ij}$.