  This is our first paper on the extension of our recent work on the
Lax-Oleinik commutators and its applications to the intrinsic approach of
propagation of singularities of the viscosity solutions of Hamilton-Jacobi
equations. We reformulate Kantorovich-Rubinstein duality theorem in the theory
of optimal transport in terms of abstract Lax-Oleinik operators, and analyze
the relevant optimal transport problem in the case the cost function
$c(x,y)=h(t_1,t_2,x,y)$ is the fundamental solution of Hamilton-Jacobi
equation. For further applications to the problem of cut locus and propagation
of singularities in optimal transport, we introduce corresponding random
Lax-Oleinik operators. We also study the problem of singularities for
$c$-concave functions and its dynamical implication when $c$ is the fundamental
solution with $t_2-t_1\ll1$ and $t_2-t_1<\infty$, and $c$ is the Peierls'
barrier respectively.
