Top

Journal of Scientific Computing

Published in:

01-07-2021

Artificial Viscosity Joint Spacetime Multigrid Method for Hamilton–Jacobi–Bellman and Kolmogorov–Fokker–Planck System Arising from Mean Field Games

Authors: Yangang Chen, Justin W. L. Wan

Published in: Journal of Scientific Computing | Issue 1/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we study numerical solutions for the Hamilton-Jacobi-Bellman (HJB) and Kolmogorov–Fokker–Planck (KFP) equations arising from mean field games. In order to solve the nonlinear discretized systems efficiently, we propose a multigrid method. Our proposed multigrid method is developed on the joint spacetime and is a full approximation scheme (FAS). We consider hybrid full-semi coarsening and kernel preserving biased restriction to address the anisotropy in time and convections in space. The main novelty of this paper is that we propose adding artificial viscosity to the direct discretization coarse grid operators, such that the coarse grid error estimations are more accurate. We use Fourier analysis to illustrate the efficiency of our proposed multigrid method. Numerical experiments show that the convergence rate of the proposed multigrid method is mesh-independent and faster than the existing methods in the literature.

previous article A Spherical Harmonic Discontinuous Galerkin Method for Radiative Transfer Equations with Vacuum Boundary Conditions

next article A Preconditioning Technique for an All-at-once System from Volterra Subdiffusion Equations with Graded Time Steps

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

In some applications, the Hamiltonian is convex in \({\mathbf {c}}\). Then “max" in (1) is replaced by “min".

\(\sigma =0.005\) in Equation (4)-(6) corresponds to \(\sigma =0.1\) (namely \(\sigma ^2/2=0.005\)) in [15].

Achdou, Y.: Finite difference methods for mean field games. In: Hamilton-Jacobi equations: approximations, numerical analysis and applications, Lecture Notes in Math., vol. 2074, pp. 1–47. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36433-4_1

Achdou, Y., Camilli, F., Capuzzo-Dolcetta, I.: Mean field games: numerical methods for the planning problem. SIAM J. Control Optim. 50(1), 77–109 (2012). https://doi.org/10.1137/100790069MathSciNetCrossRefMATH

Achdou, Y., Camilli, F., Capuzzo-Dolcetta, I.: Mean field games: convergence of a finite difference method. SIAM J. Numer. Anal. 51(5), 2585–2612 (2013). https://doi.org/10.1137/120882421MathSciNetCrossRefMATH

Achdou, Y., Capuzzo-Dolcetta, I.: Mean field games: numerical methods. SIAM J. Numer. Anal. 48(3), 1136–1162 (2010). https://doi.org/10.1137/090758477MathSciNetCrossRefMATH

Achdou, Y., Perez, V.: Iterative strategies for solving linearized discrete mean field games systems. Netw. Heterog. Media 7(2), 197–217 (2012). https://doi.org/10.3934/nhm.2012.7.197MathSciNetCrossRefMATH

Andreev, R.: Preconditioning the augmented Lagrangian method for instationary mean field games with diffusion. SIAM J. Sci. Comput. 39(6), A2763–A2783 (2017). https://doi.org/10.1137/16M1072346MathSciNetCrossRefMATH

Briceño Arias, L.M., Kalise, D., Silva, F.J.: Proximal methods for stationary mean field games with local couplings. SIAM J. Control Optim. 56(2), 801–836 (2018). https://doi.org/10.1137/16M1095615MathSciNetCrossRefMATH

Bank, R.E., Coughran Jr., W., Cowsar, L.C.: The finite volume scharfetter-gummel method for steady convection diffusion equations. Comput. Vis. Sci. 1(3), 123–136 (1998)CrossRef

Bank, R.E., Wan, J.W.L., Qu, Z.: Kernel preserving multigrid methods for convection-diffusion equations. SIAM J. Matrix Anal. Appl. 27(4), 1150–1171 (2006). https://doi.org/10.1137/040619533MathSciNetCrossRefMATH

