Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the implementation of a primal-dual algorithm for second order time-dependent mean field games with local couplings
68
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study a numerical approximation of a time-dependent Mean Field Game (MFG) system with local couplings. The discretization we consider stems from a variational approach described in [Briceno-Arias, Kalise, and Silva, SIAM J. Control Optim., 2017] for the stationary problem and leads to the finite difference scheme introduced by Achdou and Capuzzo-Dolcetta in [SIAM J. Numer. Anal., 48(3):1136-1162, 2010]. In order to solve the finite dimensional variational problems, in [Briceno-Arias, Kalise, and Silva, SIAM J. Control Optim., 2017] the authors implement the primal-dual algorithm introduced by Chambolle and Pock in [J. Math. Imaging Vision, 40(1):120-145, 2011], whose core consists in iteratively solving linear systems and applying a proximity operator. We apply that method to time-dependent MFG and, for large viscosity parameters, we improve the linear system solution by replacing the direct approach used in [Briceno-Arias, Kalise, and Silva, SIAM J. Control Optim., 2017] by suitable preconditioned iterative algorithms.
rate research
Read More
We address the numerical approximation of Mean Field Games with local couplings. For power-like Hamiltonians, we consider both unconstrained and constrained stationary systems with density constraints in order to model hard congestion effects. For finite difference discretizations of the Mean Field Game system, we follow a variational approach. We prove that the aforementioned schemes can be obtained as the optimality system of suitably defined optimization problems. In order to prove the existence of solutions of the scheme with a variational argument, the monotonicity of the coupling term is not used, which allow us to recover general existence results. Next, assuming next that the coupling term is monotone, the variational problem is cast as a convex optimization problem for which we study and compare several proximal type methods. These algorithms have several interesting features, such as global convergence and stability with respect to the viscosity parameter, which can eventually be zero. We assess the performance of the methods via numerical experiments.
We analyze a (possibly degenerate) second order mean field games system of partial differential equations. The distinguishing features of the model considered are (1) that it is not uniformly parabolic, including the first order case as a possibility, and (2) the coupling is a local operator on the density. As a result we look for weak, not smooth, solutions. Our main result is the existence and uniqueness of suitably defined weak solutions, which are characterized as minimizers of two optimal control problems. We also show that such solutions are stable with respect to the data, so that in particular the degenerate case can be approximated by a uniformly parabolic (viscous) perturbation.
The aim of this paper is to study the long time behavior of solutions to deterministic mean field games systems on Euclidean space. This problem was addressed on the torus ${mathbb T}^n$ in [P. Cardaliaguet, {it Long time average of first order mean field games and weak KAM theory}, Dyn. Games Appl. 3 (2013), 473-488], where solutions are shown to converge to the solution of a certain ergodic mean field games system on ${mathbb T}^n$. By adapting the approach in [A. Fathi, E. Maderna, {it Weak KAM theorem on non compact manifolds}, NoDEA Nonlinear Differential Equations Appl. 14 (2007), 1-27], we identify structural conditions on the Lagrangian, under which the corresponding ergodic system can be solved in $mathbb{R}^{n}$. Then we show that time dependent solutions converge to the solution of such a stationary system on all compact subsets of the whole space.
We propose a new viewpoint on variational mean-field games with diffusion and quadratic Hamiltonian. We show the equivalence of such mean-field games with a relative entropy minimization at the level of probabilities on curves. We also address the time-discretization of such problems, establish $Gamma$-convergence results as the time step vanishes and propose an efficient algorithm relying on this entropic interpretation as well as on the Sinkhorn scaling algorithm.
In this paper we propose a primal-dual homotopy method for $ell_1$-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
