{'fraction_non_alphanumeric': 0.058868594008306116, 'fraction_numerical': 0.020301600741905568, 'mean_word_length': 3.7133219308247813, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A variational finite volume scheme for Wasserstein gradient flows

We propose a variational finite volume scheme to approximate the solutions to Wasserstein gradient flows. The time discretization is based on an implicit linearization of the Wasserstein distance expressed thanks to Benamou-Brenier formula, whereas space discretization relies on upstream mobility two-point flux approximation finite volumes. Our scheme is based on a first discretize then optimize approach in order to preserve the variational structure of the continuous model at the discrete level. Our scheme can be applied to a wide range of energies, guarantees non-negativity of the discrete solutions as well as decay of the energy. We show that our scheme admits a unique solution whatever the convex energy involved in the continuous problem, and we prove its convergence in the case of the linear Fokker-Planck equation with positive initial density. Numerical illustrations show that it is first order accurate in both time and space, and robust with respect to both the energy and the initial profile.


1.
A strategy to approximate Wasserstein gradient flows 1.1. Generalities about Wasserstein gradient flows. Given a convex and bounded open subset Ω of R d , a strictly convex and proper energy functional E : L 1 (Ω; R + ) → [0, +∞], and given an initial density ρ 0 ∈ L 1 (Ω; R + ) with finite energy, i.e. such that E(ρ 0 ) < +∞, we want to solve problems of the form: in Ω.
Equation (1) expresses the continuity equation for a time evolving density , starting from the initial condition ρ 0 , convected by the velocity field −∇ δE δρ [ ]. The mixed boundary condition the system is subjected to represents a no flux condition across the boundary of the domain for the mass: the total mass is therefore preserved.
It is now well understood since the pioneering works of Otto [33,50,51] that equations of the form of (1) can be interpreted as the gradient flow in the Wasserstein space w.r.t. the energy E [2]. A gradient flow is an evolution stemming from an initial condition and evolving at each time following the steepest decreasing direction of a prescribed functional. Consider the space P(Ω) of nonnegative measures defined on the bounded and convex domain Ω with prescribed total mass that are absolutely continuous w.r.t. the Lebesgue measure (hence P(Ω) ⊂ L 1 (Ω; R + )). The Wasserstein distance W 2 between two densities ρ, µ ∈ P(Ω) is the cost to transport one into the other in an optimal way with respect to the cost given by the squared euclidean distance, namely the optimization problem (2) W 2 2 (ρ, µ) = min γ∈Γ(ρ,µ) Ω×Ω |y − x| 2 dγ(x, y), 1 with the set Γ(ρ, µ) of admissible transport plans given by Γ(ρ, µ) = γ ∈ P(Ω × Ω) : γ 1 = ρ, γ 2 = µ , where γ 1 , γ 2 denote the first and second marginal measure, respectively. A typical example of problem entering the framework of (1) is the linear Fokker-Planck equation complemented with no-flux boundary conditions and an initial condition. In (3), V ∈ W 1,∞ (Ω) denotes a Lipschitz continuous exterior potential. In this case, the energy functional is The potential V is defined up to an additive constant, which can be adjusted so that the densities e −V and ρ 0 have the same mass. Beside this simple example studied for instance in [33,10], many problems have been proven to exhibit the same variational structure. Porous media flows [51,37,15], magnetic fluids [50], supraconductivity [4,3], crowd motions [45], aggregation processes in biology [22,9], semiconductor devices modelling [35], or multiphase mixtures [18,32] are just few examples of problems that can be represented as gradient flows in the Wasserstein space. Designing efficient numerical schemes for approximating their solutions is therefore a major issue and our leading motivation.
1.2. JKO semi-discretization. An intriguing question is how to solve numerically a gradient flow. Problem (1) can of course be directly discretized and solved using one of the many tools available nowadays for the numerical approximation of partial differential equations. The development of energy diminishing numerical methods based on classical ODE solvers for the march in time has been the purpose of many contributions in the recent past, see for instance [8,16,17,13,54,49,19]. Nevertheless, the aforementioned methods disregard the fact that the trajectory aims at optimizing the energy decay, in opposition to methods based on minimizing movement scheme (often called JKO scheme after [33]). This scheme can be thought as a generalization to the space P(Ω) (the mass being defined by the initial data ρ 0 ) equipped with the metric W 2 of the backward Euler scheme and writes: (5) ρ 0 τ = ρ 0 , ρ n τ ∈ argmin ρ 1 2τ W 2 2 (ρ, ρ n−1 τ ) + E(ρ).
The parameter τ is the time discretization step. Scheme (5) generates a sequence of measures (ρ n τ ) n≥1 . Using this sequence it is possible to construct a time dependent measure by gluing them together in a piecewise constant (in time) fashion: ρ τ (t) = ρ n τ , for t ∈ (t n−1 = (n − 1)τ, t n = nτ ]. Under suitable assumptions on the functional E, it is possible to prove the uniform convergence in time of this measure to weak solutions of (1) (see for instance [2] or [53]).
Lagrangian numerical methods appear to be very natural (especially in dimension 1) to approximate the Wasserstein distance and thus the solution to (5). This was already noticed in [36], and motivated numerous contributions, see for instance [43,12,44,34,23,20,38]. In our approach, we rather consider an Eulerian method based on Finite Volumes for the space discretization. The link between monotone Finite Volumes and optimal transportation was simultaneously highlighted by Mielke [46] and Maas [41,29,25,42,30]. But these works only focuses on the space discretization, whereas we are interested in the fully discrete setting. Moreover, the approximation based on upstream mobility we propose in Section 2.3 does not enter their framework. Last but not least, let us mention the so-called ALG2-JKO scheme [7,14] where the optimization problem (5) is discretized and then solved thanks to an augmented Lagrangian iterative method. Our approach is close to the one of [7], with the goal to obtain a faster numerical solver.
Thanks to formal calculations, let us highlight the connection of the minimization problem involved at each step of (5) with a system coupling a forward in time conservation law with a backward in time Hamilton-Jacobi (HJ) equation. The problem can be rewritten thanks to Benamou-Brenier dynamic formulation of optimal transport [6] as (6) inf where the density and velocity curves satisfy weakly The next value ρ n τ is chosen equal to ρ(t n ) for the optimal ρ in (6)- (7). Using the momentum m = ρv instead of v as a variable, and incorporating the constraint (7) in (6) yields the saddlepoint problem We will refer to (8) as the primal problem. The dual problem is obtained by exchanging inf and sup in (8). Strong duality can be proven and the problem hence does not change. Optimizing first w.r.t. m leads to m = −ρ∇φ, so that the dual problem writes Because of the first term in (9), the infimum is equal to −∞ unless −∂ t φ + 1 2 |∇φ| 2 ≤ 0 a.e. in Ω × (t n−1 , t n ), with equality ρ-almost everywhere since ρ ≥ 0. Moreover, optimizing w.r.t. ρ(t n ) provides that φ(t n ) ≤ δE δρ [ρ(t n )] with equality ρ(t n )-almost everywhere. Hence the dual problem can be rewritten as (10) sup subject to the constraints in Ω.
On the one hand the monotonicity of the backward HJ equation −∂ t φ + 1 2 |∇φ| 2 = f with respect to its right-hand side f ≤ 0 implies that given φ(t n ), the solution (which exists) of −∂ t φ+ 1 2 |∇φ| 2 = 0 gives a bigger value at φ(t n−1 ) and thus a better competitor for (11). On the other given φ, among all the ρ satisfying the constraint, the competitorρ = δE δρ −1 (φ(t n )) is optimal. Indeed let At the end of the day, the primal-dual optimality conditions of problem (5) finally amounts to the mean field game in Ω.
The approximation of the system (12) is a natural strategy to approximate the solution to (1). This approach was for instance at the basis of the works [7,21]. These methods require a sub-time stepping to solve system (12) on each interval (t n−1 , t n ), yielding a possibly important computational cost. The avoidance of this sub-time stepping is the main motivation of the time discretization we propose now.
In the above formula, we denoted by Indeed, in view of (14)- (15), there holds Equation (15) can be thought as a linearization of the Monge-Ampère equation.
In view of (13), a natural idea is to replace the Wasserstein distance by the weightedḢ −1 ρ norm in (5), leading to what we call the implicitly linearized JKO (or LJKO) scheme: (16) ρ n τ ∈ argmin The choice of an implicit weight ρ in (16) appears to be particularly important when {ρ n−1 τ = 0} has a non-empty interior set, which can not be properly invaded by the ρ n τ if one chooses the explicit (but computationally cheaper) weight ρ n−1 τ as in [48]. Our time discretization is close to the one that was proposed very recently in [40] where the introduction on inner time stepping was also avoided. In [40], the authors introduce a regularisation term based on Fisher information, which mainly amounts to stabilize the scheme thanks to some additional non-degenerate diffusion. In our approach, we manage to avoid this additional stabilization term by taking advantage of the monotonicity of the involved operators.
At each step n ≥ 1, (16) can be formulated as a constrained optimization problem. To highlight its convexity, we perform the change of variables (ρ, ψ) → (ρ, m = −ρ∇ψ), in analogy with (6), and rewrite step n as: Incorporating the constraint in the above formulation yields the following inf-sup problem: the supremum w.r.t. φ being +∞ unless the constraint is satisfied. Problem (18) is strictly convex in (ρ, m) and concave (since linear) in φ. Exploiting Fenchel-Rockafellar duality theory it is possible to show that strong duality holds, so that (18) is equivalent to its dual problem where the inf and the sup have been swapped. Optimizing w.r.t. to m yields the optimality condition m = −τ ρ∇φ, hence the problem reduces to The problem is now strictly convex in ρ and concave in φ. Optimizing w.r.t. ρ leads to the optimality condition with equality on {ρ n τ > 0}. In the above formula, φ n τ denote the optimal φ realizing the sup in (19). Similarly to was was done in the previous section for the JKO scheme, it is possible to show again that saturating inequality (20) on {ρ n τ = 0} is optimal since the mapping f → φ solution to φ + τ 2 |∇φ| 2 = f is monotone. Finally, the optimality conditions for the LJKO problem (16) write set on Ω, complemented with homogeneous Neumann boundary condition ∇φ n τ · n = 0 on ∂Ω. We can interpret (21) as the one step resolvent of the mean-field game (12). Both the forward in time continuity equation and the backward in time HJ equation are discretized thanks to one step of backward Euler scheme.
1.4. Goal and organisation of the paper. As already noted, most of the numerical methods based on backward Euler scheme disregard the optimal character of the trajectory t → (t) of the exact solution to (1). Rather than discretizing directly the PDE (1), which can be thought as the Euler-Lagrange equation for the steepest descent of the energy, we propose to first discretize w.r.t. space the functional appearing in the optimization problem (16), and then to optimize. The corresponding Euler-Lagrange equations will then encode the optimality of the trajectory. The choice of the LJKO scheme (16) rather than the classical JKO scheme (5) is motivated by the fact that solving (21) is computationally affordable. Indeed, it merely demands to approximate two functions ρ n τ , φ n τ rather than time depending trajectories in function space as for the JKO scheme (12). This allows in particular to avoid inner time stepping as in [7,21], making our approach much more tractable to solve complex problems.
Two-Point Flux Approximation (TPFA) Finite Volumes are a natural solution for the space discretization. The are naturally locally conservative thus well-suited to approximate the conservation laws. Moreover, they naturally transpose to the discrete setting the monotonicity properties of the continuous operators. Monotonicity was crucial in the derivation of the optimality conditions (21), as it will also be the case in the fully discrete framework later on. This led us to use upstream mobilities in the definition of the discrete counterpart of the squaredḢ 1 ρ norm. The system (21) thus admits a discrete counterpart (36). The derivation of the fully discrete Finite Volume scheme based on the LJKO time discretization is performed in Section 2, where we also establish the wellposedness of the scheme, as well as the preservation at the discrete level of fundamental properties of the continuous model, namely the non-negativity of the densities and the decay of the energy along time. In Section 3, we show that our scheme converges in the case of the Fokker-Planck equation (3) under the assumption that the initial density is bounded from below by a positive constant. Even though we do not treat problem (1) in its full generality, this results shows for the consistency of the scheme. Finally, Section 4 is devoted to numerical results, where our scheme is tested on several problems including systems.

A variational Finite Volume scheme
The goal of this section is to define the fully discrete scheme to solve (1), and to exhibit some important properties of the scheme. But at first, let us give some assumptions and notations on the mesh.
2.1. Discretization of Ω. The domain Ω ⊂ R d is assumed to be polygonal if d = 2 or polyhedral if d = 3. The specifications on the mesh are classical for TPFA Finite Volumes [27]. More precisely, an admissible mesh of Ω is a triplet T , Σ, (x K ) K∈T such that the following conditions are fulfilled.
(i) Each control volume (or cell) K ∈ T is non-empty, open, polyhedral and convex. We assume For all K ∈ T , we assume that there exists a subset Σ K of Σ such that ∂K = σ∈Σ K σ. Moreover, we suppose that K∈T Σ K = Σ. Given two distinct control volumes K, L ∈ T , the intersection K ∩ L either reduces to a single face σ ∈ Σ denoted by K|L, or its (d − 1)-dimensional Hausdorff measure is 0.
(iii) The cell-centers (x K ) K∈T ⊂ Ω are pairwise distinct and are such that, if K, L ∈ T share a face K|L, then the vector x L − x K is orthogonal to K|L and has the same orientation as the normal n KL to K|L outward w.r.t. K.
Cartesian grids, Delaunay triangulations or Voronoï tessellations are typical examples of admissible meshes in the above sense. Since no boundary fluxes appear in our problem, the boundary faces Σ ext = {σ ⊂ ∂Ω} are not involved in our computations. Nonzeros fluxes may only occur across internal faces σ ∈ Σ = Σ \ Σ ext . We denote by Σ K = Σ K ∩ Σ the internal faces belonging to ∂K, and by N K the neighboring cells of K, i.e., N K = {L ∈ T | K|L ∈ Σ K }. For each internal face σ = K|L ∈ Σ, we refer to the diamond cell ∆ σ as the polyhedron whose edges join x K and x L to the vertices of σ. The diamond cell ∆ σ is convex if x K ∈ K and x L ∈ L. Denoting by d σ = |x K − x L |, the measure m ∆σ of ∆ σ is then equal to m σ d σ /d, where d stands for the space dimension. The transmissivity of the face σ ∈ Σ is defined by a σ = m σ /d σ .
The space R T is equipped with the scalar product which mimics the usual scalar product on L 2 (Ω).

2.2.
Upstream weighted dissipation potentials. Since the LJKO time discretization presented in Section 1.3 relies on weightedḢ 1 ρ and H −1 ρ norms, we introduce the discrete counterparts to be used in the sequel. As it will be explained in what follows, the upwinding yields to problems to introduce discrete counterparts to the norms. To bypass this difficulty, we adopt a formalism based on dissipation potentials inspired from the one of generalized gradient flows introduced by Mielke in [46]. This framework was used for instance to study the convergence of the semi-discrete in space squareroot Finite Volume approximation of the Fokker-Planck equation, see [31].
Let us now turn to the definition of the discrete counterpart of 1 . To this end, we introduce the space F T ⊂ R 2Σ of conservative fluxes. An element F of F T is made of two outward fluxes F Kσ , F Lσ for each σ = K|L ∈ Σ, and one flux F Kσ per boundary face σ ∈ Σ K . We impose the conservativity across each internal faces In what follows, we denote by F σ = |F Kσ | = |F L,σ |. There are no flux across the boundary faces. The space F T is then defined as Now, we define the subspace where the minimization over F is restricted to the linear subspace of F T such that In (25), ρ σ denotes the upwind value w.r.t. F , i.e., In the case where some ρ σ vanish, we adopt the following convention in (25) and in what follows: Remark that this condition is similar to the one implicitly used in (8) and (17). Summing (26) over K ∈ T and using the conservativity across the edges (24), one notices that there is no F ∈ F T satisfying (26) unless h ∈ R T 0 . But when h ∈ R T 0 , the minimization set in (25) is never empty. Note that Ψ T (ρ; h) may take infinite values when ρ vanishes on some cells, for instance Ψ T (ρ; h) = +∞ if h K > 0 and ρ K = 0 for some K ∈ T . Formula (25) deserves some comments. This sum is built to approximate Ω |m| 2 2ρ dx. The flux F σ approximates |m · n σ |, and thus encodes the information on m only in the one direction (normal to the face σ) over d. But on the other hand, the volume d σ m σ is equal to dm ∆σ which allows to hope that the sum is a consistent approximation of the integral. This remark has a strong link with the notion of inflated gradients introduced in [24,26]. The convergence proof carried out in Section 3 somehow shows the non-obvious consistency of this formula.
At the continuous level, the norms · Ḣ1 ρ and · H −1 ρ are in duality. This property is transposed to the discrete level in the following sense.
are one another Legendre transforms in the sense that In particular, both are proper convex l.s.c. functionals. Moreover, if Ψ T (ρ; h) is finite, then there exists a discrete Kantorovitch potential φ solving Proof. Let ρ ≥ 0 be fixed. Incorporating the constraint (26) in (25), and using the definition of ρ σ and the twice conservativity constraint (24), we obtain the saddle point primal problem The functional in the right-hand side is convex and coercive w.r.t. F and linear w.r.t. φ, so that strong duality holds. We can exchange the sup and the inf in the above formula to obtain the dual problem, and we minimize first w.r.t. F , leading to in the dual problem leads to (28), while the constraint (26) turns to (29). The fact that Ψ * T (ρ, ·) is also the Legendre transform of Ψ T (ρ, ·) follows from the fact that it is convex l.s.c., hence equal to its relaxation.
When Ψ T (ρ; h) is finite, then the supremum in (28) is achieved, ensuring the existence of the corresponding discrete Kantorovitch potentials φ. Finally, multiplying (29) by the optimal φ K and by summing over K ∈ T yields h, φ T = 2Ψ * T (ρ; φ). Substituting this relation in (28) shows the relation Ψ T (ρ; h) = Ψ * T (ρ; φ). Our next lemma can be seen as an adaptation to our setting of a well known properties of optimal transportation, namely ρ → 1 2 W 2 2 (ρ, µ) is convex, which is key in the study of Wasserstein gradient flows.
is defined as the supremum of linear functions, whence it is convex.

2.3.
A variational upstream mobility Finite Volume scheme. The finite volume discretization replaces the functions ρ n τ , φ n τ at time step n ≥ 1 defined on Ω with the vectors ρ n ∈ R T + and φ n ∈ R T . In each cell K, the restriction of each of these functions is approximated by a single real number ρ n K , φ n K , which can be thought as its mean value located in the cell center x K . Given ρ 0 ∈ R T + , the space P T which is the discrete counterpart of P(Ω) is then defined by The energy E is discretized into a strictly convex functional E T ∈ C 1 (R T + ; R + ) that we do not specify yet. We refer to Sections 3 and 4 for explicit examples.
We have introduced all the necessary material to introduce our numerical scheme, which combines upstream weighted Finite Volumes for the space discretization and the LJKO time discretization: (32) ρ n ∈ argmin A further characterization of the scheme is needed for its practical implementation, but the condensed expression (32) already provides crucial informations gathered in the following theorem. Note in particular that our scheme automatically preserves mass and the positivity since the solutions (ρ n ) n≥1 belong to P T .
3. For all n ≥ 1, there exists a unique solution ρ n ∈ P T to (32). Moreover, energy is dissipated along the time steps. More precisely, s.c. and strictly convex on the compact set P T in view of Lemma 2.2 and of the assumptions on E T . Moreover, it is proper since ρ n−1 belongs to its domain. Therefore, it admits a unique minimum on P T . The energy / energy dissipation estimate (33) is obtained by choosing ρ = ρ n−1 as a competitor in (32).
In view of (31), and after rescaling the dual variable φ ← φ τ , solving (32) amounts to solve the saddle point problem which is equivalent to its dual problem Our strategy for the practical computation of the solution to (32) is to solve the system corresponding to the optimality conditions of (35). So far, we did not take advantage of the upwind choice of the mobility (23) (we only used the linearity of (ρ, φ) → (ρ σ ) σ∈Σ in the proofs of Lemmas 2.1 and 2.2, which also holds true for a centered choice of the mobilities). The upwinding will be key in the proof of the following theorem, which, roughly speaking, states that there is no need of a Lagrange multiplier for the constraint ρ ≥ 0.
Theorem 2.4. The unique solution (ρ n , φ n ) to system where ρ n σ denotes the upwind value, i.e., is a saddle point of (35).
System (36) is the discrete counterpart of (21), whose derivation relied on the monotonicity of the inverse of the operator φ → φ + τ 2 |∇φ| 2 . Before proving Theorem 2.4, let us show that the space discretization preserves this property at the discrete level. To this end, we introduce the functional Lemma 2.5. Given f ∈ R T , there exists a unique solution to G(φ) = f , and it satisfies Moreover, let φ, φ be the solutions corresponding to f and f respectively, then Proof. Given f ≥ f and φ, φ corresponding solutions, let K * be the cell such that Then, for all the neighboring cells The uniqueness of the solution φ of G(φ) = f follows directly. The maximum principle (37) is also a straightforward consequence of (38) as one can compare φ to (min f )1 and (max f )1 which are fixed points of G. Finally, existence follows from Leray-Schauder fixed-point theorem [39] as the bounds (37) are uniform whatever τ ≥ 0.
With Lemma 2.5 at hand, we can now prove Theorem 2.4.
Proof of Theorem 2.4. Uniqueness of the solution ρ n to (32) was already proved in Theorem 2.3. Owing to (33), Ψ T (ρ n ; ρ n−1 − ρ n ) is finite. So Lemma 2.1 ensures the existence of a discrete Kantorovitch potential φ n satisfying (after a suitable rescaling by τ −1 ) The above condition is the optimality condition w.r.t. φ in (35). The optimality condition w.r.t. ρ writes where the Lagrange multiplier π n = (π n K ) K ≤ 0 for the constraint ρ ≥ 0 satisfies π n , ρ n T = 0. To prove Theorem 2.4, we thus has to prove that one can set π n = 0 and that the solution to system (36) is unique.
Let (ρ n , φ n ) be a solution to (40)-(41) with some possibly non-zero Lagrange multiplier π n ≤ 0. Denote by Z n = {K ∈ T | ρ n K = 0}, Then we deduce from (40) and from the upstream choice of the mobility that Hence the following alternative holds for all the neighbours L ∈ N K of K ∈ Z n : Let φ n be such that φ n ≥ φ n with φ n K = φ n K on P n , then it follows from the upwinding that (40) holds for all K ∈ T , while (41) holds for K ∈ P n .
Reproducing the proof of Lemma 2.5, there exists a unique solution φ n K K∈Z n to the system it follows from (42) that (ρ n , φ n ) fulfills (40). Moreover, it follows from the upwinding in (41) and from (42) that Equation (41) for K ∈ P n does not depend on (φ n K ) K∈Z n , so that (ρ n , φ n ) satisfies also (41), but with π n = 0. Finally, owing to Lemma 2.5, φ n is unique, concluding the proof of Theorem 2.4.

2.4.
Comparison with the classical backward Euler discretization. The scheme (32) is based on a "first discretize then optimize" approach. We have built a discrete counterpart of 1 2 W 2 2 and a discrete energy E T , then the discrete dynamics is chosen in an optimal way by (32). In opposition, the continuous equation (1) can be thought as the Euler-Lagrange optimality condition for the steepest descent of the energy. A classical approach to approximate the optimal dynamics is to discretize directly (1), leading to what we call a "first optimize then discretize" approach. It is classical for the semi-discretization in time of (1) to use a backward Euler scheme. If one combines this technic with upstream weighted Finite Volumes, we obtain the following fully discrete scheme: This scheme has no clear variational structure in the sense that, to our knowledge,ρ n is no longer the solution to an optimization problem. However, it shares some common features with our scheme (32): it is mass and positivity preserving as well as energy diminishing.
Proposition 2.6. Given ρ n−1 ∈ P T , there exists at least one solution (ρ n ,φ n ) ∈ P T × R T to system (43), which satisfies Proof. Summing (43) over K ∈ T provides directly the conservation of mass, i.e., ρ n , 1 T = ρ n−1 , 1 T . Assume for contradiction that K n = {K ∈ T |ρ n K < 0} = ∅, then choose K ∈ K n such thatφ n K ≥φ n K for all K ∈ K n . Then it follows from the upwind choice of the mobility in (43) showing a contradiction. Therefore, K n = ∅ andρ n ≥ 0. These two a priori estimates (mass and positivity preservation) are uniform w.r.t. τ ≥ 0, thus they are sufficient to prove the existence of a solution (ρ n ,φ n ) to (43) thanks to a topological degree argument [39].
The definition ofφ n and the convexity of . Thus to prove (44), it remains to check that In view of (29), τφ n is a discrete Kantorovitch potential sending ρ n−1 onρ n for the mobility corresponding toρ n . Therefore (45) holds as a consequence of (30).
Next proposition provides a finer energy / energy dissipation estimate than (33), which can be thought as discrete counterpart to the energy / energy dissipation inequality (EDI) which is a characterization of generalized gradient flows [2,46]. Proposition 2.7. Given ρ n−1 ∈ P T , let ρ n be the unique solution to (32) and letρ n be a solution to (43), then whereφ n is defined by m Kφ n K = ∂E T ∂ρ K (ρ n ) for all K ∈ T . Proof. Sinceρ n belongs to P T , it is an admissible competitor for (32), thus Combining this with (44) and bearing in mind that 1 τ Ψ T (ρ n ; ρ n−1 − ρ n ) = τ Ψ * T (ρ n ; φ n ) thanks to (30), we obtain the desired inequality (46).

Convergence in the Fokker-Planck case
In this section, we investigate the limit of the scheme when the time step τ and the size of the mesh h T tend to 0 in the specific case of the Fokker-Planck equation (3). The size of the mesh is defined by h T = max K∈T h K with h K = diam(K). To this end, we consider a sequence T m , Σ m , (x K ) K∈Tm m≥1 of admissible discretizations of Ω in the sense of Section 2.1 and a sequence (τ m ) m≥1 of time steps such that lim m→∞ τ m = lim m→∞ h Tm = 0. We also make the further assumptions on the mesh sequence: there exists ζ > 0 such that, for all m ≥ 1, Let T > 0 be an arbitrary finite time horizon, then we assume for the sake of simplicity that τ m = T /N m for some integer N m tending to +∞ with m. For the ease of reading, we remove the subscript m ≥ 1 when it appears to be unnecessary for understanding.
Given V ∈ C 2 (Ω), we define the discrete counterpart of the energy (4) by In view of the above formula, there holds Given an initial condition 0 ∈ P(Ω) with positive mass, i.e. Ω 0 dx > 0, and such that Note that the energy E T is not in C 1 (R T + ) since its gradient blows up on ∂R T + . However, the functional E T is continuous and strictly convex on R T + , hence the scheme (32) still admits a unique solution ρ n for all n ≥ 1 thanks to Theorem 2.3, since its proof does not use the differentiability of the energy. Thanks to the conservativity of the scheme and definition (49) of ρ 0 , one has ρ n , 1 T = ρ 0 , 1 T = Ω 0 dx > 0, ∀n ≥ 1.
Let us show that ρ n > 0 for all n ≥ 1. To this end, we proceed as in [53, Lemma 8.6].
Lemma 3.1. Assume that 0 has positive mass, then the iterated solutions (ρ n ) n≥1 to scheme (32) satisfy ρ n > 0 for all n ≥ 1. Moreover, there exists a unique sequence (φ n ) ≥1 of discrete Kantorovitch potentials such that the following optimality conditions are satisfied for all K ∈ T and all n ≥ 1: Proof. Define ρ = 1 |Ω| Ω 0 dx and ρ = ρ1 ∈ P T , and by ρ n = ρ n K, K∈T = ρ + (1 − )ρ n ∈ P T for some arbitrary ∈ (0, 1). Since ρ n is optimal in (32), there holds The convexity of ρ → Ψ T (ρ, ρ n−1 − ρ) implies that Therefore, the right-hand side in (52) can be overestimated by for some C depending on ρ n , ρ n−1 and V but not on . Setting Z n = {K ∈ T | ρ n K = 0} and and, thanks to the convexity of ρ → ρ log ρ and to the monotonicity of ρ → log ρ, Then dividing by and letting tend to 0, we obtain that which is only possible if Z n = ∅, i.e., ρ n > 0. This implies that E T is differentiable at ρ n , hence the optimality conditions (36) hold, which rewrites as (50)-(51) thanks to (48). By the way, the uniqueness of the discrete Kantorovitch potential φ n for all n ≥ 1 is provided by Theorem 2.4.
Lemma 3.1 allows to define two functions ρ T ,τ and φ T ,τ by setting It follows from the conservativity of the scheme and definition (49) so that ρ T ,τ (·, t) belongs to P(Ω) for all t ∈ (0, T ). The goal of this section is to prove the following theorem.
The proof is based on compactness arguments. At first in Section 3.1, we derive some a priori estimates on the discrete solution. These estimates will be used to obtain some compactness on ρ Tm,τm and φ Tm,τm in Section 3.2. Finally, we identify the limit value as a weak solution in Section 3.3.
3.1. Some a priori estimates. First, let us show that if the continuous initial energy E( 0 ) is bounded, then so does its discrete counterpart E T (ρ 0 ). Lemma 3.3. Given 0 ∈ P(Ω) such that E( 0 ) < +∞, and let ρ 0 be defined by (49), then there exists C 1 depending only on Ω, V and 0 (but not on T ) such that E T (ρ n ) ≤ C 1 for all n ≥ 0.
Proof. It follows from (33) we deduce from the definition (49) of ρ 0 and Jensen's inequality that Similarly, it follows from the mean value theorem that there existsx Combining (54)- (56) in (53) shows that E T (ρ 0 ) ≤ E( 0 ) + C for some C depending only on V , Ω and 0 .
Our next lemma shows that if 0 is bounded away from 0, then so does ρ T ,τ . In particular, if 0 ≥ ρ for some ρ ∈ (0, +∞), then there exists α > 0 depending only on V and ρ (but not on T , τ and n) such that ρ n ≥ α1 for all n ≥ 1.
Proof. It follows directly from (50) that log(ρ n K ) + V K ≥ φ n K for all K ∈ T . Let K ∈ T be such that φ n K ≤ φ n K for all K ∈ T , then the conservation equation (51) ensures that ρ n K ≥ ρ n−1 K . On the other hand, since the discrete HJ equation (50) provides that Assume now that 0 ≥ ρ , then for all K ∈ T and all n ≥ 0, Therefore, we obtain the desired inequality with α = ρ e − V + Our third lemma deals with some estimates on the discrete gradient of the discrete Kantorovitch potentials (φ n ) n . Lemma 3.5. Let (ρ n , φ n ) be the iterated solution to (36), then Moreover, if 0 ≥ ρ ∈ (0, +∞), then there exists C 2 depending on Ω, V and 0 ) such that Proof. Since E T (ρ) ≥ 0 for all ρ ∈ P T , summing (33) over n ∈ {1, . . . , N } yields Thanks to (30), the left-hand side rewrites so that it only remains to use Lemma 3.3 to recover (57). Finally, if 0 is bounded from below by some ρ > 0, then Lemma 3.4 shows that ρ n K ≥ α for some α depending only on ρ and V . Therefore, since ρ n σ is either equal to ρ n K or to ρ n L for σ = K|L ∈ Σ, then (58) holds with C 2 = C1 α .
The discrete solution ρ T ,τ is piecewise constant on the cells. To study the convergence of the scheme, we also need a second reconstruction ρ Σ,τ of the density corresponding to the edge mobilities. It is defined by Lemma 3.6. There exists C 3 depending only on ζ and 0 such that Moreover, there exists C 4 depending only on ζ, V and 0 such that Proof. Since t → ρ Σ,τ (·, t) is piecewise constant, it suffices to check that the above properties at each t n , 1 ≤ n ≤ N . In view of the definition of ρ Σ,τ , one has The first term can easily be overestimated by Ω ρ T ,τ (x, t n )dx = Ω 0 dx. Since ρ n σ ≤ ρ n K + ρ n L , the second term in the above expression can be overestimated by Using the regularity property of the mesh (47c), we obtain that σ∈Σ ρ n σ m ∆σ ≤ ζ Ω 0 dx, so that (60) holds with C 3 = (1 + ζ) Ω 0 dx. Reproducing the above calculations, one gets that Since E T (ρ n ) ≤ E T (ρ 0 ) ≤ C 1 and since V is uniformly bounded, we obtain that (61) holds with The last lemma of this section can be thought as a discrete L ∞ ((0, T ); W 1,∞ (Ω)) estimate on ∂ t ρ T ,τ . This estimate will be used to apply a discrete nonlinear Aubin-Simon lemma [5] in the next section.
Lemma 3.7. Let ϕ ∈ C ∞ c (Q T ), then define ϕ n K = 1 m K K ϕ(x, t n )dx for all K ∈ T . There exists C 5 depending only on ζ, T, 0 , d, such that Proof. Multiplying (51) by ϕ n K and summing over K ∈ T and n ∈ {1, . . . , N } yields Applying Cauchy-Schwarz inequality on the right-hand side then provides The first term in the right-hand side is bounded thanks to Lemma 3.5. On the other hand, the regularity of ϕ ensures that there exists x K ∈ K such that ϕ(x K , t n ) = ϕ n K for all K ∈ T . Thanks to the regularity assumptions (47a)-(47b) on the mesh, there holds Hence, the second term of the right-hand side in (62) can be overestimated by ∞ , the last inequality being a consequence of Lemma 3.6. Combining all this material in (62) shows the desired estimate with

