June  2015, 10(2): 233-253. doi: 10.3934/nhm.2015.10.233

On gradient structures for Markov chains and the passage to Wasserstein gradient flows

1. 

Weierstrass Institute, Mohrenstraße 39, 10117 Berlin, Germany

2. 

Weierstrass Institute, Mohrenstraße 39, 10117 Berlin, Germany

Received  March 2014 Revised  October 2014 Published  April 2015

We study the approximation of Wasserstein gradient structures by their finite-dimensional analog. We show that simple finite-volume discretizations of the linear Fokker-Planck equation exhibit the recently established entropic gradient-flow structure for reversible Markov chains. Then we reprove the convergence of the discrete scheme in the limit of vanishing mesh size using only the involved gradient-flow structures. In particular, we make no use of the linearity of the equations nor of the fact that the Fokker-Planck equation is of second order.
Citation: Karoline Disser, Matthias Liero. On gradient structures for Markov chains and the passage to Wasserstein gradient flows. Networks & Heterogeneous Media, 2015, 10 (2) : 233-253. doi: 10.3934/nhm.2015.10.233
References:
[1]

S. Adams, N. Dirr, M. A. Peletier and J. Zimmer, From a large-deviations principle to the Wasserstein gradient flow: A new micro-macro passage,, Communications in Mathematical Physics, 307 (2011), 791.  doi: 10.1007/s00220-011-1328-4.  Google Scholar

[2]

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures,, Lectures in Mathematics ETH Zürich, (2005).   Google Scholar

[3]

S. Arnrich, A. Mielke, M. A. Peletier, G. Savaré and M. Veneroni, Passing to the limit in a Wasserstein gradient flow: From diffusion to reaction,, Calc. Var. Part. Diff. Eqns., 44 (2012), 419.  doi: 10.1007/s00526-011-0440-9.  Google Scholar

[4]

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem,, Numer. Math., 84 (2000), 375.  doi: 10.1007/s002110050002.  Google Scholar

[5]

M. Bessemoulin-Chatard, A finite volume scheme for convection-diffusion equations with nonlinear diffusion derived from the Scharfetter-Gummel scheme,, Numer. Math., 121 (2012), 637.  doi: 10.1007/s00211-012-0448-x.  Google Scholar

[6]

A. Bradji and J. Fuhrmann, Some abstract error estimates of a finite volume scheme for a nonstationary heat equation on general nonconforming multidimensional spatial meshes,, Appl. Math., 58 (2013), 1.  doi: 10.1007/s10492-013-0001-y.  Google Scholar

[7]

C. Chainais-Hillairet, M. Gisclon and A. Jüngel, A finite-volume scheme for the multidimensional quantum drift-diffusion model for semiconductors,, Numer. Methods Partial Differential Equations, 27 (2011), 1483.  doi: 10.1002/num.20592.  Google Scholar

[8]

S.-N. Chow, W. Huang, Y. Li and H. Zhou, Fokker-Planck equations for a free energy functional or Markov process on a graph,, Arch. Rational Mech. Anal., 203 (2012), 969.  doi: 10.1007/s00205-011-0471-6.  Google Scholar

[9]

M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy,, Arch. Rational Mech. Anal., 206 (2012), 997.  doi: 10.1007/s00205-012-0554-z.  Google Scholar

[10]

M. Erbar and J. Maas, Gradient flow structures for discrete porous medium equations,, Discrete Contin. Dyn. Syst., 34 (2014), 1355.  doi: 10.3934/dcds.2014.34.1355.  Google Scholar

[11]

R. Eymard, T. Gallouët and R. Herbin, The finite volume method,, in Handbook of Numerical Analysis. Vol. VII, (2000), 713.   Google Scholar

[12]

R. Eymard and J.-M. Hérard, eds., Finite Volumes for Complex Applications V,, ISTE, (2008).   Google Scholar

[13]

J. Fořt, J. Fürst Jiří, H. R. Herbin and F. Hubert, eds., Finite Volumes for Complex Applications. VI. Problems & perspectives. Volume 1, 2,, Springer Proceedings in Mathematics, (2011).  doi: 10.1007/978-3-642-20671-9.  Google Scholar

[14]

J. Fuhrmann, A. Linke and H. Langmach, A numerical method for mass conservative coupling between fluid flow and solute transport,, Appl. Numer. Math., 61 (2011), 530.  doi: 10.1016/j.apnum.2010.11.015.  Google Scholar