10.

Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comp. 31(138), 333–390 (1977)MathSciNetCrossRef

11.

Brandt, A., Yavneh, I.: On multigrid solution of high-Reynolds incompressible entering flows. J. Comput. Phys. 101(1), 151–164 (1992). https://doi.org/10.1016/0021-9991(92)90049-5MathSciNetCrossRefMATH

12.

Briceño-Arias, L., Kalise, D., Kobeissi, Z., Laurière, M., González, Á.M., Silva, F.J.: On the implementation of a primal-dual algorithm for second order time-dependent mean field games with local couplings. arXiv preprint arXiv:1802.07902 (2018)

13.

Carlini, E., Silva, F.J.: A semi-Lagrangian scheme for a degenerate second order mean field game system. Dis. Contin. Dyn. Syst. 35(9), 4269–4292 (2015). https://doi.org/10.3934/dcds.2015.35.4269MathSciNetCrossRefMATH

14.

Carlini, E., Silva, F.J.: On the discretization of some nonlinear Fokker-Planck-Kolmogorov equations and applications. SIAM J. Numer. Anal. 56(4), 2148–2177 (2018). https://doi.org/10.1137/17M1143022MathSciNetCrossRefMATH

15.

Chan, P., Sircar, R.: Bertrand and cournot mean field games. Appl. Math. Optim. 71(3), 533–569 (2015)MathSciNetCrossRef

16.

Chen, L., Jakobsen, E.R., Naess, A.: On numerical density approximations of solutions of SDEs with unbounded coefficients. Adv. Comput. Math. 44(3), 693–721 (2018). https://doi.org/10.1007/s10444-017-9558-4MathSciNetCrossRefMATH

17.

Djehiche, B., Tcheukam, A., Tembine, H.: Mean-field-type games in engineering. arXiv preprint arXiv:1605.03281 (2016)

18.

Forsyth, P.A., Labahn, G.: Numerical methods for controlled Hamilton-Jacobi-Bellman PDEs in finance. J. Comput. Fin. 11(2), 1 (2007)CrossRef

19.

Franca, L.P., Frey, S.L., Hughes, T.J.R.: Stabilized finite element methods. I. Application to the advective-diffusive model. Comput. Methods Appl. Mech. Engrg. 95(2), 253–276 (1992). https://doi.org/10.1016/0045-7825(92)90143-8

20.

Friedhoff, S., MacLachlan, S.: A generalized predictive analysis tool for multigrid methods. Num. Linear Algebra Appl. 22(4), 618–647 (2015)MathSciNetCrossRef

21.

Gander, M.J.: 50 years of time parallel time integration. In: Multiple Shooting and Time Domain Decomposition Methods, pp. 69–113. Springer (2015)

22.

Gander, M.J., Neumüller, M.: Analysis of a new space-time parallel multigrid algorithm for parabolic problems. SIAM J. Sci. Comput. 38(4), A2173–A2208 (2016). https://doi.org/10.1137/15M1046605MathSciNetCrossRefMATH

23.

Graber, P.J., Bensoussan, A.: Existence and uniqueness of solutions for Bertrand and Cournot mean field games. Appl. Math. Optim. 77(1), 47–71 (2018). https://doi.org/10.1007/s00245-016-9366-0MathSciNetCrossRefMATH

24.

Guéant, O., Lasry, J.M., Lions, P.L.: Mean field games and applications. In: Paris-Princeton lectures on mathematical finance 2010, pp. 205–266. Springer (2011)

25.

Hackbusch, W.: Multi-grid methods and applications, vol. 4. Springer Science & Business Media (2013)

26.

Han, D., Wan, J.W.L.: Multigrid methods for second order Hamilton-Jacobi-Bellman and Hamilton-Jacob-Bellman-Isaacs equations. SIAM J. Sci. Comput. 35(5), S323–S344 (2013). https://doi.org/10.1137/120881476MathSciNetCrossRefMATH