3.2.
Compactness of the approximate solution. The goal of this section is to show enough compactness in order to be able to pass to the limit m → ∞. For the sake of readability, we remove the subscript m unless necessary. Owing to Lemma 3.3, one has E T (ρ n ) ≤ C 1 for all n ∈ {1, . . . , N }. Proceeding as in the proof of Lemma 3.6, this allows to show that for some C 6 depending only on 0 , ζ and V . Combining de La Vallée Poussin's theorem with Dunford-Pettis' one [56, Ch. XI, Theorem 3.6], there exists ∈ L ∞ ((0, T ); L 1 (Ω)) such that, up to a subsequence, (64) ρ Tm,τm tends to weakly in L 1 (Q T ) as m tends to +∞.
for the weak convergence in L 1 (Q T ) (see for instance [11,Corollary 3.9]), so that (63) yields Moreover, since ρ T ,τ ≥ α thanks to Lemma 3.4, then ≥ α too. Our goal is to show that is the unique weak solution to the Fokker-Planck equation (3) corresponding to the initial data 0 . Even though the continuous problem is linear, (64) is not enough to pass to the limit in our nonlinear scheme. Refined compactness have to be derived in this section so that one can identify as the solution to (3) in the next section. To show enhanced compactness (and most of all the consistency of the scheme in the next section), we have to assume that the initial data is bounded away from 0. Proposition 3.8. Assume that 0 ≥ ρ ∈ (0, +∞), then, up to a subsequence, Proof. Our proof of (66)-(67) relies on ideas introduced in [47] that were adapted to the discrete setting in [5]. Define the two convex and increasing conjugated functions defined on R + : Υ : x → e x − x − 1 and Υ * : y → (1 + y) log(1 + y) − y, then the following inequality holds for any measurable functions f, g : Q T → R: Now, notice that since ρ T ,τ is bounded from below thanks to Lemma 3.4 and bounded in L 1 (Q T ), then log ρ T ,τ is bounded in L p (Q T ) for all p ∈ [1, ∞) and Υ(| log(ρ T ,τ )|) is bounded in L 1 (Q T ). As a consequence, there exists ∈ L ∞ ((0, T ); L p (Ω)) such that Since f → Q T Υ(|f |) is convex thus l.s.c. for the weak convergence, we infer that Υ(| |) belongs to L 1 (Q T ). Moreover, in view of (65), Υ * ( ) belongs also to L 1 (Q T ). Therefore, thanks to (69), the function is in L 1 (Q T ). Define the quantities and by r T ,τ ∈ L 1 (Q T ) the function defined Thanks to Lemma 3.5, r T ,τ L 1 (Q T ) ≤ 1 2 C 2 τ . As a consequence, r Tm,τm tends to 0 in L 1 (Q T ) as m tends to +∞.
Let ξ ∈ R d be arbitrary, we denote by Ω ξ = {x ∈ Ω | x + ξ ∈ Ω}. Then using (50) and the triangle inequality, we obtain that for all m ≥ 1, there holds where, denoting by V T (x) = V K if x ∈ K, we have set Since (r Tm,τm ) m≥1 and (V Tm ) m≥1 are compact in L 1 (Q T ) and L 1 (Ω) respectively, it follows from the Riesz-Frechet-Kolmogorov theorem (see for instance [11,Exercise 4.34]) that there exists ω ∈ C(R + ; R + ) with ω(0) = 0 such that On the other hand, the function φ T ,τ belongs to L 1 ((0, T ); BV (Ω)) and the integral in time of its total variation in space can be estimated as follows: with C 7 = d|Ω|T C 2 . This implies in particular that A 2,m (ξ) ≤ C 7 |ξ| for all m ≥ 1. Combining this estimate with (71) in (50) yields The combination of (72) with Lemma 3.7 is exactly what one needs to reproduce the proof of [5,Proposition 3.8], which shows that the product of the weakly convergent sequences (ρ Tm,τm ) m and (log ρ Tm,τm ) m converges towards the product of their weak limits: Let us now identify as log( ) thanks to Minty's trick. Let κ > 0 and ϕ ∈ C ∞ c (Q T ; R + ) be arbitrary, then thanks to (73), As a consequence, ( − κ) ( − log κ) ≥ 0 a.e. in Q T for all κ > 0, which holds if and only if = log . To finalize the proof of (66)-(67), define c m = (ρ Tm,τm − )(log ρ Tm,τm − log ) ∈ L 1 (Q T ; R + ), ∀m ≥ 1.