[15]

K. Gärtner, Charge transport in semiconductors and a finite volume scheme,, in Finite volumes for complex applications. VI. Problems & perspectives. Volume 1, (2011), 513.  doi: 10.1007/978-3-642-20671-9_54.  Google Scholar

[16]

N. Gigli, On the heat flow on metric measure spaces: Existence, uniqueness and stability,, Calc. Var. Partial Differential Equations, 39 (2010), 101.  doi: 10.1007/s00526-009-0303-9.  Google Scholar

[17]

N. Gigli and J. Maas, Gromov-Hausdorff convergence of discrete transportation metrics,, SIAM J. Math. Anal., 45 (2013), 879.  doi: 10.1137/120886315.  Google Scholar

[18]

D. Hilhorst, H. C. V. Do and Y. Wang, A finite volume method for density driven flows in porous media,, in CEMRACS'11: Multiscale Coupling of Complex Models in Scientific Computing, (2012), 376.  doi: 10.1051/proc/201238021.  Google Scholar

[19]

R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation,, SIAM J. Math. Analysis, 29 (1998), 1.  doi: 10.1137/S0036141096303359.  Google Scholar

[20]

M. Liero, Passing from bulk to bulk-surface evolution in the Allen-Cahn equation,, NoDEA Nonlinear Differential Equations Appl., 20 (2013), 919.  doi: 10.1007/s00030-012-0189-7.  Google Scholar

[21]

M. Liero and A. Mielke, Gradient structures and geodesic convexity for reaction-diffusion systems,, Phil. Trans. Royal Soc. A, 371 (2013).  doi: 10.1098/rsta.2012.0346.  Google Scholar

[22]

M. Liero and U. Stefanelli, Weighted inertia-dissipation-energy functionals for semilinear equations,, Boll. Unione Mat. Ital. (9), 6 (2013), 1.   Google Scholar

[23]

J. Maas, Gradient flows of the entropy for finite Markov chains,, J. Funct. Anal., 261 (2011), 2250.  doi: 10.1016/j.jfa.2011.06.009.  Google Scholar

[24]

P. A. Markowich, The Stationary Semiconductor Device Equations,, Computational Microelectronics, (1986).  doi: 10.1007/978-3-7091-3678-2.  Google Scholar

[25]

D. Matthes and H. Osberger, Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation,, ESAIM Math. Model. Numer. Anal., 48 (2014), 697.  doi: 10.1051/m2an/2013126.  Google Scholar

[26]

A. Mielke, A gradient structure for reaction-diffusion systems and for energy-drift-diffusion systems,, Nonlinearity, 24 (2011), 1329.  doi: 10.1088/0951-7715/24/4/016.  Google Scholar

[27]

A. Mielke, Geodesic convexity of the relative entropy in reversible Markov chains,, Calc. Var. Part. Diff. Eqns., 48 (2013), 1.  doi: 10.1007/s00526-012-0538-8.  Google Scholar

[28]

A. Mielke, Thermomechanical modeling of energy-reaction-diffusion systems, including bulk-interface interactions,, Discr. Cont. Dynam. Systems Ser. S, 6 (2013), 479.  doi: 10.3934/dcdss.2013.6.479.  Google Scholar

[29]

A. Mielke, T. Roubíček and U. Stefanelli, $\Gamma$-limits and relaxations for rate-independent evolutionary problems,, Calc. Var. Part. Diff. Eqns., 31 (2008), 387.  doi: 10.1007/s00526-007-0119-4.  Google Scholar

[30]

A. Mielke and U. Stefanelli, Weighted energy-dissipation functionals for gradient flows,, ESAIM Control Optim. Calc. Var., 17 (2011), 52.  doi: 10.1051/cocv/2009043.  Google Scholar

[31]

L. Onsager, Reciprocal relations in irreversible processes, I+II,, Physical Review, 37 (1931), 405.   Google Scholar

[32]

F. Otto, Dynamics of labyrinthine pattern formation in magnetic fluids: A mean-field theory,, Arch. Rational Mech. Anal., 141 (1998), 63.  doi: 10.1007/s002050050073.  Google Scholar

[33]

