Finite-metric transport and normalized dual optima are attained

Define ${\pi }_{ij}=p_i{q}_j$. These entries are nonnegative by [F1], and their row sums are $p_i{\sum }_j{q}_j=p_i$ while their column sums are $q_j{\sum }_i{p}_i=q_j$. Thus $\pi \in \mathrm{\Gamma }(p,q)$ and the coupling set is nonempty.

Flatten a matrix into ${\mathbb{R}}^{m^2}$ in row-major order, assigning entry ${\pi }_{ij}$ to library coordinate $k=(i-1)m+(j-1)<m^2$; likewise potential coordinate $f_i$ corresponds to library coordinate $i-1<m$. In any dimension $n\ge 1$, for $u\in {\mathbb{R}}^n$ and $k<n$, [F11] gives $u_k^2\le {\sum }_{j<n}{u}_j^2$; by [F5,F11], $\mathrm{\mid }{u}_k{\mathrm{\mid }}^2=u_k^2\le d_2(u,0{)}^2$, and both $\mathrm{\mid }{u}_k\mathrm{\mid }$ and $d_2(u,0)$ are nonnegative, so [F11] gives $\mathrm{\mid }{u}_k\mathrm{\mid }\le d_2(u,0)$. By induction on $n$, every finite list satisfies $\mathrm{\mid }{\sum }_{k<n}{a}_k\mathrm{\mid }\le {\sum }_{k<n}\mathrm{\mid }{a}_k\mathrm{\mid }$: the empty case is equality and the successor step follows from $\mathrm{\mid }a+b\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }+\mathrm{\mid }b\mathrm{\mid }$ in [F11]. Thus for every finite linear form $L(z)={\sum }_{k<n}{c}_k{z}_k$, this bound, $\mathrm{\mid }ab\mathrm{\mid }=\mathrm{\mid }a\mathrm{\mid }\mathrm{\mid }b\mathrm{\mid }$, the coordinate estimate, multiplication by nonnegative coefficients, finite-sum monotonicity and scaling in [F11] give $\mathrm{\mid }L(z)-L(w)\mathrm{\mid }\le ({\sum }_{k<n}\mathrm{\mid }{c}_k\mathrm{\mid })d_2(z,w)$. The same estimate holds for every affine form $H(z)=L(z)+b$, since the constant cancels in $H(z)-H(w)$. The set $\mathrm{\Gamma }(p,q)$ is defined by finitely many affine equalities and weak inequalities. Each row or column equality, after moving its marginal to one side, has $m$ coefficients equal to $1$; each entrywise nonnegativity constraint has one coefficient equal to $1$, so the coefficient sum $C=\sum \mathrm{\mid }{c}_k\mathrm{\mid }$ is positive for every constraint. If an affine equality $H(z)=0$ fails at $z_0$, then for $d_2(z,z_0)<\mathrm{\mid }H(z_0)\mathrm{\mid }\mathrm{/}(2C)$ the estimate gives $\mathrm{\mid }H(z)-H(z_0)\mathrm{\mid }<\mathrm{\mid }H(z_0)\mathrm{\mid }\mathrm{/}2$, so $H(z)\mathrm{\ne }0$. If an affine inequality $H(z)\ge 0$ fails at $z_0$, then for $d_2(z,z_0)<-H(z_0)\mathrm{/}(2C)$ the estimate gives $H(z)<H(z_0)\mathrm{/}2<0$. Thus every point outside $\mathrm{\Gamma }(p,q)$ has a ball in its complement, so [F5,F6] make $\mathrm{\Gamma }(p,q)$ closed. Also $0\le {\pi }_{ij}\le p_i\le 1$ by [F1,F2], so the set is bounded. Since $m^2\ge 1$, [F6] makes $\mathrm{\Gamma }(p,q)$ compact.

For a matrix difference $z-w$, the objective changes by at most $C{d}_2(z,w)$, where $C={\sum }_{i,j}d(x_i,x_j)\ge 0$ is finite; the coordinate bound is the same as in step 1.2. For any $\epsilon >0$, taking $\delta =\epsilon \mathrm{/}(C+1)$ shows that inputs within $\delta$ have output difference less than $\epsilon$, so the objective is continuous by [F8] and lower semicontinuous by [F9]. It is real-valued because all distances are finite reals; by [F4] and [F1] its values are nonnegative. The nonempty compact set from steps 1.1–1.2 and [F7] therefore give a finite attained minimum, which is $W_1(p,q)$ by [F10].

The set ${\mathcal{L}}_1(X,d)$ contains the zero vector. It is closed because its constraints are finitely many linear equalities and weak inequalities: $f_1=0$ has one nonzero coefficient, and writing each $\mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le d(x_i,x_j)$ as $d(x_i,x_j)-(f_i-f_j)\ge 0$ and $d(x_i,x_j)+(f_i-f_j)\ge 0$ gives two nonzero coefficients in each inequality when $i\mathrm{\ne }j$; when $i=j$ the constraint is the identity $0\le 0$. Thus every violated constraint has positive coefficient sum and the strict-violation ball argument in step 1.2 applies using [F5,F6,F11]. Since $f_1=0$ and $\mathrm{\mid }{f}_i-f_1\mathrm{\mid }\le d(x_i,x_1)$, every $f\in {\mathcal{L}}_1(X,d)$ satisfies $\mathrm{\mid }{f}_i\mathrm{\mid }\le d(x_i,x_1)\le 1+{\sum }_{k=1}^{m}d(x_k,x_1)$ by [F3,F4]; thus the set is bounded. Since $m\ge 1$, [F6] makes it compact.

The objective $f\mapsto {\sum }_i(p_i-q_i)f_i$ changes by at most $C^{\mathrm{\prime }}{d}_2(f,g)$, where $C^{\mathrm{\prime }}={\sum }_i\mathrm{\mid }{p}_i-q_i\mathrm{\mid }\ge 0$; taking $\delta =\epsilon \mathrm{/}(C^{\mathrm{\prime }}+1)$ for each $\epsilon >0$ proves continuity by [F8] and upper semicontinuity by [F9]. The nonempty compact set from step 2.2 and [F7] give an attained maximum.