Viscosity solution methods and the discrete Aubry-Mather problem

In this paper we study a discrete multi-dimensional version of Aubry- Mather theory using mostly tools from the theory of viscosity solutions. We set this problem as an infinite dimensional linear programming problem. The dual problem turns out to be a discrete analog of the Hamilton-Jacobi equations. We present some applications to discretizations of Lagrangian systems. 1. Introduction. Certain variational problems which arise in applications such as Lagrangian mechanics, Mather's problem (Mn92, Mn96), Monge-Kantorowich opti- mal transport problems (Eva99), or stationary stochastic optimal control (Gom02a), can be written as infinite dimensional linear programming problems in spaces of measures. The standard strategy to study such problems is to compute the dual problem. In general, the dual yields important information about the original (pri- mal) problem. This dual may be of interest itself, and therefore the primal problem may provide useful insights about the dual. In the continuous case, the dual of Mather's problem is related to viscosity solu- tions of Hamilton-Jacobi equations (Fat97a, Fat97b, Fat98a, Fat98b). For stationary stochastic optimal control, it turns out to be related with second order nonlinear elliptic equations. For discrete problems, such as optimal transport and the problem discussed in this paper, the dual is not a partial dierential equation but a dierence equa- tion. These equations can be seen as discretizations of the corresponding partial dierential equations in the appropriate limit. The objective of this paper is twofold, one is to show that viscosity solutions methods can be adapted and used to study certain discrete dynamical system, and can be used to prove many well known facts about Mather's theory such as the existence of invariant sets and measures, the graph theorem, and asymptotic behaviour. The other one is to show that in the continuous limit one can recover the corresponding objects such as Mather's measures and viscosity solutions. We would like to point out that our results concerning Mather sets and measures are not new, the main novelty consists in the formulation and the methods used to obtain them,