Then (73) implies that
As a consequence, c m tends to 0 almost everywhere in Q T , which implies the ρ Tm,τm tends almost everywhere towards (up to a subsequence). Then (66)-(67) follow from Vitali's convergence theorem (see for instance [56, Chap. XI, Theorem 3.9]). Finally, one has φ T ,τ = log ρ T ,τ + V T − r T ,τ . In view of the above discussion, the right-hand side converges strongly in L 1 (Q T ) up to a subsequence towards log + V , then so does the left-hand side. This provides (68) and concludes the proof of Proposition 3.8.
Next lemma shows that ρ Σ,τ shares the same limit as ρ T ,τ . Lemma 3.9. Assume that 0 ≥ ρ ∈ (0, +∞), then Proof. Thanks to Lemma 3.6, it follows from the de La Vallée-Poussin and Dunford Pettis theorems that (ρ Σm,τm ) m≥1 is relatively compact for the weak topology of L 1 (Q T ). Combining this with (64), we infer that, up to a subsequence, (ρ Σm,τm − ρ Tm,τm ) m≥1 converges towards some w weakly in L 1 (Q T ). Thanks to Vitali's convergence theorem, it suffices to show that from any subsequence of (ρ Σm,τm − ρ Tm,τm ) m≥1 , one can extract a subsequence that tends to 0 a.e. in Q T (so that the whole sequence converges towards w = 0), or equivalently since both (ρ Σm,τm ) m≥1 and (ρ Tm,τm ) m≥1 are bounded away from 0 thanks to Lemma 3.4. Bearing in mind the definition (59) of ρ Σm,τm , and one has Using (50) and the triangle inequality, one gets that Using again that dm ∆σ = d σ m σ ≤ ζh T m σ thanks to (47a), one has Since |r n K − r n L | ≤ r n K + r n L , the regularity assumption (47c) on the mesh implies that so that (74) holds, concluding the proof of Lemma 3.9.
In order to conclude the proof of Theorem 3.2, it remains to check that any limit value of the scheme is a solution to the Fokker-Planck equation (3) in the distributional sense.

