How does one derive this dual from the primal? On page 22 in https://tel.archives-ouvertes.fr/tel-02926037/document it states the dual problem to the primal optimal transport problem:

So the primal is $\min_x -\epsilon\langle\exp(\frac{-w}{\epsilon})\, \vert \, \textbf{1} \rangle $ subject to $x\textbf{1}=f$ and $x^T\textbf{1}=g.$
It is clear to me that the objective function does not depend on $x$, thus the dual becomes unconstrained.
However, it is not clear to me how we get $\lambda_i$ and $\mu_j$ involved in the last term, i.e. why do these variables appear in $\exp()$?
 A: Actually, the primal problem is
$\inf_x\sup_{\lambda,\mu} {\mathcal L}(x,\lambda,\mu)$.   Note that, in this context, we can write
$$
{\mathcal L}(x,\lambda,\mu) = \langle\lambda|f\rangle + \langle \mu|g\rangle
+ \langle x,a\rangle +\varepsilon\langle x|\log x -{\bf 1}\rangle ,
\qquad a_{i,j}=w_{i,j}-\lambda_i-\mu_j.
$$
In the primal problem, the $\sup$ is $+\infty$ unless the matrix $x$ satisfies the constraints $\lambda=x\bf1$ and $\mu=x^T\bf1$.
The dual problem, however, is $\sup_{\lambda,\mu}\inf_{x}{\mathcal L}(x,\lambda,\mu)$. Applying the proposition mentioned, which immediately precedes the quoted text, we can compute the $\inf$ over $x$ for any $\lambda,\mu$, since
$$
\min_x  \langle x,a\rangle +\varepsilon\langle x|\log x -{\bf 1}\rangle
= -\varepsilon\sum_{i,j}\exp\left(\frac{-a_{i,j}}\varepsilon\right).
$$
Note that the minimizer is $x_{i,j}=\exp(-a_{i,j}/\varepsilon)$ and with this, one has $\langle x|a\rangle+\varepsilon\langle x|\log x\rangle=0$.
Thus expression (1.6) simply restates the dual problem after explicit evaluation of $\inf_x {\mathcal L}(x,\lambda,\mu)$.
