  In this paper a duality relation between the Ma\~{n}\'e potential and
Mather's action functional is derived in the context of convex and
state-dependent Hamiltonians. The duality relation is used to obtain min-max
representations of viscosity solutions of first order Hamilton-Jacobi
equations. These min-max representations naturally suggest class\-es of
subsolutions of Hamilton-Jacobi equations that arise in the theory of large
deviations. The subsolutions, in turn, are good candidates for designing
efficient rare-event simulation algorithms.
