Mean Field Type Control with Congestion (II): An Augmented Lagrangian Method

Applied Mathematics & Optimization - Tập 74 - Trang 535-578 - 2016
Yves Achdou1, Mathieu Laurière1
1Laboratoire Jacques-Louis Lions, UMR 7598, UPMC, CNRS, Univ. Paris Diderot, Sorbonne Paris Cité, Paris, France

Tóm tắt

This work deals with a numerical method for solving a mean-field type control problem with congestion. It is the continuation of an article by the same authors, in which suitably defined weak solutions of the system of partial differential equations arising from the model were discussed and existence and uniqueness were proved. Here, the focus is put on numerical methods: a monotone finite difference scheme is proposed and shown to have a variational interpretation. Then an Alternating Direction Method of Multipliers for solving the variational problem is addressed. It is based on an augmented Lagrangian. Two kinds of boundary conditions are considered: periodic conditions and more realistic boundary conditions associated to state constrained problems. Various test cases and numerical results are presented.

Tài liệu tham khảo

Achdou, Y.: Hamilton–Jacobi equations: approximations, numerical analysis and applications, Lecture Notes in Math. In: Loreti, P., Tchou, N.A. (eds.) Finite Difference Methods for Mean Field Games, vol. 2074, pp. 1–47. Springer, Heidelberg (2013)

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)

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)

Achdou, Y., Capuzzo-Dolcetta, I.: Mean field games: numerical methods. SIAM J. Numer. Anal. 48(3), 1136–1162 (2010)

Achdou, Y., Lasry, J.-M.: Mean field games for modeling crowd motion, preprint

Achdou, Y., Laurière, M.: On the system of partial differential equations arising in mean field type control. Discret. Contin. Dyn. Syst. 35(9), 3879–3900 (2015)

Achdou, Y., Laurière, M.: Mean field type control with congestion. Appl. Math. Optim. 73(3), 393–418 (2016)

Achdou, Y., Porretta, A.: Mean field games with congestion, in preparation

Achdou, Y., Porretta, A.: Convergence of a finite difference scheme to weak solutions of the system of partial differential equations arising in mean field games. SIAM J. Numer. Anal. 54(1), 161–186 (2016)

Andreev, R.: Preconditioning the augmented lagrangian method for instationary mean field games with diffusion. (2016)

Benamou, J.-D., Brenier, Y.: A computational fluid mechanics solution to the monge-kantorovich mass transfer problem. Numer. Math. 84(3), 375–393 (2000)

Benamou, J.-D., Carlier, G.: Augmented lagrangian methods for transport optimization, mean field games and degenerate elliptic equations. J. Optim. Theory Appl. 167(1), 1–26 (2015)

Bensoussan, A., Frehse, J.: Control and Nash games with mean field effect. Chin. Ann. Math. Ser. B 34(2), 161–192 (2013)

Bensoussan, A., Frehse, J., Yam, P.: Mean field games and mean field type control theory, Springer Briefs in Mathematics. Springer, New York (2013)

Cardaliaguet, P., Carlier, G., Nazaret, B.: Geodesics for a class of distances in the space of probability measures. Calc. Var. Part. Differ. Equ. 48(3–4), 395–420 (2013)

Cardaliaguet, P., Graber, J., Porretta, A., Tonon, D.: Second order mean field games with degenerate diffusion and local coupling. NoDEA Nonlinear Differ. Equ. Appl. 22(5), 1287–1317 (2015)

Carmona, R., Delarue, F.: Mean field forward-backward stochastic differential equations. Electron. Commun. Probab. 18(68), 15 (2013)

Carmona, R., Delarue, F., Lachapelle, A.: Control of McKean–Vlasov dynamics versus mean field games. Math. Financ. Econ. 7(2), 131–166 (2013)

Eckstein, J., Bertsekas, D.P.: On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1–3), 293–318 (1992)

Eckstein, J., Yao, W.: Augmented lagrangian and alternating direction methods for convex optimization: a tutorial and some illustrative computational results. RUTCOR Res. Rep. 32 (2012)

Fortin, M., Glowinski, R.: Augmented lagrangian methods: applications to the numerical solution of boundary-value problems. Elsevier, Amsterdam (2000)

Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Compu. Math. Appl. 2(1), 17–40 (1976)

Gomes, D.A., Saúde, J.: Mean field games models—a brief survey. Dyn. Games Appl. 4(2), 110–154 (2014)

Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)

Lasry, J.-M., Lions, P.-L.: Jeux à champ moyen. I. Le cas stationnaire. C. R. Math. Acad. Sci. Paris 343(9), 619–625 (2006)

Lasry, J.-M., Lions, P.-L.: Jeux à champ moyen. II. Horizon fini et contrôle optimal. C. R. Math. Acad. Sci. Paris 343(10), 679–684 (2006)

Lasry, J.-M., Lions, P.-L.: Mean field games. Jpn. J. Math. 2(1), 229–260 (2007)

Lions, P.-L.: Cours du Collège de France. http://www.college-de-france.fr/default/EN/all/equ_der/ (2007–2011)

Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)

McKean Jr., H.P.: A class of Markov processes associated with nonlinear parabolic equations. Proc. Nat. Acad. Sci. USA 56, 1907–1911 (1966)

Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 127–239 (2014)

Porretta, A.: Weak solutions to Fokker–Planck equations and mean field games. Arch. Ration. Mech. Anal. 216, 1–62 (2014)

Powell, M.J.D.: A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele), vol. 1969, pp. 283–298. Academic Press. London (1968)

Rockafellar, R.T.: Convex analysis, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, Reprint of the 1970 original, Princeton Paperbacks (1997)

Sznitman, A.-S.: Topics in propagation of chaos. In: École d’Été de Probabilités de Saint-Flour XIX—1989, Lecture Notes in Math., vol. 1464, pp. 165–251. Springer, Berlin (1991)

van der Vorst, H.A.: Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 13(2), 631–644 (1992)

Thông tin
Thông tin xuất bản

Applied Mathematics & Optimization

Tập 74

535-578

Thông tin tác giả