F. Otto, The geometry of dissipative evolution equations: The porous medium equation,, Comm. Partial Differential Equations, 26 (2001), 101.  doi: 10.1081/PDE-100002243.  Google Scholar

[34]

E. Sandier and S. Serfaty, Gamma-convergence of gradient flows with applications to Ginzburg-Landau,, Comm. Pure Appl. Math., 57 (2004), 1627.  doi: 10.1002/cpa.20046.  Google Scholar

show all references

References:
[1]

S. Adams, N. Dirr, M. A. Peletier and J. Zimmer, From a large-deviations principle to the Wasserstein gradient flow: A new micro-macro passage,, Communications in Mathematical Physics, 307 (2011), 791.  doi: 10.1007/s00220-011-1328-4.  Google Scholar

[2]

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures,, Lectures in Mathematics ETH Zürich, (2005).   Google Scholar

[3]

S. Arnrich, A. Mielke, M. A. Peletier, G. Savaré and M. Veneroni, Passing to the limit in a Wasserstein gradient flow: From diffusion to reaction,, Calc. Var. Part. Diff. Eqns., 44 (2012), 419.  doi: 10.1007/s00526-011-0440-9.  Google Scholar

[4]

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem,, Numer. Math., 84 (2000), 375.  doi: 10.1007/s002110050002.  Google Scholar

[5]

M. Bessemoulin-Chatard, A finite volume scheme for convection-diffusion equations with nonlinear diffusion derived from the Scharfetter-Gummel scheme,, Numer. Math., 121 (2012), 637.  doi: 10.1007/s00211-012-0448-x.  Google Scholar

[6]

A. Bradji and J. Fuhrmann, Some abstract error estimates of a finite volume scheme for a nonstationary heat equation on general nonconforming multidimensional spatial meshes,, Appl. Math., 58 (2013), 1.  doi: 10.1007/s10492-013-0001-y.  Google Scholar

[7]

C. Chainais-Hillairet, M. Gisclon and A. Jüngel, A finite-volume scheme for the multidimensional quantum drift-diffusion model for semiconductors,, Numer. Methods Partial Differential Equations, 27 (2011), 1483.  doi: 10.1002/num.20592.  Google Scholar

[8]

S.-N. Chow, W. Huang, Y. Li and H. Zhou, Fokker-Planck equations for a free energy functional or Markov process on a graph,, Arch. Rational Mech. Anal., 203 (2012), 969.  doi: 10.1007/s00205-011-0471-6.  Google Scholar

[9]

M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy,, Arch. Rational Mech. Anal., 206 (2012), 997.  doi: 10.1007/s00205-012-0554-z.  Google Scholar

[10]

M. Erbar and J. Maas, Gradient flow structures for discrete porous medium equations,, Discrete Contin. Dyn. Syst., 34 (2014), 1355.  doi: 10.3934/dcds.2014.34.1355.  Google Scholar

[11]

R. Eymard, T. Gallouët and R. Herbin, The finite volume method,, in Handbook of Numerical Analysis. Vol. VII, (2000), 713.   Google Scholar

[12]

R. Eymard and J.-M. Hérard, eds., Finite Volumes for Complex Applications V,, ISTE, (2008).   Google Scholar

[13]

J. Fořt, J. Fürst Jiří, H. R. Herbin and F. Hubert, eds., Finite Volumes for Complex Applications. VI. Problems & perspectives. Volume 1, 2,, Springer Proceedings in Mathematics, (2011).  doi: 10.1007/978-3-642-20671-9.  Google Scholar

[14]

J. Fuhrmann, A. Linke and H. Langmach, A numerical method for mass conservative coupling between fluid flow and solute transport,, Appl. Numer. Math., 61 (2011), 530.  doi: 10.1016/j.apnum.2010.11.015.  Google Scholar

[15]

K. Gärtner, Charge transport in semiconductors and a finite volume scheme,, in Finite volumes for complex applications. VI. Problems & perspectives. Volume 1, (2011), 513.  doi: 10.1007/978-3-642-20671-9_54.  Google Scholar

[16]

N. Gigli, On the heat flow on metric measure spaces: Existence, uniqueness and stability,, Calc. Var. Partial Differential Equations, 39 (2010), 101.  doi: 10.1007/s00526-009-0303-9.  Google Scholar

[17]