Let us define
Then it follows from Lemma 3.10 that To conclude the proof of Proposition 3.11, it only remains to check that Since ϕ is smooth and since d σ n KL = x K − x L thanks to the orthogonality condition satisfied by the mesh, for some C ϕ depending only on ϕ. Therefore, Applying Cauchy-Schwarz inequality, one gets that thanks to Lemma 3.6.

Numerical results
To check the correctness and reliability of our formulation we performed some numerical tests. Before that, we are going to present some details on the solution of the nonlinear system involved in the scheme. 4.1. Newton method. Due to the explicit formulation of the optimality condition of the saddle point problem (35), it appears extremely convient to use a Newton method for their solution. Given u n−1 = (φ n−1 , ρ n−1 ) ∈ R 2T solution of the scheme at the time step n − 1, the Newton method aims at constructing a sequence of approximations of u n as u n,k+1 = u n,k + d k , d k = (d k φ , d k ρ ) being the Newton direction, solution to the block-structured system of equations In the above linear system, f k φ and f k ρ are the discrete HJ and continuity equations evaluated in u n,k , and J k φ,φ , J k φ,ρ , J k ρ,φ and J k ρ,ρ are the four blocks of the Hessian matrix J k of the discrete functional in (35) evaluated in u n,k . The sequence converges to the unique solution u n as soon as the initial guess is sufficiently close to it, which is ensured for a sufficiently small time step by taking u n 0 = u n−1 . The algorithm stops when the ∞ norm of the discrete equations is smaller than a prescribed tolerance or if the maximum number of iterations is reached. It is possible to implement an adaptative time stepping: if the Newton method converges in few iterations the time step τ increases; if it reaches the maximum number of iterations the time step is decreased and the method restarted. Issues could arise if the iterate u n,k reaches negative values, especially if the energy is not defined for negative densities. To avoid this problem two possible strategies may be implemented: the iterate may be projected on the set of positive measure by taking u n,k = (u n,k ) + ; the method may be restarted with a smaller time step.
In case of a local energy functional, as it is the case for the Fokker-Planck and many more examples, the block J k ρ,ρ is diagonal and therefore straightforward to invert. System (76) can be rewritten in term of the Schur complement and solved for d k φ as (77) Proposition 4.1. The Schur complement S k = J k φ,φ − J k φ,ρ (J k ρ,ρ ) −1 J k ρ,φ is symmetric and negative definite.
Proof. S k is symmetric since J k φ,φ and J k ρ,ρ are, while J k φ,ρ = (J k ρ,φ ) T . The matrix J k ρ,ρ is positive definite since the problem is strictly convex, whereas J k φ,φ is negative definite if ρ n,k K > 0, ∀K ∈ T , since the problem is strictly concave, but it is semi-negative definite if the density vanishes somewhere. Therefore, it is sufficient to show that the matrix J k φ,ρ = (J k ρ,φ ) T = M + A k is invertible. M is a diagonal matrix such that (M ) K,K = m K , whereas and, for L = K, Therefore the columns of A k sum up to 0, so that (J k φ,ρ ) is a column M-matrix [28] and thus invertible.
In case the matrix J k ρ,ρ is simple to invert it is then possible to decrease the computational complexity of the solution of system (76). Moreover, it is possible to exploit for the solution of system (77) symmetric solvers, which are computationally more efficient than non-symmetric ones. ρ(x, y, t) = exp(−αt + g 2 x)(π cos(πx) + g 2 sin(πx)) + π exp(g(x − 1 2 )), where α = π 2 + g 2 4 . On the domain Ω = [0, 1] 2 , the function ρ(x, y, t) is positive and satisfies the mixed boundary conditions (∇ρ + ρ∇V ) · n| ∂Ω = 0. We want to exploit the knowledge of this exact solution to compute the error we commit in the spatial and time integration. Consider a sequence of meshes T m , Σ m , (x K ) K∈Tm with decreasing mesh size h Tm and a sequence of decreasing time steps τ m such that τm . In particular, we used a sequence of Delaunay triangular meshes such that the mesh size halves at each step, obtained subdividing at each step each triangle into four using the edges midpoints. Three subsequent partitioning of the domain are shown in figure 1. Let us introduce the following mesh-dependent errors: where ρ(x K , nτ m ) is the value in the cell center of the triangle K of the analytical solution at time nτ m , n running from 0 to the total number of time steps N m . The upstream Finite Volume scheme with implicit Euler discretization of the temporal derivative is known to exhibit order one of convergence applied to this problem, both in time and space. This means that the L ∞ ((0, T ); L 1 (Ω)) and L 1 ((0, T ); L 1 (Ω)) errors halve whenever h T and τ halve. We want to inspect whether scheme (36) recovers the same behavior. For the sequence of meshes and time steps, for m going from one to the total number of meshes, we computed the solution to the linear Fokker-Planck equations and the errors, using both the Finite Volume scheme and scheme (36). The results are shown in Table 1. For each mesh size and time step m, it is represented the error together with the rate with respect to the previous one.   Table 2. Time-space convergence for scheme (36). Integration on the time step Scheme (36) exhibits the same order of convergence of the FV scheme. It is noticeable that the rate of convergence of scheme (36) senses a big drop and then recovers order one, especially in the L ∞ ((0, T ); L 1 (Ω)) error. This is due to the fact that the initial condition ρ(x K , 0) is too close to zero, and in particular equal to zero on the set 1 × [0, 1], and scheme (36) tends to be repulsed away from zero due to the singularity of the gradient of the first variation of the energy. In Table 2 we repeated the convergence test for the time interval [0.05, 0.25]: the convergence profile sensibly improves.
To further investigate and compare the behavior of scheme (36) with the FV, we computed also the energy decay along the trajectory. We call dissipation the difference E(ρ) − E(ρ ∞ ), where ρ ∞ is the final equilibrium condition, the long time behavior. Since we are discretizing a gradient flow, its dissipation is a useful criteria to assess the goodness of the scheme. The long time value of the energy is equal to: It is possible to define the equilibrium solution also on the discrete dynamics on the grid. Namely, the equilibrium solution for the dynamic defined on the grid is as it can be easily checked to be the unique minimizer of the discrete energy E h = K∈T E(ρ K )m K subject to the constraint of the conservation of the mass, with λ lagrange multiplier associated with the constraint. M is the constant that makes (ρ ∞ K ) K∈T have the same total mass: It is immediate to observe that this is indeed the equilibrium solution in the FV scheme, since with such density the potential in (43) is constant: For the scheme (36) instead, as it appears clear from Lemma 2.1, whenever ρ n K = ρ n−1 K , ∀K ∈ T , as it is the case for an equilibrium solution, the potential is constant. From the potential equation one gets again Figure 2 it is represented the semilog plot of the dissipation of the system, computed for the scheme (36) and the FV one, E h (ρ K ) − E h (ρ ∞ K ), and the real solution, E(ρ) − E(ρ ∞ ). In Figure 2a it is noticeable that scheme (36) scheme dissipates the energy faster than the FV one, being indeed a bit more diffusive. This is an expected behavior since the scheme is built to maximize the decrease of the energy and this is actually one of the main strength of the approach. In Figure 2b, one can see that the two dissipations tends to the real one when finer mesh and smaller time step are used, for both schemes, despite the fact that (36) still dissipates faster. In the end, in Figure 2c it is remarkable that for a very small time step the dissipation of the two schemes tends to coincide, as it is expected. For the time parameter going to zero the two schemes coincide. has been proven in [51] to be a gradient flow in Wasserstein space with respect to the energy for a given m strictly greater than one. Our aim is to show that scheme (36) works regardless of the positivity assumption on the initial measure ρ 0 . For this reason, we use a confining potential V (x) = 1 2 ||x − 0.5|| 2 2 . The equilibrium solution of the gradient flow should then be the Barenblatt profile ρ ∞ (x) = m−1 2m max(1 − ||x|| 2 ) 1 m−1 . In Figure 3 the evolution of an initial density with compact support is shown for the case m = 4. As expected, the solution converges towards the Barenblatt profile.       and initial conditions f (t = 0) = f 0 , g(t = 0) = g 0 , with f 0 , g 0 ∈ L ∞ (Ω), f 0 , g 0 ≥ 0. The quantities f , g, and b represent respectively the thickness of the fresh layer of water, the thickness of the salty water layer and the height of the bedrock. Therefore the quantity b + g represents the height of the sharp interface separating the two fluids. The parameter ν = ρ f ρs is the ratio between the constant mass density of the fresh and salt water. Equation (78) has been proven in [37] to be a Wasserstein gradient flow with respect to the energy Figure 4 represents the bedrock b and the evolution of the surfaces of salt water, b + g, and of fresh water, b + g + f (see [1] for a full description of the test case). Also this case is not covered from the theoretical analysis we performed on the convergence of the scheme but still scheme (36) works. As already said, from numerical evidences the scheme works under much more general and mild hypotheses.