27.

Horton, G., Vandewalle, S.: A space-time multigrid method for parabolic partial differential equations. SIAM J. Sci. Comput. 16(4), 848–864 (1995). https://doi.org/10.1137/0916050MathSciNetCrossRefMATH

28.

Howard, R.A.: Dynamic programming and Markov processes. The Technology Press of M.I.T., Cambridge, Mass.; John Wiley & Sons, Inc., New York-London (1960)

29.

Hughes, T.J., Franca, L.P., Hulbert, G.M.: A new finite element formulation for computational fluid dynamics: Viii. the galerkin/least-squares method for advective-diffusive equations. Comput. Methods Appl. Mech. Eng. 73(2), 173–189 (1989)MathSciNetCrossRef

30.

Lachapelle, A., Salomon, J., Turinici, G.: Computation of mean field equilibria in economics. Math. Models Methods Appl. Sci. 20(4), 567–588 (2010). https://doi.org/10.1142/S0218202510004349MathSciNetCrossRefMATH

31.

Lasry, J.M., Lions, P.L.: Jeux à champ moyen. I-le cas stationnaire. Comptes Rendus Mathématique 343(9), 619–625 (2006)CrossRef

32.

Lasry, J.M., Lions, P.L.: Jeux à champ moyen. II–horizon fini et contrôle optimal. Comptes Rendus Mathématique 343(10), 679–684 (2006)

33.

Lasry, J.M., Lions, P.L.: Mean field games. Jpn. J. Math. 2(1), 229–260 (2007). https://doi.org/10.1007/s11537-007-0657-8MathSciNetCrossRefMATH

34.

Lax, P., Wendroff, B.: Systems of conservation laws. Comm. Pure Appl. Math. 13, 217–237 (1960). https://doi.org/10.1002/cpa.3160130205MathSciNetCrossRefMATH

35.

Rhebergen, S., Cockburn, B., van der Vegt, J.J.W.: A space-time discontinuous Galerkin method for the incompressible Navier-Stokes equations. J. Comput. Phys. 233, 339–358 (2013). https://doi.org/10.1016/j.jcp.2012.08.052MathSciNetCrossRefMATH

36.

Toro, E.F.: Riemann solvers and numerical methods for fluid dynamics: a practical introduction. Springer Science & Business Media (2013)

37.

Trottenberg, U., Oosterlee, C.W., Schüller, A.: Multigrid. Academic Press, Inc., San Diego, CA (2001). With contributions by A. Brandt, P. Oswald and K. Stüben

38.

Wienands, R., Oosterlee, C.W.: On three-grid Fourier analysis for multigrid. SIAM J. Sci. Comput. 23(2), 651–671 (2001)MathSciNetCrossRef

Title: Artificial Viscosity Joint Spacetime Multigrid Method for Hamilton–Jacobi–Bellman and Kolmogorov–Fokker–Planck System Arising from Mean Field Games
Authors: Yangang Chen
Justin W. L. Wan
Publication date: 01-07-2021
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 1/2021
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-021-01520-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2021

Orthogonal Jacobi Rational Functions and Spectral Methods on the Half Line

On Thermodynamically Compatible Finite Volume Methods and Path-Conservative ADER Discontinuous Galerkin Schemes for Turbulent Shallow Water Flows

Stability and Conservation Properties of Hermite-Based Approximations of the Vlasov-Poisson System

Unconditional Energy Dissipation and Error Estimates of the SAV Fourier Spectral Method for Nonlinear Fractional Generalized Wave Equation

Stability of Discontinuous Galerkin Spectral Element Schemes for Wave Propagation when the Coefficient Matrices have Jumps

Data-Driven Extrapolation Via Feature Augmentation Based on Variably Scaled Thin Plate Splines

Premium Partner