N. Gigli and J. Maas, Gromov-Hausdorff convergence of discrete transportation metrics,, SIAM J. Math. Anal., 45 (2013), 879.  doi: 10.1137/120886315.  Google Scholar

[18]

D. Hilhorst, H. C. V. Do and Y. Wang, A finite volume method for density driven flows in porous media,, in CEMRACS'11: Multiscale Coupling of Complex Models in Scientific Computing, (2012), 376.  doi: 10.1051/proc/201238021.  Google Scholar

[19]

R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation,, SIAM J. Math. Analysis, 29 (1998), 1.  doi: 10.1137/S0036141096303359.  Google Scholar

[20]

M. Liero, Passing from bulk to bulk-surface evolution in the Allen-Cahn equation,, NoDEA Nonlinear Differential Equations Appl., 20 (2013), 919.  doi: 10.1007/s00030-012-0189-7.  Google Scholar

[21]

M. Liero and A. Mielke, Gradient structures and geodesic convexity for reaction-diffusion systems,, Phil. Trans. Royal Soc. A, 371 (2013).  doi: 10.1098/rsta.2012.0346.  Google Scholar

[22]

M. Liero and U. Stefanelli, Weighted inertia-dissipation-energy functionals for semilinear equations,, Boll. Unione Mat. Ital. (9), 6 (2013), 1.   Google Scholar

[23]

J. Maas, Gradient flows of the entropy for finite Markov chains,, J. Funct. Anal., 261 (2011), 2250.  doi: 10.1016/j.jfa.2011.06.009.  Google Scholar

[24]

P. A. Markowich, The Stationary Semiconductor Device Equations,, Computational Microelectronics, (1986).  doi: 10.1007/978-3-7091-3678-2.  Google Scholar

[25]

D. Matthes and H. Osberger, Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation,, ESAIM Math. Model. Numer. Anal., 48 (2014), 697.  doi: 10.1051/m2an/2013126.  Google Scholar

[26]

A. Mielke, A gradient structure for reaction-diffusion systems and for energy-drift-diffusion systems,, Nonlinearity, 24 (2011), 1329.  doi: 10.1088/0951-7715/24/4/016.  Google Scholar

[27]

A. Mielke, Geodesic convexity of the relative entropy in reversible Markov chains,, Calc. Var. Part. Diff. Eqns., 48 (2013), 1.  doi: 10.1007/s00526-012-0538-8.  Google Scholar

[28]

A. Mielke, Thermomechanical modeling of energy-reaction-diffusion systems, including bulk-interface interactions,, Discr. Cont. Dynam. Systems Ser. S, 6 (2013), 479.  doi: 10.3934/dcdss.2013.6.479.  Google Scholar

[29]

A. Mielke, T. Roubíček and U. Stefanelli, $\Gamma$-limits and relaxations for rate-independent evolutionary problems,, Calc. Var. Part. Diff. Eqns., 31 (2008), 387.  doi: 10.1007/s00526-007-0119-4.  Google Scholar

[30]

A. Mielke and U. Stefanelli, Weighted energy-dissipation functionals for gradient flows,, ESAIM Control Optim. Calc. Var., 17 (2011), 52.  doi: 10.1051/cocv/2009043.  Google Scholar

[31]

L. Onsager, Reciprocal relations in irreversible processes, I+II,, Physical Review, 37 (1931), 405.   Google Scholar

[32]

F. Otto, Dynamics of labyrinthine pattern formation in magnetic fluids: A mean-field theory,, Arch. Rational Mech. Anal., 141 (1998), 63.  doi: 10.1007/s002050050073.  Google Scholar

[33]

F. Otto, The geometry of dissipative evolution equations: The porous medium equation,, Comm. Partial Differential Equations, 26 (2001), 101.  doi: 10.1081/PDE-100002243.  Google Scholar

[34]

E. Sandier and S. Serfaty, Gamma-convergence of gradient flows with applications to Ginzburg-Landau,, Comm. Pure Appl. Math., 57 (2004), 1627.  doi: 10.1002/cpa.20046.  Google Scholar

[1]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[2]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217

[3]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[4]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[5]

Ebraheem O. Alzahrani, Muhammad Altaf Khan. Androgen driven evolutionary population dynamics in prostate cancer growth. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020426

[6]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[7]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[8]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[9]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[10]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[11]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[12]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[13]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[14]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

[15]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.053

Metrics

  • PDF downloads (26)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]