F Mazon

G Santambrogio

J D Carlier

Benamou

Tout d'abord, je souhaiterais exprimer ma profonde gratitude à mon directeur de thèse, le Professeur Noureddine IGBIDA, pour son encadrement durant ces trois ans de thèse et un stage de Master, pour sa patience et sa disponibilité. J'ai beaucoup apprécié son soutien enthousiaste et ses conseils qui m'ont été et me resteront très utiles, non seulement pour le travail scientifique mais aussi pour la vie quotidienne. Le Professeur Igbida m'a donné de nombreuses occasions de rencontrer, de travailler et de discuter avec des chercheurs qui s'investissent notamment sur la théorie du transport optimal, les équations aux dérivées partielles, l'optimisation et l'analyse numérique. Encore merci pour tout ce que vous m'avez apporté.

General Introduction

This thesis is devoted to the mathematical and numerical analysis of the optimal partial transport and optimal constrained matching problems, which are variants of the optimal transport. The common point of the two mentioned problems is the presence of unknown active submeasures. For each problem, we are interested in the characterizations, uniqueness of solution, equivalent formulations and numerical approximations. The main tools which we have used are some combinations of PDE techniques, optimal transport theory, Fenchel-Rockafellar dual theory and augmented Lagrangian methods (first-order splitting methods).

The optimal transport problem (Fig. 1) was first proposed by French geometer G. Monge in 1781 [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] which consists in transporting piles of sand into holes with the least amount of work. In modern mathematics language, let µ and ν be two It is well-known that Monge's problem is quite difficult even for the usual question about the existence of optimal map. The main difficulty comes from the fact that the constraint T #µ = ν is so highly nonlinear that the admissible set T (µ, ν) is not closed, in general, under usual topologies. Since the 1980s, many authors have carried out deep analyses for the existence of optimal map. On this direction, we refer to the non-exhaustive list [START_REF] Ambrosio | Existence and stability results in the L 1 theory of optimal transportation[END_REF][START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF][START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF][START_REF] Th | The Monge problem in R d[END_REF][START_REF] Gangbo | The geometry of optimal transportation[END_REF][START_REF] Sudakov | Geometric problems in the theory of infinite-dimensional probability distributions[END_REF][START_REF] Trudinger | On the Monge mass transfer problem[END_REF] and the references therein.

In 1942, by applications in economics, L. Kantorovich [START_REF] Kantorovich | On the translocation of masses[END_REF] introduced an optimal problem that is now seen as a relaxation of Monge's optimal transport problem. Kantorovich searched a measure on the product space X × Y instead of a measure-preserving map as in Monge's problem. The trick is first to introduce the admissible set π(µ, ν)

:= {γ ∈ M + b (X×Y ) : γ(A×Y ) = µ(A), γ(X×B) = ν(B) ∀A ⊂ X, B ⊂ Y },
where A and B are Borel sets of X and Y , respectively. We can imagine as follows: the quantity γ(A × B) is seen as the amount of mass moving from A to B. So all the mass moved to B is γ(X × B) while the demand mass at B is ν(B). To fulfill the requirement, one should impose γ(X × B) = ν(B). Analogously, one requires γ(A × Y ) = µ(A). In other words,

π(µ, ν) = γ ∈ M + b (X × Y ) : π x #γ = µ, π y #γ = ν ,
where π x and π y stand for the two canonical projections from X × Y onto X and onto Y , respectively. Kantorovich's problem reads as min γ∈π(µ,ν) X×Y c(x, y) dγ, (MK) which is a linear programming in the (possibly infinite-dimensional) space M b (X × Y ) of finite Radon measures. The difference between the two problems is that the Kantorovich problem allows to split mass, i.e. mass from x can be sent to several destinations y. Moreover, for any transport map T ∈ T (µ, ν), one has γ := (id, T )#µ ∈ π(µ, ν). Unlike Monge's problem, under very general conditions General Introduction on c, the Kantorovich problem admits optimal solutions, called optimal plans, by using the standard direct method (see e.g. [START_REF] Villani | Optimal Transport, Old and New[END_REF]). On the other hand, Kantorovich also introduced a dual maximization problem which turns out to be very important to the proofs of existence of optimal map for Monge's problem (see e.g. [START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF][START_REF] Gangbo | The geometry of optimal transportation[END_REF]). Nowadays, Kantorovich's problem (MK) is called Monge-Kantorovich problem and it appears quite naturally in applications.

Besides the applications in industry and in economics as motivated by Monge and Kantorovich, this subject has got a lot of attention and has been investigated under various points of view since the end of the eighties with many surprising applications in partial differential equations (PDEs), differential geometry, probability theory, geometric inequalities, image processing and other areas. For more details on the optimal mass transport problem, we refer the reader to the pedagogical books [3,[START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF][START_REF] Villani | Topics in Optimal Transportation[END_REF][START_REF] Villani | Optimal Transport, Old and New[END_REF]. Like many other mathematical topics, the optimal transport problem has been generalized in different trends. Among generalizations of the optimal transport, we are interested in two problems, called optimal partial transport and optimal constrained matching problems, which are closely connected to obstacle type PDEs.

Optimal partial transport aims to study the case where only a part of the commodity (respectively, consumer demand) of total mass m needs to be transported (respectively, fulfilled). More precisely, let µ, ν ∈ M + b (R N ) be finite Radon measures and c : R N × R N -→ [0, +∞) be a measurable cost function. Given a prescribed total mass m ∈ [0, m max ] with m max = min µ(R N ), ν(R N ) , the optimal partial transport problem (or partial Monge-Kantorovich problem, PMK for short) reads as follows min

   K(γ) := R N ×R N c(x, y)dγ : γ ∈ π m (µ, ν)    , (PMK)
where

π m (µ, ν) := γ ∈ M + b (R N × R N ) : π x #γ ≤ µ, π y #γ ≤ ν, γ(R N × R N ) = m .
Here, π x #γ and π y #γ are marginals of γ. This generalized problem brings out new unknown quantities ρ 0 := π x #γ and ρ 1 := π y #γ where the commodity is taken and the consumer demand is fulfilled, respectively. The problem (PMK) was first studied theoretically in Caffarelli & McCann [27, Ann. of Math., 2010] and Figalli [48, Arch. Ration. Mech. Anal., 2010] with a particular attention to the quadratic cost, c(x, y) = |x -y| 2 , with results on the existence, uniqueness and regularity of active submeasures 1 . The regularities are also discussed in Indrei [61, J. Funct. Anal., 2013] and Davila & Kim [36, Calc. Var., 2016] for c(x, y) = |x -y| 2 ; and in Chen & Indrei [33, J. Differential Equations, 2015] for general costs under assumptions on "smoothness" of c and regularity of µ, ν.

The main part of this thesis is devoted to the problem (PMK) with general Finsler distance costs d F and Lagrangian costs c L which cover the Euclidean cost c(x, y) = |x -y| and the quadratic cost c(x, y) = |x -y| 2 as particular cases, respectively. We will focus on the uniqueness and characterizations of solution as well as variational aspects and numerical approximations. These will be the subjects of Chapters 2, 3 and 4. Discussions on the existing techniques and results will be considered in concrete contexts.

Chapter 2 concerns a rigorous theoretical study of (PMK) with Finsler distance costs c := d F (including the case of Euclidean distance cost), where

d F (x, y) := inf ξ∈Lip([0,1];R N )    1 0 F (ξ(t), ξ(t))dt : ξ(0) = x, ξ(1) = y   
with F (x, .) having a linear growth and satisfying some conditions that will be clarified later. This chapter provides equivalent formulations, the characterizations and uniqueness of active submeasures for these costs. In this setting, we first introduce the Kantorovich-Rubinstein type duality for (PMK) with Finsler distance costs. Recall that in the case c(x, y) = |x -y| 2 , the obstacle Monge-Ampère equation (cf. Caffarelli & McCann [27] and Figalli [START_REF] Figalli | The optimal partial transport problem[END_REF]) plays an important role to gather many informations on (PMK). In our case, we introduce the obstacle Monge-Kantorovich (OMK) equation and show how it is information-rich PDE for (PMK). Among the main issues of our approach, the uniqueness of the active submeasures as well as their monotonicity hold true in the case where µ and ν are absolutely continuous without disjointness condition of the supports. Note that the methods used in [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF][START_REF] Figalli | The optimal partial transport problem[END_REF] do not work for the uniqueness of active submeasures of (PMK) with Finsler distance costs by the fact that the authors there need the strict convexity of c as well as the existence and uniqueness of optimal map. Our point of view is to obtain the uniqueness via the study of the OMK equation by using PDE techniques. On the other hand, our equivalent formulations will be exploited in Chapter 3 to give interesting numerical simulations.

General Introduction

Our main result starts with the Kantorovich-Rubinstein type duality. where

L λ d F := u ∈ L 1 µ ∩ L 1 ν : u(y) -u(x) ≤ d F (x, y), 0 ≤ u(x) ≤ λ for all x, y ∈ R N .
In addition, σ ∈ π m (µ, ν) and (λ, u) ∈ R + ×L λ d F are solutions of the PMK problem and of the dual partial Monge-Kantorovich (DPMK) problem (0.1) if and only if u(x) = 0 for (µπ x #σ)-a.e. x ∈ R N , u(x) = λ for (νπ y #σ)-a.e. x ∈ R N and u(y)u(x) = d F (x, y) for σ-a.e. (x, y) ∈ R N × R N .

Next, to introduce the OMK equation, we see that the dual maximization formulation (0.1) may be written as is given by the following PDE: Find (θ, Φ, u)

∈ M b (R N ) × M b (R N ) N × L λ d F such that          θ -∇ • Φ = ν -µ in D ′ (R N ) Φ |Φ| (x) • ∇ |Φ| u(x) = F x, Φ |Φ| (x)
|Φ|-a.e. x ∈ R N u = 0 θ --a.e. in R N and u = λ θ + -a.e. in R N ,

(P λ )
where θ + and θ -are the positive and negative parts of the measure θ given by the Hahn-Jordan decomposition. This is a double obstacle problem associated with (PMK) for c = d F , called obstacle Monge-Kantorovich (OMK) equation. To fix the idea, it is expected that νθ + and µθ -are active submeasures. This

Optimal Partial Transport and Constrained Matching Problems primarily requires that θ + ≤ ν and θ -≤ µ, (0.2) which are not explicitly stated in (P λ ). In other words, the estimates (0.2) are important for (PMK) but the advantage of ignoring the constraints (0.2) in the definition of (P λ ) lies in the use of augmented Lagrangian methods, which only give dual solutions in the sense of the Fenchel-Rockafellar duality. This leads to the question whether the estimates (0.2) are automatically satisfied for any solution (θ, Φ, u) of (P λ ).

The central issues of Chapter 2 are the existence, estimates (0.2) and uniqueness of solution for (P λ ) as well as its connection to (PMK). The existence of solution for (P λ ) will be shown by duality arguments. On the other hand, although the OMK equation is so degenerate that its flux Φ does not explicitly depend on the gradient ∇u, it still admits somehow monotonicity because of the second equation in (P λ ). This helps us to show that θ -≤ µµ ∧ ν ≤ µ and θ + ≤ νµ ∧ ν ≤ ν for any solutions (θ, Φ, u).

This fulfils the requirement (0.2) (see Theorem 2.3). Concerning the uniqueness of solution, we have the following result. Theorem 0.2 (Uniqueness of θ). Assume that µ, ν ∈ L 1 (R N ) + . Let θ 1 and θ 2 be two solutions to the same OMK equation (P λ ). Then θ 1 , θ 2 ∈ L 1 (R N ) and θ 1 = θ 2 .

Our proof will be based on doubling variables which was used for the first time by Kruzkov [66] for first order quasilinear equations. In general, one cannot expect the uniqueness of Φ and u because of the degeneracy of (P λ ). Now, we come back on the connection between the OMK equation and (PMK).

Theorem 0.3 (Active submeasures and OMK equation). Let µ, ν ∈ M + b (R N ) be compactly supported. (i) For any λ ≥ 0 and θ λ a solution of the OMK equation (P λ ), the couple

(ρ 0 , ρ 1 ) := (µ -θ - λ , ν -θ + λ )
is a couple of active submeasures corresponding to m λ = (µθ - λ )(R N ). (ii) Conversely, if (ρ 0 , ρ 1 ) ∈ Sub m (µ, ν) is a given couple of active submeasures and m ∈ [(µ ∧ ν)(R N ), m max ], then for any λ m ≥ 0 such that λ m ∈ argmax Following Theorems 0.3 and 0.2, we deduce the uniqueness result for (PMK).

Corollary 0.4 (Uniqueness of active submeasures). Let µ, ν ∈ L 1 (R N ) + be compactly supported and m ∈ [ µ ∧ ν L 1 , m max ]. There exists a unique couple of active submeasures.

For general Finsler metric F , this uniqueness result is derived by using the doubling variables technique to the OMK equation. In Chapter 2, we also provide an alternative proof for C 2 Finsler metric F basing on the Lebesgue negligibility of the set of endpoints of maximal transport rays.

The purpose of Chapter 3 is to complete Chapter 2 with the numerical analysis of (PMK) for Finsler distance costs c = d F . For numerical approximations, Barrett & Prigozhin [9, Interfaces Free Bound., 2009] studied numerically the case c(x, y) = |x -y| using approximated nonlinear PDEs and Raviart-Thomas finite elements.

More recently, Benamou et al. [14, SIAM J. Sci. Comput., 2015] introduced a general numerical framework to approximate solutions of linear programs related to optimal transport such as barycenters in Wasserstein space, multi-marginal optimal transport, optimal partial transport and optimal transport with capacity constraints. Their idea is based on an entropic regularization of the initial linear programs and Bregman-Dykstra iterations. In this trend, we also refer to the very recent paper of Chizat et al. [START_REF] Chizat | Scaling algorithms for unbalanced transport problems[END_REF]. These approaches need to use (approximated) values of d F .

In Chapter 3, we propose a different strategy basing on the theoretical results from Chapter 2 and on augmented Lagrangian methods. We first show how one can directly reformulate the unknown quantities (active submeasures) of the optimal partial transport into an infinite-dimensional minimization problem of the form:

min φ∈V F(φ) + G(Λφ), (0.3)
where F, G are l.s.c., convex functionals and Λ ∈ L(V, Z) is a continuous linear operator between two Banach spaces. More precisely, the DPMK formulation (0.1) will be rewritten in the form of (0.3). To do this, we show that the constraint u(y)u(x) ≤ d F (x, y) for all x, y is equivalent to F * (x, ∇u(x)) ≤ 1 a.e. x, where F * is the polar function of F , by definition, F * (x, p) := sup v∈R N { p, v : F (x, v) ≤ 1}. Then, the problem (0.3) is approximated by finite-dimensional problems of the form min

φ h ∈V h F h (φ h ) + G h (Λ h φ h ). (0.4)
We prove the convergence of discretization, i.e. primal-dual solutions of (0.4) converge to the ones of the original problem. At last, thanks to peculiar properties of F and G in our situation, an augmented Lagrangian method is effectively applied in the same spirit as Benamou & Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] (see also [START_REF] Benamou | Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations[END_REF][START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF]). For computation, we just need to solve linear equations (with a symmetric positive definite coefficient matrix) or to update explicit formulations. It is worth noting that this method uses only elementary operations without evaluating d F . This is an advantage when the evaluation of d F (x, y), for each pair (x, y), is difficult.

In where L(x, .) is convex and has superlinear growth (for example, L(x, v) = |v| q q with q > 1). Our main aims are to study equivalent dynamical formulations and to provide a numerical approximation for the PMK problem with these Lagrangian costs c L . By using the convex conjugate function H(x, p) := sup

v∈R N p, v -L(x, v),
we introduce the dual maximization formulation in the form

max (λ,u)    R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : λ ∈ R + , u ∈ K λ c    , (0.5)
where

K λ c := u ∈ Lip([0, 1] × R N ) : ∂ t u(t, x) + H(x, ∇ x u(t, x)) ≤ 0 a.e. (t, x) ∈ [0, 1] × R N , -λ ≤ u(0, x), u(1, x) ≤ 0 ∀x ∈ R N .
The Fenchel-Rockafellar dual problem of (0.5) gives exactly the Benamou-Brenier type formulation for the PMK problem. For rigorous proofs, the main difficulty General Introduction in the study of general Lagrangian L remains in smooth approximation of the elements in K λ c . This issue will be discussed in Chapter 4. As we will see, the maximization problem (0.5) contains all informations on the transportation and it falls into the scope of (0.3) which allows us to use augmented Lagrangian methods for numerical computation. Again, note that we need to use only the function L via elementary operations instead of the evaluation c L (x, y). This approach provides at the same time active submeasures and their movement. Thus the method should be a choice when one cares not only active submeasures but also the optimal transportation. The last chapter of the thesis deals with an optimal constrained matching problem, which is a variant from Ekeland's optimal matching problem (see Ekeland [41, ESAIM Control Optim. Calc. Var., 2005]), consists in transporting two kinds of goods and matching them into a target set with constraints on mass at the target. For example, the target represents the capacities of some companies, the amount of goods matching at each company should have a predetermined bound from above. In mathematical language, the optimal matching problem with constraints for the Euclidean costs can be modeled as follows: Let Ω ⊂ R N be a nonempty convex set and

f 1 , f 2 ∈ M + b (Ω) represent source measures of the same mass, i.e., f 1 (Ω) = f 2 (Ω). The constraint on the target set is represented by a measure Θ ∈ M + b (Ω) satisfying f 1 (Ω) = f 2 (Ω) < Θ(Ω).
The optimal constrained matching problem reads as follows

W (f 1 , f 2 ; Θ) := inf (γ 1 ,γ 2 )∈π(f 1 ,f 2 ;Θ)   Ω×Ω |x -y|dγ 1 + Ω×Ω |x -y|dγ 2   , (0.6)
where

π(f 1 , f 2 ; Θ) := (γ 1 , γ 2 ) ∈ M + b (Ω×Ω) 2 : π y #γ 1 = π y #γ 2 ≤ Θ, π x #γ i = f i , i = 1, 2 .
This problem can be written as

inf ρ∈M + b (Ω) W 1 (f 1 , ρ) + W 1 (f 2 , ρ) : ρ ≤ Θ, ρ(Ω) = f 1 (Ω) ,
where W 1 (., .) is the 1-Wasserstein distance (see Chapter 1). An optimal solution ρ is called optimal matching measure.

The optimal constrained matching problem (0.6) is recently studied

Optimal Partial Transport and Constrained Matching Problems

theoretically by Mazon et al. [START_REF] Mazón | An optimal matching problem with constraints[END_REF] in connection with p-Laplacian type systems by using PDE techniques. In [START_REF] Barrett | Partial L 1 Monge-Kantorovich problem: Variational formulation and numerical approximation[END_REF], Barrett & Prigozhin also give a numerical approximation to the problem (0.6) in the case where Θ = CL N D, i.e. Θ is a constant C on the destination set D.

Chapter 5 is left to the uniqueness and numerical approximation of the optimal matching measure. We note that the uniqueness of optimal matching measure does not hold even with regular f 1 , f 2 , Θ (see Section 5.2). This interesting behaviour is different from the PMK problem (see Chapter 2). An additional geometric condition, as well as the absolute continuity of the measure Θ, is needed for the uniqueness.

Theorem 0.5. Assume that Θ ∈ L 1 and that S(

f 1 , f 2 ) ∩ supp(Θ) = ∅ with S(f 1 , f 2 ) := z = (1 -t)x + ty : x ∈ supp(f 1 ), y ∈ supp(f 2 ) and t ∈ [0, 1] .
There exists a unique optimal matching measure ρ.

For the proof, we will make use of the special property of Kantorovich potentials about the Lebesgue negligibility of endpoints of maximal transport rays. We also give counterexamples to show that the above conditions are non-negligible.

Concerning numerical computation, we develop the variational study of the problem. We introduce the following dual maximization formulation

max (u 1 + u 2 )dΘ -u 1 df 1 -u 2 df 2 : (u 1 , u 2 ) ∈ K , (0.7)
where

K := {(u 1 , u 2 ) ∈ Lip 1 (Ω) × Lip 1 (Ω) : u 1 + u 2 ≤ 0} .
Using the Fenchel-Rockafellar dual theory to the maximization problem (0.7), we also introduce the minimal matching flow problem:

min |Φ 1 |(Ω) + |Φ 2 |(Ω) : (Φ 1 , Φ 2 , ν) ∈ Ψ(f 1 , f 2 ; Θ) , (MMF)
where

Ψ(f 1 , f 2 ; Θ) := (Φ 1 , Φ 2 , ν) ∈ M b (Ω) N ×M b (Ω) N ×M + b (Ω) : -∇•Φ i = Θ-ν-f i in D ′ (R N ) .
The interesting point to note here is, in contrast to the PMK problem, the optimal solutions of Fenchel-Rockafellar dual formulation do not really give optimal matching measure. In fact, it may in general happen ν Θ for optimal solution (Φ 1 , Φ 2 , ν). This is again different from the PMK problem. The following theorem General Introduction provides a criterion for the reconstruction of optimal matching measure from solutions of (MMF).

Theorem 0.6. Let f 1 , f 2 , Θ ∈ M + b (Ω) be Radon measures. Assume that S(f 1 , f 2 )∩ supp(Θ) = ∅ holds. Let (Φ 1 , Φ 2 , ν) ∈ Ψ(f 1 ,
f 2 ; Θ) be an optimal solution for the problem (MMF) and set ρ := Θν. Then ρ ≥ 0 and it is an optimal matching measure.

Based on these equivalent formulations, we also provide numerical approximations for which the convergence of discretization and numerical simulations are given.

At last, let us give the structure of this thesis. Chapter 1 provides some preliminaries needed in the thesis. In Chapter 2, we study theoretically the optimal partial transport with Finsler distance costs d F . We introduce equivalent formulations for the optimal partial transport with a particular attention to the so-called obstacle Monge-Kantorovich (OMK) equation. More precisely, active submeasures are characterized as solutions of the OMK equation. And then, we study some properties of this OMK equation which allow us to show the uniqueness and monotonicity results for the active submeasures. To do this, we will make use of tools from optimal transport theory, variational analysis and PDE techniques. Chapter 3 concerns numerical approximations for the optimal partial transport via augmented Lagrangian methods. The convergence of our discretization is also shown in detail. We base on the so-called ALG2 algorithm to give numerical simulations. Chapter 4 provides a detailed exposition of theoretical and numerical results for the PMK problem with Lagrangian costs. In this case, we derive equivalent formulations basing the form of Hamilton-Jacobi equations with constraints. In Chapter 5, we will be concerned with the optimal constrained matching problem subject to constraints on capacity of the target. For such a problem, we show the existence and uniqueness of solution under some additional geometric conditions. Besides these issues, we also provide numerical approximations, the convergence of discretization and numerical examples. The contents of Chapters 2, 3, 4 and 5 are mainly taken from four papers [START_REF] Igbida | Optimal partial mass transportation and obstacle Monge-Kantorovich equation[END_REF][START_REF] Igbida | Optimal partial transport with Lagrangian costs[END_REF][START_REF] Igbida | Augmented Lagrangian method for optimal partial transportation[END_REF][START_REF] Igbida | On the uniqueness and numerical approximations for a matching problem[END_REF], among which [START_REF] Igbida | Augmented Lagrangian method for optimal partial transportation[END_REF] is published in IMA Journal of Numerical Analysis, [START_REF] Igbida | On the uniqueness and numerical approximations for a matching problem[END_REF] is accepted for publication in SIAM Journal on Optimization and [START_REF] Igbida | Optimal partial mass transportation and obstacle Monge-Kantorovich equation[END_REF] is under revision for publication in Journal of Differential Equations.

Chapter 1 Preliminaries

The purpose of this chapter is to provide notations and some preliminaries in optimal transport theory, the notion of tangential gradient to a measure and Fenchel-Rockafellar dual theory as well as augmented Lagrangian methods.

Notations

Let us set up the basic notions which are used in the text. Ω ⊂ R N stands for a non-empty domain (sometimes convex or bounded, which will be specified in the context) with a Lipschitz boundary. We denote by |.| the usual Euclidean norm on R N (or even Hilbertian norm) and when it is not ambiguous, we also use |µ| for the total variation norm of the measure µ.

We denote by C b (Ω) (respectively, C(Ω)) the spaces of bounded continuous functions on Ω (respectively, continuous functions on Ω). We set M b (Ω) (respectively, M + b (Ω)) for the space of signed (respectively, non-negative) finite Radon measures defined on Ω. Given the Hahn-Jordan decomposition

µ = µ + -µ - with µ + , µ -∈ M + b (Ω), we set |µ|(Ω) := µ + (Ω) + µ -(Ω)
for the total variation of µ on Ω which turns out to be a norm on M b (Ω). Moreover, this normed space is the topological dual space of (C b (Ω), . ∞ ). For two measures

µ 1 , µ 2 ∈ M b (Ω), we write µ 1 ≤ µ 2 if µ 1 (B) ≤ µ 2 (B) for any Borel set B ⊂ Ω, or equivalently Ω φ dµ 1 ≤ Ω φ dµ 2 for any φ ∈ C b (Ω), φ ≥ 0.
The notation µ ∧ ν stands for the measure of common mass of µ and ν, i.e.

µ ∧ ν(A) = inf{µ(A 1 ) + ν(A 2 ) : disjoint Borel sets A 1 , A 2 , such that A 1 ∪ A 2 = A}. 1. Preliminaries If µ, ν ∈ L 1 (R N ) then µ ∧ ν ∈ L 1 (R N ) and (µ ∧ ν)(x) = min{µ(x), ν(x)} for a.e. x ∈ R N .
We also denote by M b (Ω) N the space of R N -valued finite Radon measures, i.e., Φ ∈ M b (Ω) N if and only if Φ = (Φ 1 , ..., Φ N ) with Φ i ∈ M b (Ω). We recall that the total variation associated with Φ ∈ M b (Ω), denoted by |Φ|(Ω) (or simply |Φ|), is defined by

|Φ|(B) := sup ∞ i=1 |Φ(B i )|: B = ∞ i=1 B i with pairwise disjoint Borel sets B i ⊂ Ω ,
which coincides with the definition via the Hahn-Jordan decomposition whenever N = 1. It is known that the space M b (Ω) N equipped with the total variation norm is isometric to the topological dual of C b (Ω) N with the duality bracket

Φ, ξ := N i=1 Ω ξ i dΦ i for any Φ = (Φ 1 , ..., Φ N ) ∈ M b (Ω) N and ξ = (ξ 1 , ..., ξ N ) ∈ C b (Ω) N . The weak* convergence in M b (Ω) N is understood in the usual sense, i.e., Φ k → Φ weakly* in M b (Ω) N as k → +∞ if and only if Φ k , ξ → Φ, ξ for any ξ ∈ C b (Ω) N .
Let us now collect the basic notations used in the thesis.

R N the N -dimensional Euclidean space |.|
Euclidean (or generally Hilbertian) norm B(x, r) the ball of center x and radius r in

R N [x, y] segment joining x to y, i.e., [x, y] := {(1 -t)x + ty : t ∈ [0, 1]} [x, y[ [x, y[:= {(1 -t)x + ty : 0 ≤ t < 1[} L N the N -dimensional Lebesgue measure Lip(Ω)
the set of Lipschitz functions on Ω w.r.t. the Euclidean norm Lip 1 (Ω) the set of 1-Lipschitz functions on Ω w.r.t. the Euclidean norm φ k ⇒ φ φ k converges uniformly to φ M b (X) the space of signed finite Radon measures on X M + b (X) the set of non-negative finite Radon measures on X µ 1 ≪ µ 2 the measure µ 1 is absolutely continuous w.r.t. the Dirac mass measure at x f + , f - positive and negative parts of f

Proj K projection on the set K χ A characteristic function of A, i.e., χ A (x) = 1 if x ∈ A and χ A (x) = 0 if x / ∈ A I K indicator function of K, i.e., I(x) = 0 if x ∈ K and I(x) = +∞ otherwise
., . V,V * duality bracket between V and V *

Optimal Transport

For the optimal mass transport theory, the two books of C. Villani [START_REF] Villani | Topics in Optimal Transportation[END_REF][START_REF] Villani | Optimal Transport, Old and New[END_REF], the monograph of L. Ambrosio et al. [3] and the new book of F. Santambrogio [START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF] are used as basic references in the sequel.

Monge-Kantorovich problem

Given two non-negative Radon measures µ and ν with equal masses defined on two subsets X ⊂ R N and Y ⊂ R N , respectively, the Monge optimal transport problem is to find a map T : X -→ Y that transports µ onto ν, i.e., T #µ = ν (meaning ν(B) = µ(T -1 (B)) for all Borel sets B ⊂ Y ) and to minimize the transport cost

X |x -T (x)|dµ(x).
In other words, Monge's problem reads as follows inf

T #µ=ν X |x -T (x)|dµ(x). (MP)
A competitor T for (MP) is called a transport map while a minimizer is indicated as optimal transport map or simply optimal map.

It is well-known that the Monge problem is in general ill-posed. The set of transport maps may be empty, nonconvex and noncompact under usual topologies 1. Preliminaries (see e.g. [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF][START_REF] Urbas | Mass transfer problems[END_REF]). Moreover, it could happen that no transport map realizes the minimum even if the set of transport maps is not empty. In addition, the uniqueness of optimal transport map does not hold in general.

In 1942, L. Kantorovich [START_REF] Kantorovich | On the translocation of masses[END_REF] introduced a problem that he made several years later [START_REF] Kantorovich | On a problem of Monge[END_REF] the connection with Monge's work in the sense that Kantorovich's problem is a relaxation of Monge's problem. The idea is to enlarge the admissible set of Monge's problem. Kantorovich's problem reads as follows inf

γ∈π(µ,ν) X×Y |x -y|dγ(x, y), (MK)
where π(µ, ν) is the set of the so-called transport plans defined by

π(µ, ν) := γ ∈ M + b (X × Y ) : π x #γ = µ, π y #γ = ν .
The problem (MK) is nowadays called Monge-Kantorovich (MK) problem. It is known that, for any transport map T , one always has γ := (id, T )#µ ∈ π(µ, ν). Moreover, in contrast to Monge's problem, the set π(µ, ν) is always non-empty (for instance, by taking γ :

= 1 µ(X) (µ ⊗ ν) ∈ π(µ, ν)) and the MK problem is a linear programming in the (possibly infinite-dimensional) space M b (X × Y ).
In the problem (MK), one can replace the cost function |x -y| by any proper l.s.c. function c : X × Y -→ [0, +∞]. In this setting, the existence result can be shown by means of the direct method in calculus of variations (see e.g. [START_REF] Villani | Optimal Transport, Old and New[END_REF]Chapter 4]).

An interesting feature of the MK problem is that it admits a dual problem. Let us summarize some results in the following theorem.

, ν ∈ M + b (R N ) be such that µ(R N ) = ν(R N )
. Then one has: (i) The MK problem has an optimal plan and the Kantorovich duality holds, i.e.

min γ∈π(µ,ν)      R N ×R N c(x, y) dγ(x, y)      = sup R N u dµ + R N v dν : (u, v) ∈ S c (µ, ν) , (1.1)
where

S c (µ, ν) := (u, v) ∈ L 1 µ (R N ) × L 1 ν (R N ) : u(x) + v(y) ≤ c(x, y) ∀x, y ∈ R N .
(ii) It does not change the value of the supremum in the right-hand side of (1.

(iii) If c(x, y) ≤ C µ (x) + C ν (y) for some (C µ , C ν ) ∈ L 1 µ × L 1
ν then the dual problem on the right-hand side (called Kantorovich dual problem) has an optimal solution. (iv) If the cost function c is a distance then the Kantorovich dual problem can be rewritten as sup

R N u d(ν -µ) : u ∈ L 1 µ ∩ L 1 ν , u(y) -u(x) ≤ c(x, y) ∀x, y ∈ R N . (1.2)
A solution u of the Kantorovich dual problem (1.

2) is called Kantorovich potential. Without abusing, the term Kantorovich potential is also understood for the general case.

The Kantorovich dual maximization problem in (1.1) turns out to be very useful to show the existence of optimal map for (MP). In this direction, motivated by problems in fluid mechanics, Y. Brenier [START_REF] Brenier | Polar factorization and monotone rearrangement of vector-valued functions[END_REF] showed for the quadratic cost c(x, y) := |x -y| 2 and µ ≪ L N that there exists a unique optimal transport map T in Monge's problem which is the gradient of a convex function and

T (x) = ∇ 1 2 |x| 2 -φ(x) = x -∇φ(x),
for any φ Kantorovich potential transporting µ onto ν. Moreover, γ := (id, T )#µ is an optimal plan for the MK problem. Similar results hold true if one replaces the quadratic cost by c(x, y) := h(xy), where h is strictly convex (see [START_REF] Gangbo | The geometry of optimal transportation[END_REF]). In [START_REF] Mccann | Polar factorization of maps on Riemannian manifolds[END_REF], R.J. McCann extended Brenier's result to Riemannian manifolds.

The costs of the form c(x, y) = |x -y| p with 1 ≤ p ≤ +∞ play an important role in applications. The applications need very often the fact that one can define the quantity

W p (µ, ν) :=    min γ∈π(µ,ν) X×X |x -y| p dγ(x, y)    1 p
, which turns out to be a metric on P p (X) the space of probability measures with finite pth order moment, i.e. η ∈ P p (X) if X |x| p dη < +∞, and it metrizes the weak convergence (i.e. test functions are bounded continuous) on P p (X) whenever X is bounded (see e.g. [START_REF] Villani | Optimal Transport, Old and New[END_REF]Chapter 6]). We call W p (µ, ν) the p-Wasserstein distance between µ and ν.

1. Preliminaries

Benamou-Brenier formula

Among equivalent formulations for the optimal transport, we should mention the so-called dynamical formulation (or Benamou-Brenier formula) that, for the quadratic cost c(x, y) = |x -y| 2 , reads as follows

W 2 (µ, ν) 2 = min 1 0 R N |υ t (x)| 2 dρ t (x)dt,
where the minimum is taken over all pairs (ρ t , υ t ), with ρ t a curve of measures and υ t a time-dependent velocity, such that the following continuity equation is satisfied

∂ t ρ t + div x (υ t ρ t ) = 0, ρ 0 = µ and ρ 1 = ν.
As usual, the continuity equation is understood in the weak sense of distribution, that is,

1 0 R N ∂ t φdρ + 1 0 R N ∇ x φ • υdρ = R N φ(1, .)dν - R N φ(0, .)dµ, (1.3)
for any compactly supported smooth function φ ∈ C ∞ c ([0, 1] × R N ). For short, we denote (1.3) by -div t,x (ρ, υρ) = δ 1 ⊗ νδ 0 ⊗ µ throughout the thesis.

The dynamical formulation was introduced by Benamou & Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] for numerical computation. The approach is then generalized with theoretical point of view for Lagrangian costs (see [START_REF] Bernard | Optimal mass transportation and Mather theory[END_REF]) and for transport-type problems (see for instance [START_REF] Brasco | A Benamou-Brenier approach to branched transport transport[END_REF][START_REF] Piccoli | On properties of the generalized Wasserstein distance[END_REF] and the references therein).

Beckmann problem and Monge-Kantorovich equation

In the case where c(x, y) := |x -y|, the Kantorovich dual problem can be written as follows, called Kantorovich-Rubinstein dual formulation, sup

   R N ud(ν -µ) : u ∈ Lip 1 (R N )    . (1.4)
As shown by Evans & Gangbo [START_REF] Evans | 136 Optimal Partial Transport and Constrained Matching Problems Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance[END_REF] (see also [START_REF] Evans | Partial differential equations and Monge-Kantorovich mass transfer[END_REF]), under additional conditions on µ and ν, that any Kantorovich potential u of (1.4) is characterized by the following Optimal Partial Transport and Constrained Matching Problems

1.3. Tangential gradient to a measure PDE          -∇ • (a(x)∇u(x)) = ν -µ in D ′ (R N ) a ∈ L ∞ , a ≥ 0, |∇u|≤ 1 a (|∇u|-1) = 0.
(1.5)

By using the functions a and u satisfied (1.5) via PDE methods, Evans & Gangbo [START_REF] Evans | 136 Optimal Partial Transport and Constrained Matching Problems Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance[END_REF] constructed an optimal map for (MP) with c(x, y) := |x -y|. This gives a deep result on the existence for this non-strictly convex cost function. There is by now a large literature on the existence of optimal map by several techniques (see for instance [START_REF] Ambrosio | Existence of optimal transport maps for crystalline norms[END_REF][START_REF] Ambrosio | Existence and stability results in the L 1 theory of optimal transportation[END_REF][START_REF] Bernard | The Monge problem for supercritical Mané potentials on compact manifolds[END_REF][START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF][START_REF] Th | The Monge problem in R d[END_REF][START_REF] Trudinger | On the Monge mass transfer problem[END_REF]).

Bouchitté-Buttazzo-Seppecher [START_REF] Bouchitté | Shape optimization solutions via Monge-Kantorovich equation[END_REF] generalized the system (1.5) for general Radon measures µ and ν via the notion of tangential gradient to a measure that was introduced by themselves in [START_REF] Bouchitté | Energies with respect to a measure and applications to low dimensional structures[END_REF] (see the next section if necessary). In this case, the PDE (1.5), called Monge-Kantorovich (MK) equation, reads as

         -∇ • Φ = ν -µ in D ′ (R N ) Φ ∈ M b (R N ) N , |∇u|≤ 1 Φ |Φ| = ∇ |Φ| u |Φ|-a.e..
On the other hand, by means of the Fenchel-Rockafellar duality, the Kantorovich-Rubinstein dual problem (1.4) admits another dual problem reading as min

   R N d|Φ|: Φ ∈ M b (R N ) N , -∇ • Φ = ν -µ in D ′ (R N )    . (1.6)
This new formulation is called minimal flow or Beckmann problem in the connection with a continuous model of transportation proposed by Beckmann [START_REF] Beckmann | A continuous model of transportation[END_REF].

Tangential gradient to a measure

The notion of tangential gradient to a measure was first introduced by Bouchitté-Buttazzo-Seppecher [START_REF] Bouchitté | Energies with respect to a measure and applications to low dimensional structures[END_REF] with applications to low dimensional structures. Here we recall few useful notations and results from [START_REF] Bouchitté | Energies with respect to a measure and applications to low dimensional structures[END_REF] with slight modifications as in [START_REF] Ch | Dynamic formulation of optimal transport problems[END_REF]. Given any (non-negative) finite Radon measure η on R N , it admits a tangent space at η-a.e. point x ∈ R N , denoted by T η (x), which is a linear subspace of R N .

Preliminaries

Set

X η := φ ∈ L 1 η (R N ; R N ) : div(φη) ∈ M b (R N ) ,
where the divergence constraint is understood in the sense of distributions. In other words, there is a constant M such that

R N ∇ξ • φdη ≤ M ξ ∞ (1.7)
for any compactly supported smooth function ξ ∈ C ∞ c (R N ). Formally, if η is the Hausdorff measure H k over a k-dimensional smooth manifold S in R N , by taking all nonzero test functions ξ which vanish on S in (1.7), every vector field φ ∈ X η must be tangent to S.

T η (x) is defined as the envelope of all vectors φ(x) for φ running in X η . This is rigorously done by using the so-called η-essential union. Define

T η (x) := η -ess ∪ {φ(x) : φ ∈ X η } ,
where the η-essential union is defined as a η-measurable closed multifunction given by

• φ ∈ X η ⇒ φ(x) ∈ T η (x) η-a.e.;
• the η-essential union is minimal among all the multifunctions Γ(x) satisfying the previous properties, i.e. T η (x) ⊂ Γ(x) η-a.e.. , where S is a k-dimensional Lipschitz manifold in R N . Then T η (x) = T S (x) for η-a.e. x ∈ S with T S (x) being the classical tangent space to S at x. We denote by P η (x, .) the orthogonal projection on T η (x) for η-a.e. x. Given u ∈ C 1 (R N ), the tangential gradient of u, denoted by ∇ η u, is defined by

∇ η u(x) := P η (x, ∇u(x)). If moreover u ∈ C 1 (R N ) ∩ Lip(R N ) then ∇ η u ∈ L ∞ η (R N ; R N ).
As in [21, Proposition 2.1] or [START_REF] Ch | Dynamic formulation of optimal transport problems[END_REF]Proposition 4.5], the tangential gradient operator ∇ η :

C 1 (R N ) ∩ Lip(R N ) → L ∞ η (R N ; R N
) is closable for the uniform convergence and weak* convergence, respectively. More precisely, one has

Proposition 1.3. Let {u n } ⊂ C 1 (R N ) be such that u n ⇒ 0 on R N and ∇ η u n ⇀ ξ weakly* in L ∞ η (R N ; R N ).
Then ξ = 0 η-a.e..

Tangential gradient to a measure

This proposition allows to extend the tangential gradient to any Lipschitz function u on R N . Indeed, let {u n } be a sequence of equi-Lipschitz functions such that u n ⇒ u on R N . Following Proposition 1.3, there is a unique ξ

∈ L ∞ η (R N ; R N ) such that ∇ η u n ⇀ ξ weakly* in L ∞ η (R N ; R N ).
One defines ∇ η u := ξ. By approximation, the following integration by parts formula holds

-div(φη), u = φ • ∇ η u dη for any φ ∈ X η , u ∈ Lip(R N ) ∩ C b (R N ). Remark 1.4. (i) Let η ∈ M + b (Ω) and u ∈ Lip(Ω).
Then ∇ η u := ∇ η ũ for any Lipschitz extension ũ on R N of u (it does not depend on the choice of ũ). (ii) If η = L N Ω then ∇ η u = ∇u a.e. for Lipschitz functions u on Lipschitz domain Ω.

We will need the following chain rule for the tangential gradient.

Proposition 1.5 (Chain rule for the tangential gradient). Let η ∈ M + b (R N ) and u be a Lipschitz continuous function defined on R N . Let G be a Lipschitz continuous function on R such that the set of non-differentiable points of G is finite. Then

∇ η G(u)(x) = G ′ (u(x))∇ η u(x) for η-a.e. x, (1.8)
where G ′ (u(x)) is the usual derivative with convention G ′ (u(x))∇ η u(x) = 0 when

∇ η u(x) = 0 even if G is not differentiable at u(x).
In particular, we have

(i) ∇ η u + = χ [u>0] ∇ η u and ∇ η u -= -χ [u<0] ∇ η u η-a.e. in R N ; (ii) ∇ η u = 0 η-a.e. on the set [u = c] := {x ∈ R N : u(x) = c} for a constant c ∈ R.
Proof. Let us first assume that G is continuously differentiable. In order to prove (1.8), it is enough to show that

R N ∇ η G(u) • Φ dη = R N G ′ (u)∇ η u • Φ dη, for every Φ ∈ L 1 η (R N ; R N ) such that Φ(x) ∈ T η (x) η-a.e. x ∈ R N . Let u ε ∈ C ∞ (R N
) be the regularization of u by convolution. Since u and G are Lipschitz, the sequences of equi-Lipschitz functions u ε and G • u ε converge uniformly to u and G • u on R N , respectively. Thus ∇ η u ε and ∇ η G(u ε ) converge to ∇ η u and

∇ η G(u) weakly* in L ∞ η (R N ; R N ), respectively. Since Φ(x) ∈ T η (x) η-a.e. x ∈ R N , 1. Preliminaries we have R N ∇ η G(u) • Φ dη = lim ε→0 R N ∇ η G(u ε ) • Φ dη = lim ε→0 R N ∇G(u ε ) • Φ dη = lim ε→0 R N G ′ (u ε )∇u ε • Φ dη = lim ε→0 R N G ′ (u ε )∇ η u ε • Φ dη = R N G ′ (u)∇ η u • Φ dη.
This gives the result (1.8) whenever G is continuously differentiable by taking

Φ = ∇ η G(u) -G ′ (u)∇ η u.
For (i), consider the function

G ε (r) :=    √ r 2 + ε 2 -ε if r > 0 0 if r ≤ 0 . Then G ε is
continuously differentiable and Lipschitz on R. Thus we have

R N ∇ η G ε (u) • Φ dη = R N G ′ ε (u)∇ η u • Φ dη = {[u>0]} u √ u 2 + ε 2 ∇ η u • Φ dη for every Φ ∈ L 1 η (R N ; R N ) such that Φ(x) ∈ T η (x) for η-a.e. x. Letting ε → 0, R N ∇ η u + • Φ dη = {[u>0]} ∇ η u • Φ dη = R N χ [u>0] ∇ η u • Φ dη.
The proof of the positive part ends up by choosing

Φ := ∇ η u + -χ [u>0] ∇ η u.
A similar proof is done for the negative part. For (ii), we can assume that c = 0. The proof follows from

∇ η u = ∇ η u + -∇ η u -. Now,
i := u -1 (R \ {r i }) and Ω := n i=1 Ω i . Since u is a constant on R N \ Ω i , i = 1, ..., n, we have ∇ η G(u)(x) = G ′ (u(x))∇ η u(x) = 0 η-a.e. x ∈ R N \ Ω i , i = 1, ..., n.
Optimal Partial Transport and Constrained Matching Problems

∇ η G(u)(x) = G ′ (u(x))∇ η u(x) η-a.e. x ∈ Ω. (1.9)
Let us assume that Ω = ∅ (if not, there is nothing to prove). Let G ε be a smooth approximation of G by convolution.

Let Φ ∈ L 1 η (R N ; R N ) be such that Φ(x) = 0 η-a.e. x in R N \ Ω. Then R N ∇ η G(u)Φ dη = lim ε→0 R N ∇ η G ε (u)Φ dη = lim ε→0 R N G ′ ε (u)∇ η uΦ dη = lim ε→0 Ω G ′ ε (u)∇ η uΦ dη (since Φ(x) = 0 η-a.e. x in R N \ Ω) = Ω G ′ (u)∇ η uΦ dη,
where we used the Lebesgue Dominated Convergence Theorem. Next, choosing

Φ = ∇ η G(u) -G ′ (u)∇ η u
as a test function, we obtain (1.9).

Fenchel-Rockafellar duality and ALG2 method

Let V and Z be Banach spaces. Let us consider an optimization problem of the form inf φ∈V

F(φ) + G(Λφ) (1.10)
where F : V -→ (-∞, +∞] and G : Z -→ (-∞, +∞] are convex, l.s.c. and Λ ∈ L(V, Z) the space of linear continuous functions from V to Z. Using F * and G * the convex conjugate functions (given by the Legendre-Fenchel transformation)

of F and G respectively, and Λ * is the adjoint operator of Λ, it is easy to see that

sup σ∈Z * (-F * (-Λ * σ) -G * (σ)) ≤ inf φ∈V F(φ) + G(Λφ), 1.
Preliminaries where Z * is the topological dual space associated with Z. This is the so-called weak duality. For the strong duality, which corresponds to equality we have the following well-known result.

Proposition 1.6 (cf. [START_REF] Ekeland | Convex Analysis and Variational Problems[END_REF]). Assume moreover that there exists φ 0 such that F(φ 0 ) < +∞, G(Λφ 0 ) < +∞ and G is continuous at Λφ 0 . Then the so-called Fenchel-Rockafellar dual problem

sup σ∈Z * (-F * (-Λ * σ) -G * (σ)) (1.11)
has at least a solution σ ∈ Z * and inf (1.10) = max (1.11). Moreover, in this case, φ is a solution to the primal problem (1.10) if and only if the optimality condition holds

   -Λ * σ ∈ ∂F(φ)
σ ∈ ∂G(Λφ).

(1.12)

We are now concerned with numerical approximations for the optimization problems (1.10) and (1.11), or equivalently for the optimality condition (1.12). Assume that V and Z are two Hilbert spaces. We introduce a new variable q ∈ Z to the primal problem (1.10) and we rewrite it in the form inf (φ,q)∈V ×Z : Λφ=q F(φ) + G(q).

To solve (1.12), it is sufficient to determine saddle-points of the augmented Lagrangian L r (φ, q; σ) := F(φ) + G(q) + σ, Λφq + r 2 |Λφ -q| 2 , r > 0.

In other words, we shall solve the problem min

(φ,q)∈V ×Z max σ∈Z * L r (φ, q; σ). (1.13)
This problem is solved by the so-called ALG2 method, also known as Alternating direction method of multipliers, which is given as follows: Given q 0 , σ 0 ∈ Z, we construct the sequences {φ i }, {q i } and {σ i }, i = 1, 2, ..., by

• Step 1:

φ i+1 = argmin φ∈V L r (φ, q i ; σ i ) = argmin φ∈V F(φ) + σ i , Λφ + r 2 |Λφ -q i | 2 .
1.4. Fenchel-Rockafellar duality and ALG2 method

• Step 2:

q i+1 = argmin q∈Z L r (φ i+1 , q; σ i ) = argmin q∈Z G(q) -σ i , q + r 2 |Λφ i+1 -q| 2 .
• Step 3:

σ i+1 = argmax σ∈Z * L r (φ i+1 , q i+1 ; σ) - 1 2r |σ -σ i | 2 = σ i + r(Λφ i+1 -q i+1 ).
Formally, if the sequences {φ i }, {q i } and {σ i } are convergent then their limits should be solutions of (1.13). For the theory of this method and its interpretation, we refer the reader to [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF][START_REF] Fortin | Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems[END_REF][START_REF] Gabay | A dual algorithm for the solution of nonlinear variational problems via finite element approximation[END_REF][START_REF] Glowinski | Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics[END_REF][START_REF] Glowinski | Numerical Analysis of Variational Inequalities[END_REF]. Here, we recall the convergence result of this method which is enough for our discretized problems later.

Theorem 1.7 (cf. [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF], Theorem 8). Fixed r > 0, assuming that V = R n , Z = R m and that Λ has full column rank. If there exists a solution to the optimality relations (1.12) then {φ i } converges to a solution of the primal problem (1.10) and {σ i } converges to a solution of the dual problem (1.11). Moreover, {q i } converges to Λφ * , where φ * is the limit of {φ i }.

The proof of this result in the case of finite-dimensional spaces V and Z can be found in [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF]. The result holds true in infinite-dimensional Hilbert spaces under additional assumptions. One can see [START_REF] Glowinski | Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics[END_REF] and [START_REF] Fortin | Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems[END_REF] for more details in this direction.

Chapter 2 Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

Optimal partial mass transport, which is a variant of the optimal transport problem, consists in transporting effectively a prescribed amount of mass from a source to a target. The problem was first studied by Caffarelli & McCann [27, Ann. of Math., 2010] and Figalli [48, Arch. Ration. Mech. Anal., 2010] with a particular attention to the quadratic cost. In this chapter, our aim is to study the optimal partial transport problem with Finsler distance costs including the Monge cost given by the Euclidian distance. Among our results, we introduce a PDE of Monge-Kantorovich type with a double obstacle to characterize active submeasures, Kantorovich potential and optimal flow for the optimal partial transport problem. This new PDE enables us to study the uniqueness and monotonicity results w.r.t. Lagrangian multiplier λ for the active submeasures. Another interesting issue of our approach is its convenience for numerical analysis and computation that we develop in Chapter 3.

Introduction

The partial Monge-Kantorovich (PMK) problem (or optimal partial transport) is a very natural extension of the original optimal transport problem. Given µ, ν ∈ M + b (R N ), a prescribed total mass m satisfying 0 ≤ m ≤ m max with m max := min µ(R N ), ν(R N ) and a measurable ground cost c : R N × R N -→ [0, +∞), the

(R N ×R N )    R N ×R N c(x, y)dγ : π x #γ ≤ µ, π y #γ ≤ ν, γ(R N × R N ) = m    .
This generalized problem brings out new unknown quantities ρ 0 := π x #γ and ρ 1 := π y #γ. In other words, let us denote by Sub m (µ, ν) the set of submeasures of mass m which is defined by

Sub m (µ, ν) := {(ρ 0 , ρ 1 ) ∈ M + b (R N )×M + b (R N ) : ρ 0 ≤ µ, ρ 1 ≤ ν, ρ 0 (R N ) = ρ 1 (R N ) = m}.
Then the PMK problem reads min K(γ) :=

R N ×R N c(x, y)dγ : γ ∈ π m (µ, ν) , (PMK)
where

π m (µ, ν) := γ ∈ π(ρ 0 , ρ 1 ) : (ρ 0 , ρ 1 ) ∈ Sub m (µ, ν) .
An element (ρ 0 , ρ 1 ) ∈ Sub m (µ, ν) is called a couple of active submeasures if there exists an optimal plan γ of (PMK) such that γ ∈ π(ρ 0 , ρ 1 ).

As mentioned in the general introduction, the existence, uniqueness and regularity issues for active submeasures were initially studied by Caffarelli & McCann [27] with a special focus on the quadratic cost, i.e., c(x, y) = |x -y| 2 . Thereafter, Figalli [START_REF] Figalli | The optimal partial transport problem[END_REF] improves the results. In particular, he removes the disjointness assumption on the supports of the initial measures.

Our aim here is to give a complete and rigorous study of (PMK) with a Finsler distance cost d F (x, y) (including the case of Euclidean distance cost). Before going further, let us take a while to comment our approach and main ideas. It is not difficult to see that (PMK) is a bilevel optimization problem that aims to find the active submeasures with the constraint on the total mass as well as the optimal plan. The authors in [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF] introduce a Lagrange multiplier λ for the mass constraint, add a point at infinity which acts as a tariff-free reservoir for transporting the extra mass and study the relations given by classical duality results. In this way, they could deduce existence and uniqueness of minimizers when the supports of µ and ν are disjoint. As to the strategy of [START_REF] Figalli | The optimal partial transport problem[END_REF] is to study directly the minimization problem by studying the convexity of the function that associates to each m the total Monge-Kantorovich work. In particular, this allows the author to prove Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation the uniqueness without disjointness condition. The techniques used in [START_REF] Bao | An Introduction to Riemann-Finsler Geometry[END_REF][START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF] also deduce the uniqueness for costs which require existence and uniqueness of optimal plan in the full transfer case (see [START_REF] Bao | An Introduction to Riemann-Finsler Geometry[END_REF]Proposition 2.9], [START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF]Renark 2.11] for precise statements). However, these techniques do not work for the uniqueness of active submeasures of (PMK) with Finsler costs. Our point of view is to obtain the uniqueness via the study of the so-called OMK equation by PDE techniques.

We begin by handling directly the problem for general costs by adding two arbitrary sites in R N to process the problem into a balanced optimal mass transportation. Taking the cost for free to the new sites, we show that the new total work coincides with the total work of the PMK problem. Moreover, combining this with classical duality results, we introduce a bilevel maximization problem to provide a natural dual partial Monge-Kantorovich (DPMK) problem for the optimal partial transport. Then, using the triangle inequality satisfied by d F , we give the Kantorovich-Rubinstein type duality for (PMK) with Finsler distance costs. In the case of Finsler distances, the variable of the DPMK problem can be expressed as a couple (λ, u) where u can be interpreted as the Kantorovich potential associated with (PMK) and λ would be used to give informations on active submeasures. Recall that in the case where the cost is given by the square of the Euclidean distance (cf. [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF]), the connection between the obstacle Monge-Ampère PDE and (PMK) is given by a map that associates to each value parameter λ a solution of the Monge-Ampère PDE. In our case, we introduce a map that associates to each value λ a solution of the OMK equation. Then, we show how a right value λ m enters in connection with the Kantorovich potential to bring out the solution of (PMK). Among the main issues of our approach, the uniqueness of the active submeasures holds true in the case where µ and ν are absolutely continuous without disjointness condition of the supports. As a consequence, we also obtain the monotonicity of active submeasures with respect to Lagrange multiplier λ. This chapter is organized as follows: In the next section 2.2, we introduce our main results for the PMK problem with Finsler distances and the OMK equation. The remaining sections aim to prove the main results. In section 2.3, we first prove the Kantorovich type duality for the PMK problem with general costs and then lead to the duality for Finsler distance costs. The existence and uniqueness issues for the OMK equation are studied in section 2.4. In section 2.5, we show the connection between the OMK equation and the active submeasures by using the DPMK problem and the partial minimum flow problem. Thanks to this connection and the results on the OMK equation, we deduce the uniqueness of active submeasures. To finish the proofs of the main results, we also study 2.2. Main results some strong L 1 continuous dependence and monotonicity of solution of the OMK equation with respect to the obstacle in section 2.6.

Main results

We give in this section our main results for (PMK) with Finsler distance costs c = d F . Let us begin with a reminder concerning Finsler distances. A continuous function

F : R N × R N -→ [0, +∞) is called Finsler metric on R N if • F (x, .) is convex w.r.t. the second variable for fixed x ∈ R N ; • F (x, .) is positively 1-homogeneous for fixed x ∈ R N , i.e. F (x, tv) = tF (x, v) for every v ∈ R N and t > 0.
In addition, throughout the thesis, we assume that F is nondegenerate in the sense that there exist M 1 , M 2 > 0 such that

M 1 |v|≤ F (x, v) ≤ M 2 |v| ∀(x, v) ∈ R N × R N .
The Finsler distance d F on R N is defined by

d F (x, y) := inf ξ∈Lip([0,1];R N )    1 0 F (ξ(t), ξ(t))dt : ξ(0) = x, ξ(1) = y    . (2.1)
Under the above assumptions on F , the inf problem (2.1) is actually the minimum and d F is a (not necessarily symmetric) distance, i.e. d F satisfies

• d F (x, y) ≥ 0; d F (x, y) = 0 if and only if x = y; • d F (x, y) ≤ d F (x, z) + d F (z, y) for any x, y, z ∈ R N . An example of a Finsler metric which is not a norm in R is given by F (x, v) = av -+ bv + with 0 < a = b. More generally, for each x ∈ R N fixed, given vectors d x 1 , ..., d x k = 0 depending on x such that, for any 0 = v ∈ R N , max 1≤i≤k { v, d x i } > 0, we define F (x, v) := max 1≤i≤k { v, d x i } for any v ∈ R N
which turns out to be a Finsler metric.

We say that a function u is 1-d F Lipschitz if and only if

u(y) -u(x) ≤ d F (x, y) for all x, y.
Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

The polar function F * of F is defined by

F * (x, p) := sup v∈R N { v, p : F (x, v) ≤ 1} for any x, p ∈ R N .
It is easy to see that F * is also a continuous, nondegenerate Finsler metric and

v, p ≤ F * (x, p) F (x, v) for all x, v, p ∈ R N .
Coming back to (PMK) with Finsler distances, our analysis begins with the following Kantorovich-Rubinstein type duality.

K(σ * ) = max (λ,u)∈[0,+∞)×L λ d F D(λ, u) := u d(ν -µ) + λ(m -ν(R N )) , (2.2)
where

L λ d F := u ∈ L 1 µ ∩ L 1 ν : u(y) -u(x) ≤ d F (x, y), 0 ≤ u(x) ≤ λ for all x, y ∈ R N .
In addition, σ ∈ π m (µ, ν) and (λ, u) ∈ R + × L λ d F are solutions of (PMK) and of the DPMK problem (2.2), respectively, if and only if

u(x) = 0 for (µ -π x #σ)-a.e. x ∈ R N , u(x) = λ for (ν -π y #σ)-a.e. x ∈ R N and u(y) -u(x) = d F (x, y) for σ-a.e. (x, y) ∈ R N × R N .
Next, we introduce a new nonlinear PDE that we call the obstacle Monge-Kantorovich (OMK) equation. Then, we use this PDE to show the uniqueness of active submeasures whenever the data µ and ν are absolutely continuous with respect to the Lebesgue measure.

To introduce our PDE, we see that the DPMK problem (2.2) reads as

max λ≥0 max u D(λ, u) : u ∈ L λ d F .
Moreover, formally, for any fixed λ ≥ 0, the Euler-Lagrange equation associated with the problem max

u D(λ, u) : u ∈ L λ d F (2.3)
Optimal Partial Transport and Constrained Matching Problems

Main results

is given by the following PDE

         θ -∇ • Φ = ν -µ in D ′ (R N ) Φ • ∇u = F (., Φ) u ∈ L λ d F , θ ∈ ∂I [0,λ] (u). (P λ )
This is a double obstacle problem associated with (PMK) for c = d F . And, formally we conclude that the study of (PMK) is closely connected to the study of the dependence of solution of (P λ ) with respect to λ. Our aim now is to study this connection to get a characterization of active submeasures. Before going further, let us give the notion of solution to the OMK equation.

Definition 2.2. For a fixed λ ≥ 0, a triplet (θ, Φ, u) ∈ M b (R N )×M b (R N ) N ×L λ d F
is said to be a solution to the OMK equation (P λ ) if

         θ -∇ • Φ = ν -µ in D ′ (R N ) Φ |Φ| (x) • ∇ |Φ| u(x) = F x, Φ |Φ| (x) |Φ|-a.e. x ∈ R N u = 0 θ --a.e. in R N and u = λ θ + -a.e. in R N ,
where θ + and θ -are the positive and negative parts of the measure θ given by the Hahn-Jordan decomposition.

Without abusing, we also say that a Radon measure

θ ∈ M b (R N ) is a solution of (P λ ) if there exists (Φ, u) ∈ M b (R N ) N × L λ d F such that (θ, Φ, u) satisfies the OMK equation (P λ ).
It is to be expected that νθ + and µθ -are active submeasures. The important point to note here is that we do not impose any constraints of type θ + ≤ ν and θ -≤ µ in the definition of the OMK equation. These estimates are summarized in the following theorem and will be proved later via PDE techniques.

Theorem 2.3 (Existence and estimates for OMK equation

). Given µ, ν ∈ M + b (R N ) and λ ≥ 0, the OMK equation (P λ ) admits at least one solution (θ, Φ, u). Moreover, θ -≤ µ -µ ∧ ν ≤ µ and θ + ≤ ν -µ ∧ ν ≤ ν for any solution (θ, Φ, u).
Because of the degeneracy of the OMK equation, the question of the uniqueness of solution for (P λ ) is delicate. In fact, one cannot in general expect the uniqueness Optimal Partial Transport and Constrained Matching Problems Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation of components Φ and u of solution for the OMK equation (P λ ). However, we can prove the uniqueness of component θ whenever µ and ν are absolutely continuous with respect to the Lebesgue measure.

Theorem 2.4 (Uniqueness of θ). Assume that µ, ν ∈ L 1 (R N ) + . Let θ 1 and θ 2 be two solutions to the same OMK equation

(P λ ). Then θ 1 , θ 2 ∈ L 1 (R N ) and θ 1 = θ 2 .
Now, we come to the connection between the OMK equation and (PMK).

(ρ 0 , ρ 1 ) := (µ -θ - λ , ν -θ + λ ) is a couple of active submeasures corresponding to m λ = (µ -θ - λ )(R N ). (ii) Conversely, if (ρ 0 , ρ 1 ) ∈ Sub m (µ, ν) is a given couple of active submeasures and m ∈ [(µ ∧ ν)(R N ), m max ] then for any λ m ≥ 0 such that λ m ∈ argmax λ≥0 max u D(λ, u) : u ∈ L λ d F , the measure θ λm defined by θ - λm := µ -ρ 0 and θ + λm := ν -ρ 1
is a solution of the OMK equation (P λm ).

As a consequence of Theorems 2.5 and 2.4, we have the uniqueness for (PMK).

Corollary 2.6 (Uniqueness of active submeasures

). Let µ, ν ∈ L 1 (R N ) + be compactly supported and m ∈ [ µ ∧ ν L 1 , m max ].
There exists a unique couple of active submeasures.

To end up this section of main results, we propose to study the maps that associate to each λ ≥ 0 the corresponding active submeasures and their total mass in the case µ, ν ∈ L 1 (R N ). Thanks to Theorems 2.3, 2.5 and 2.4, for any λ ≥ 0 there exist a unique mass

m λ := (µ -θ - λ )(R N ) and a unique couple of active submeasures (ρ λ 0 , ρ λ 1 ) := (µ -θ - λ , ν -θ + λ ) corresponding to m λ . Set m : [0, ∞) → [(µ ∧ ν)(R N ), m max ] λ → m(λ) := m λ
Optimal Partial Transport and Constrained Matching Problems

2.2. Main results and R : [0, ∞) → L 1 (R N ) × L 1 (R N ) λ → R(λ) := (ρ λ 0 , ρ λ 1 )
. To simplify the presentation, let us denote

Sub opt (µ, ν) := (ρ 0 , ρ 1 ) : (ρ 0 , ρ 1 ) is a couple of active submeasures corresponding to some m ∈ [(µ ∧ ν)(R N ), m max ] .
Theorem 2.7. Let µ, ν ∈ L 1 (R N ) + be compactly supported. We have that (i) The map m is continuous, non-decreasing and surjective. (ii) The map R is continuous, non-decreasing and surjective from [0, ∞) to Sub opt (µ, ν).

It is known that the monotonicity of active submeasures corresponding to the mass m is obtained for continuous cost c (see [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF]Theorem 3.4]) and that the monotonicity corresponding to Lagrange multiplier λ is guaranteed for costs satisfying the left twist condition (see [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF]Sections 2 and 3]). Our result says that, even if the Finsler distances do not satisfy the condition, the monotonicity w.r.t. Lagrange multiplier λ still holds true. On the other hand, in the quadratic case, Davila and Kim obtain a Lipschitz continuous dependence of m λ on λ (see [START_REF] Dávila | Dynamics of optimal partial transport[END_REF]Theorem 4.5]). In the case of Finsler distances, we do not know this kind of estimates.

Remark 2.8. (i)

There is in general no uniqueness of active submeasures when m < (µ ∧ ν)(R N ). Indeed, in this case, all feasible submeasures ρ 0 ≡ ρ 1 ≤ µ ∧ ν are optimal. This is not a contradiction with our PDE approach by the fact that there is no such an OMK equation with λ ≥ 0 characterizing (PMK).

(ii) In general, the uniqueness of active submeasures does not hold true if both µ and ν are not in L 1 . For example, take µ = δ 1 + δ 3 , ν = δ 2 , where δ k is the Direct mass at k in R. Then all feasbile submeasures are optimal for any m.

(iii) We show here that the uniqueness holds true whenever µ, ν ∈ L 1 (R N ) by using PDE techniques. We do not know if this holds true when one of µ, ν belongs to L 1 (R N ).

32

Optimal Partial Transport and Constrained Matching Problems

Kantorovich-type duality

The aim of this section is to introduce the Kantorovich type duality for (PMK).

Our main result concerning duality for general costs is the following.

Theorem 2.9. Let µ, ν ∈ M + b (R N ) be measures with compact supports X and Y , m ∈ [0, m max ]. Assume that c is l.s.c. and bounded on X × Y . The PMK problem has a solution σ * ∈ π m (µ, ν) and the Kantorovich type duality turns into

K(σ * ) = min γ∈πm(µ,ν)    R N ×R N c(x, y)dγ(x, y)    = max (λ,φ,ψ)    R N φ dµ + R N ψ dν + λm : λ ∈ R + , (φ, ψ) ∈ S λ c (µ, ν)    , (2.4)
where

S λ c (µ, ν) := (φ, ψ) ∈ L 1 µ × L 1 ν : φ ≤ 0, ψ ≤ 0 and φ(x) + ψ(y) + λ ≤ c(x, y) ∀x, y ∈ R N . Moreover, σ ∈ π m (µ, ν) and (λ, φ, ψ) ∈ R + × S λ c (µ, ν) are solutions if and only if φ(x) = 0 for (µ -π x #σ)-a.e. x ∈ R N , ψ(y) = 0 for (ν -π y #σ)-a.e. y ∈ R N and φ(x) + ψ(y) + λ = c(x, y) for σ-a.e. (x, y) ∈ R N × R N . (2.5)
The maximization problem on the right hand side of (2.4) is called dual partial Monge-Kantorovich (DPMK) problem.

Remark 2.10. See that the duality formulations (2.4) is different from Caffarelli-McCann's duality (see [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF]Corollary 2.7]) which reads as, for fixed parameter λ,

min γ∈π ≤ (µ,ν)    R N ×R N (c -λ)dγ    = max u(x) + v(y) ≤ c(x, y) -λ u(x) ≤ 0, v(y) ≤ 0 R N u(x)dµ+ R N v(y)dν, where π ≤ (µ, ν) := γ ∈ M + b (R N × R N ) : π x #γ ≤ µ, π y #γ ≤ ν .

Kantorovich-type duality

Note that in this formulation there is no mass constraint on variable γ. The duality (2.4) follows the Caffarelli-McCann one in the case where the problem

min γ∈π ≤ (µ,ν) R N ×R N (c -λ)dγ (2.6)
has a unique optimal plan γ for each λ. Indeed, given a total mass m, by using [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF]Corollary 2.11], one can choose a λ * such that the unique solution γ λ * of (2.6)

w.r.t. λ * satisfies γ λ * (R N × R N ) = m.
It follows that the left hand side of (2.4) is less than or equal the right hand side. The inverse inequality can be verified directly. However, the uniqueness of the problem (2.6) is, in general, not satisfied.

On the other hand, in (2.4), λ is a variable and the duality is direct to (PMK). This formulation reduces to the duality for linear programmings in finitedimensional space when µ and ν are sums of Dirac masses (see e.g. [START_REF] Nocedal | Numerical optimization[END_REF]Theorem 13.1]). For numerical computations, the formulation (2.4) with λ as a variable is very useful. This issue will be discussed in Chapter 3.

Proof of Theorem 2.9. The existence of an optimal plan σ * ∈ π m (µ, ν) is standard, which can be shown by the direct method. Next, for any σ ∈ π m (µ, ν)

and (λ, φ, ψ) ∈ R + × S λ c (µ, ν), we have R N φ(x) dµ(x) + R N ψ(y) dν(y) + λm ≤ R N φ(x) dπ x #σ + R N ψ(y) dπ y #σ + λm = R N ×R N (φ(x) + ψ(y) + λ) dσ ≤ R N ×R N c(x, y)dσ.
(2.7)

As a consequence, sup

   R N φ dµ + R N ψ dν + λm : λ ∈ R + , (φ, ψ) ∈ S λ c (µ, ν)    ≤ min σ∈πm(µ,ν) K(σ).
To prove the converse inequality, we add two points x ∈ R N \ X and ŷ ∈ R N \ Y as extra production and consumption positions, respectively. Let us consider X := X ∪ {x}, Ŷ := Y ∪ {ŷ} as metric spaces (induced by the Euclidean distance) and the measures on X and Ŷ defined by, respectively,

µ = µ + (ν(Y ) -m))δ x and ν = ν + (µ(X) -m)δ y .
Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

Obviously, μ( X) = ν( Ŷ ). Then, let us consider the extra cost on X × Ŷ

ĉ(x, y) :=    c(x, y) if (x, y) ∈ X × Y 0 if x = x or y = ŷ.
From the assumptions on c, we have that ĉ is l.s.c. and bounded on the compact metric space X × Ŷ . It follows from Theorem 1.1 that

min γ∈π(μ,ν) X× Y ĉ(x, y) dγ = max (û,v)∈S ĉ( μ,ν) X û dμ + Ŷ v dν. Fix any γ ∈ π(μ, ν), set γ 1 := γ X×Y the restricted measure of γ on X × Y . It is easy to see that π x #γ 1 ≤ µ, π y #γ 1 ≤ ν and γ 1 (X × Y ) ≥ m. Let us define γ := m γ 1 (X×Y ) γ 1 ∈ π m (µ, ν) so that X×Y c(x, y)dγ ≤ X×Y c(x, y)dγ 1 = X× Ŷ ĉ(x, y)dγ.
Then,

min γ∈πm(µ,ν) X×Y c(x, y)dγ ≤ min γ∈π(μ,ν) X× Ŷ ĉ(x, y)dγ = max (û,v)∈S ĉ( μ,ν) X û dμ + Ŷ v dν.
To finish the proof, for any (û, v) ∈ S ĉ( μ, ν), we can moreover assume that û, v always take values in R. Set

u 1 := û + v(ŷ), v 1 := v + û(x) and λ := -û(x) -v(ŷ) ≥ 0. Since û(x)+v(y) ≤ ĉ(x, y), we see that u 1 ≤ 0 in X, v 1 ≤ 0 in Y and u 1 (x)+v 1 (y) ≤ c(x, y) -λ for any (x, y) ∈ X × Y. So, extending arbitrarily u 1 and v 1 up to R N such that (u 1 , v 1 ) ∈ S λ c (µ, ν), we get X û(x) dμ + Y v(y) dν = X û(x) dµ + Y v(y) dν + (ν(Y ) -m)û(x) + (µ(X) -m)v(ŷ) = X (û(x) + v(ŷ)) dµ + Y (v(y) + û(x)) dν -(û(x) + v(ŷ))m = X u 1 (x) dµ + Y v 1 (y) dν + λm.
Optimal Partial Transport and Constrained Matching Problems

2.3. Kantorovich-type duality Consequently, min γ∈πm(µ,ν) X×Y c(x, y) dγ ≤ max (û,v)∈S ĉ( μ,ν) X û dμ + Ŷ v dν ≤ sup    R N φ dµ + R N ψ dν + λm : λ ≥ 0, (φ, ψ) ∈ S λ c (µ, ν)    .
From the above arguments, the last supremum is actually the maximum.

At last, by (2.4), σ ∈ π m (µ, ν) and (λ, φ, ψ) ∈ R + × S λ c (µ, ν) are solutions of (PMK) and the DPMK problem, respectively, if and only if the inequalities in (2.7) are equalities. This is equivalent to the optimality criterion (2.5).

We have a further structure of the duality (2.4) for the costs satisfying triangle inequality. The following theorem is a more general form of Theorem 2.1.

Theorem 2.11. Under the assumptions and notations of Theorem 2.9, assume moreover that the cost function c satisfies triangle inequality and c(x, x) = 0 for any x ∈ R N . Then the DPMK problem can be rewritten as

K(σ * ) = max (λ,u) D(λ, u) := u d(ν -µ) + λ(m -ν(R N )) : λ ≥ 0 and u ∈ L λ c , (2.8)
where

L λ c := u ∈ L 1 µ ∩ L 1 ν : u(y) -u(x) ≤ c(x, y), 0 ≤ u(x) ≤ λ for any x, y ∈ R N .
In addition, σ ∈ π m (µ, ν) and (λ, u) ∈ R + × L λ c are solutions of (PMK) and of the DPMK (2.8), respectively, if and only if

u(x) = 0 for (µ -π x #σ)-a.e. x ∈ R N , u(x) = λ for (ν -π y #σ)-a.e. x ∈ R N and u(y) -u(x) = c(x, y) for σ-a.e. (x, y) ∈ R N × R N .
(2.9)

Proof of Theorem 2.11. We see that

min γ∈πm(µ,ν) R N ×R N c(x, y)dγ ≥ sup D(λ, u) : λ ≥ 0 and u ∈ L λ c .

36

Optimal Partial Transport and Constrained Matching Problems

Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation Indeed, for any γ ∈ π m (µ, ν) and u ∈ L λ c , we have

R N u d(ν -µ) + λ(m -ν(R N )) = R N -u(x) dµ + R N (u(y) -λ)dν + λm ≤ R N -u dπ x #γ + R N (u(y) -λ) dπ y #γ + λm ≤ R×R N c(x, y) dγ(x, y).
(2.10)

Conversely, for a given λ ≥ 0 and (φ, ψ) ∈ S λ c (µ, ν), we consider

u 1 (x) := sup y∈Y (ψ(y) + λ -c(x, y)) ≤ λ and u(x) := max{u 1 (x), 0} ∀x ∈ R N .
By using the triangle inequality, u is 1-Lipschitz with respect to c. Moreover, -u ≥ φ and u(y)λ ≥ ψ(y) ∀y ∈ Y (where we use the condition c(y, y) = 0).

Thus

R N u d(ν -µ) + λ(m -ν(R N )) ≥ R N φ dµ + R N ψ dν + λm.
By Theorem 3.1, the duality and the existence of a solution (λ * , u * ) are proved.

For the optimality condition (2.9), we use again the duality and (2.10) similarly to the case of general costs.

Remark 2.12. If c satisfies triangle inequality and c(x, x) = 0 for any x ∈ R N then the DPMK problem can be also written as

max (λ,u) u d(ν -µ) + λ(m -µ(R N )) : λ ∈ R + , u(y) -u(x) ≤ c(x, y), -λ ≤ u ≤ 0 ∀x, y .
Indeed, in the construction of u from (φ, ψ), we can take

u 1 (y) := inf x∈X (c(x, y) -φ(x) -λ) and u(y) := min{u 1 (y), 0} ∀y ∈ R N .

OMK equation

The aim of this section is to study the existence and uniqueness of solution for the OMK equation (P λ ). We also show some estimates for solution θ, which are useful for later use. We will make use of variational techniques for the existence while the uniqueness and estimates of θ are shown by using PDE techniques. In 2.4. OMK equation this section, we do not really need the compactness of the supports of µ and ν.

Existence of solution to the OMK equation

The existence of solution to the OMK equation is based on the dual approach. More precisely, by using the Fenchel-Rockafellar dual theory to the problem (2.3), we introduce a minimal flow-type problem. The OMK equation is then derived by optimality condition.

Proposition 2.13. Let µ, ν ∈ M + b (R N ) and λ ≥ 0 be fixed. We have

max u∈L λ d F R N ud(ν -µ) = min R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 : (Φ, θ 0 , θ 1 ) ∈ S , (2.11)
where

S := (Φ, θ 0 , θ 1 ) ∈ M b (R N ) N ×M + b (R N )×M + b (R N ) : -∇•Φ = ν -θ 1 -(µ-θ 0 ) .
Lemma 2.14. Let F be a nondegenerate Finsler metric and u be 1-d F Lipschitz, i.e., u(y)u(x) ≤ d F (x, y) for all x, y. Let u ε := ρ ε ⋆ u be the convolution of u with the standard mollifiers ρ ε on R N . Then

lim sup ε→0 F * (x, Du ε (x)) ≤ 1 for all x ∈ R N .
(2.12)

Proof. Fix x ∈ R N . There exists some ξ ε = 1 such that

F * (x, Du ε (x)) = Du ε (x) • ξ ε F (x, ξ ε ) = lim h→0 + u ε (x + hξ ε ) -u ε (x) F (x, hξ ε ) = lim h→0 + R N ρ ε (t) (u(x + hξ ε -t) -u(x -t)) dt F (x, hξ ε ) .
This implies that Since ξ εn = 1, up to a subsequence of {ξ εn }, we can assume moreover that

F * (x, Du ε (x)) ≤ lim sup h→0 + R N ρ ε (t)d F (x -t, x -t + hξ ε ) dt F (x, hξ ε ) ≤ lim h→0 + R N ρ ε (t) 1 0 F (x -t + τ hξ ε , hξ ε ) dτ dt F (x, hξ ε ) = R N ρ ε (t)F (x -t, ξ ε ) dt F (x, ξ ε ) .
ξ εn → ξ as ε n → 0. (2.15)
Thanks to (2.13), we get

F * (x, Du εn (x)) ≤ R N ρ εn (t)F (x -t, ξ εn ) dt F (x, ξ εn ) . ( 2
F * (x, Du ε (x)) = lim εn→0 F * (x, Du εn (x)) ≤ lim εn→0 R N ρ εn (t)F (x -t, ξ εn ) dt F (x, ξ εn ) = 1.
Remark 2.15. The lower semicontinuity of F is not enough to hold (2.12). Indeed, we take the lower semicontinuous, nondegenerate Finsler metric F and 1-d F Lipschitz function u on R defined by, respectively,

F (x, v) =    |v| if x ≤ 0 2|v| if x > 0 for x, v ∈ R and u(x) =    x if x ≤ 0 2x if x > 0 for x ∈ R.
Then,

F * (x, p) =    |p| if x ≤ 0 1 2 |p| if x > 0 and u ′ ε (x) = R ρ ε (s)u ′ (x -s)ds. Therefore, u ′ ε (0) = [s≥0] ρ ε (s)ds + 2 [s<0] ρ ε (s)ds = 3 2 and F * (0, u ′ ε (0)) = 2.

OMK equation

The latter is equivalent to

q • ∇u(x) ≤ F (x, q) ∀x ∈ R N , ∀q ∈ R N .
In the case where u is non-smooth, we have the following characterization via the tangential gradient.

Lemma 2.16. For any 1-d F Lipschitz function u and

Φ ∈ M b (R N ) N such that ∇ • Φ ∈ M b (R N ), we have Φ |Φ| (x) • ∇ |Φ| u(x) ≤ F (x, Φ |Φ| (x)) |Φ|-a.e. x ∈ R N .
Proof. Taking u ε as in Lemma 2.14, for any Borel subset B, we have

B Φ |Φ| •∇ |Φ| ud|Φ|= lim ε→0 B Φ |Φ| (x)•∇u ε (x)d|Φ|≤ lim sup ε→0 B F * (x, ∇u ε (x))F (x, Φ |Φ| (x))d|Φ|.
Letting ε → 0, using Fatou's Lemma and Lemma 2.14, we get

B Φ |Φ| (x) • ∇ |Φ| u(x)d|Φ|(x) ≤ B F (x, Φ |Φ| (x))d|Φ|(x).
The proof ends up by the arbitrariness of Borel set B.

Proof of Proposition 2.13. The case λ = 0 is obvious. We now assume that λ > 0.

1. Let us first show that max

u∈L λ d F R N ud(ν -µ) ≤ inf R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 : (Φ, θ 0 , θ 1 ) ∈ S .
Fix any u ∈ L λ d F and (Φ, θ 0 , θ 1 ) ∈ S. Taking u as a test function in the equation

-∇ • Φ = ν -θ 1 -(µ -θ 0 ), using Lemma 2.16, we have R N ud(ν -µ) = R N Φ |Φ| ∇ |Φ| ud|Φ|+ R N udθ 1 - R N udθ 0 ≤ R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 .
Thus, sup

u∈L λ d F R N ud(ν -µ) ≤ inf R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 : (Φ, θ 0 , θ 1 ) ∈ S .
It is easy to see that the supremum is actually the maximum by the direct method. 2. Obviously, we have max

R N ud(ν -µ) : u ∈ L λ d F ≥ sup R N ud(ν -µ) : u ∈ L λ d F , u ∈ C 1,1 (R N ) .
It remains to show that sup

R N ud(ν -µ) : u ∈ C 1,1 (R N ) L λ d F = min R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 : (Φ, θ 0 , θ 1 ) ∈ S .
(2.17)

On the other hand, sup

R N ud(ν -µ) : u ∈ C 1,1 (R N ) L λ d F = sup R N ud(ν -µ) : u ∈ C 1,1 (R N ), F * (x, ∇u(x)) ≤ 1, 0 ≤ u(x) ≤ λ ∀x ∈ R N = -inf u∈V F(u) + G(Λu) ,
where

F(u) := - R N ud(ν -µ) ∀u ∈ V := C 1,1 (R N ) C b (R N ), Λ(u) := (∇u, -u, u) ∈ Z := C b (R N ; R N ) × C b (R N ) × C b (R N )
and, for all (q, z, w) ∈ Z,

G(q, z, w) :=    0 if z(x) ≤ 0, w(x) ≤ λ and F * (x, q(x)) ≤ 1 ∀x ∈ R N +∞ otherwise.
We use the W 1,∞ -norm and L ∞ -norm for the spaces V and Z, respectively, i.e.

u V := u L ∞ + ∇u L ∞ and (q, z, w) Z := q L ∞ + z L ∞ + w L ∞ . Now,
F(u) + G(Λ(u)) = max (Φ,θ 0 ,θ 1 )∈M b (R N ) N ×M b (R N )×M b (R N ) -F * (-Λ * (Φ, θ 0 , θ 1 )) -G * (Φ, θ 0 , θ 1 ) .
The proof of (2.17) is completed by computing explicitly the quantities in this maximization problem.

• Since F is linear, F * (-Λ * (Φ, θ 0 , θ 1 )) is finite (and is equal to 0) if and only if

-Λ * (Φ, θ 0 , θ 1 ), u = F(u) = - R N ud(ν -µ) for any u ∈ V, or equivalently Φ, ∇u -θ 0 , u + θ 1 , u = ν -µ, u for any u ∈ V, i.e. -∇ • Φ = ν -θ 1 -(µ -θ 0 ) in D ′ (R N ).
• For G * (Φ, θ 0 , θ 1 ), we have

G * (Φ, θ 0 , θ 1 ) = sup q∈C b (R N ;R N ):F * (x,q(x))≤1,∀x Φ, q + sup z∈C b (R N ):z≤0 θ 0 , z + sup w∈C b (R N ):w≤λ θ 1 , w =      R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 if θ 0 ≥ 0 and θ 1 ≥ 0 +∞ otherwise.
Proposition 2.17. Given µ, ν ∈ M + b (R N ) and λ ≥ 0, we have that: (i) If u and (Φ, θ 0 , θ 1 ) are solutions for the duality (2.11)

then (θ, Φ, u) := (θ 1 - θ 0 , Φ, u) is a solution to the OMK equation (P λ ). Moreover θ + = θ 1 , θ -= θ 0 if λ > 0. (ii) Conversely, if (θ, Φ, u
) is a solution to the OMK equation (P λ ) then u and (Φ, θ 0 , θ 1 ) := (Φ, θ -, θ + ) are solutions for the duality (2.11).

Proof. (i) Let u ∈ L λ d F and (Φ, θ 0 , θ 1 ) ∈ S be solutions for the duality (2.11). Then (θ, Φ, u) := (θ 1θ 0 , Φ, u) is a solution to the OMK equation (P λ ). Indeed, we have

θ -∇ • Φ = ν -µ in D ′ (R N )
Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

and ud(ν -µ) = Φ |Φ| ∇ |Φ| ud|Φ|+ udθ 1 -udθ 0 ≤ F (x, Φ |Φ| (x))d|Φ|+λ dθ 1 (by Lemma 2.16).
By the optimality of u and (Φ, θ 0 , θ 1 ), Proposition 2.13 and Lemma 2.16, we have that

Φ |Φ| (x)∇ |Φ| u(x) = F (x, Φ |Φ| (x)) |Φ|-a.e.
x, u = 0 θ 0 -a.e. and u = λ θ 1 -a.e..

By the Hahn-Jordan decomposition, we get θ -≤ θ 0 , θ + ≤ θ 1 and thus u = 0 θ --a.e. and u = λ θ + -a.e.. Therefore (θ, Φ, u) is a solution to the OMK equation (P λ ). It remains to verify that θ -= θ 0 and θ + = θ 1 in the case λ > 0. Since λ > 0, we deduce that θ 0 and θ 1 are concentrated on two disjoint sets. Thus θ + = θ 1 and θ -= θ 0 by virtue of the Hahn-Jordan decomposition.

(ii) Conversely, let (θ, Φ, u) be a solution to the OMK equation (P λ ). We see that

R N ud(ν -µ) = R N Φ |Φ| ∇ |Φ| ud|Φ|+ R N udθ = R N F (x, Φ |Φ| (x))d|Φ|+ R N λdθ + .
The optimality of u and (Φ, θ -, θ + ) follows immediately from the duality (2.11).

We have the following estimates for solution θ of the OMK equation.

Proposition 2.18 (Estimate for the component θ). Assume that µ, ν ∈ M + b (R N ) and λ ≥ 0. Let (θ, Φ, u) be a solution to the OMK equation (P λ ). Then

θ -≤ µ -µ ∧ ν ≤ µ and θ + ≤ ν -µ ∧ ν ≤ ν. Proof. Case 1: If λ = 0, then u ≡ 0, Φ ≡ 0 and θ ≡ ν -µ = ν -µ ∧ ν -(µ -µ ∧ ν).
By the Hahn-Jordan decomposition, we get that θ + ≤ ν -µ∧ν and θ -≤ µ-µ∧ν.

Optimal Partial Transport and Constrained Matching Problems

OMK equation

Case 2: Let us now assume that λ > 0. For 0 < ε < λ, we consider the Lipschitz continuous functions of one variable

T 1 ε (r) :=          0 if r ≤ λ -ε r -(λ -ε) ε if λ -ε ≤ r ≤ λ 1 if r ≥ λ ∀r ∈ R. For ξ ∈ C ∞ c (R N ) such that ξ ≥ 0, we take T 1 ε (u)ξ as a test function in the equation θ -∇ • Φ = ν -µ. We get T 1 ε (u)ξdθ + Φ |Φ| • ∇ |Φ| T 1 ε (u)ξ d|Φ|= T 1 ε (u)ξd(ν -µ). (2.18)
Thanks to the chain rule given in Proposition 1.5, we get

Φ |Φ| • ∇ |Φ| T 1 ε (u)ξ d|Φ| = (T 1 ε ) ′ (u)∇ |Φ| u • Φ |Φ| ξd|Φ|+ Φ |Φ| • ∇ξT 1 ε (u)d|Φ| ≥ Φ |Φ| • ∇ξT 1 ε (u)d|Φ|. (2.19)
Using (2.18) and (2. [START_REF] Bernard | Optimal mass transportation and Mather theory[END_REF]), we see that

T 1 ε (u)ξ dθ + Φ |Φ| • ∇ξT 1 ε (u) d|Φ| ≤ T 1 ε (u)ξ d(ν -µ) = T 1 ε (u)ξ d(ν -µ ∧ ν -(µ -µ ∧ ν)) ≤ T 1 ε (u)ξ d(ν -µ ∧ ν).
(2.20)

Since u ≤ λ, for any x ∈ R N , we have

T 1 ε (u)(x) → χ [u=λ] (x) as ε → 0.
Now, using Proposition 1.5 (ii), the nondegeneracy of F and the definition of solution for (P λ ), we have

|Φ|([u = λ]) = 0. Consequently, Φ |Φ| • ∇ξT 1 ε (u)d|Φ|→ 0 as ε → 0.
Letting ε → 0 in (2.20), we get Using the definition of solution for (P λ ), we have u = 0 for θ --a.e.. Since λ > 0, we obtain

[u=λ] ξdθ ≤ [u=λ] ξd(ν -µ ∧ ν) for any ξ ∈ C ∞ c (R N ), ξ ≥ 0.
[u=λ] ξdθ + = [u=λ] ξdθ ≤ [u=λ] ξd(ν -µ ∧ ν) for any ξ ∈ C ∞ c (R N ), ξ ≥ 0. This implies that θ + ≤ ν -µ ∧ ν on [u = λ] and that θ + ≤ ν -µ ∧ ν (since θ + is concentrated on [u = λ]). At last, using T 2 ε (u)ξ as a test function in the equation θ -∇ • Φ = ν -µ,
where

T 2 ε (r) :=          -1 if r ≤ 0 -1 + r ε if 0 ≤ r ≤ ε 0 if r ≥ ε ∀r ∈ R,
we can prove in much the same way that θ -≤ µµ ∧ ν.

Proof of Theorem 2.3. The proof follows from Propositions 2.13, 2.17 and 2.18.

As a consequence of Proposition 2.13, we have the duality result for λ = +∞.

Corollary 2.19. Let µ, ν ∈ M + b (R N ) be such that ν(R N ) ≤ µ(R N ). We have sup R N ud(ν -µ) : u is 1-d F Lispchitz, u ≥ 0 = min (Φ,θ 0 )∈M b (R N ) N ×M + b (R N ) R N F (x, Φ |Φ| (x))d|Φ|: -∇ • Φ = ν -(µ -θ 0 ) . Proof. Using the assumption ν(R N ) ≤ µ(R N ), there exists ( Φ, θ0 ) ∈ M b (R N ) N × M + b (R N ) such that -∇ • Φ = ν -(µ -θ0 ). This implies that inf (Φ,θ 0 )∈M b (R N ) N ×M + b (R N ) R N F (x, Φ |Φ| (x))d|Φ|: -∇•Φ = ν-(µ-θ 0 ) := C < +∞. Now, taking u as a test function in the equation -∇ • Φ = ν -(µ -θ 0 ), we get R N ud(ν -µ) = R N Φ |Φ| ∇ |Φ| ud|Φ|- R N udθ 0 ≤ R N F (x, Φ |Φ| (x))d|Φ|.
Optimal Partial Transport and Constrained Matching Problems

2.4. OMK equation Hence, sup R N ud(ν -µ) : u is 1-d F Lispchitz, u ≥ 0 ≤ inf (Φ,θ 0 )∈M b (R N ) N ×M + b (R N ) R N F (x, Φ |Φ| (x))d|Φ|: -∇ • Φ = ν -(µ -θ 0 ) = C.
(2.21)

Conversely, let us consider a sequence λ n → +∞ as n → +∞. Thanks to Proposition 2.13, there exist

u n ∈ L λn d F and (Φ n , θ 0 n , θ 1 n ) ∈ S such that R N F (x, Φ n |Φ n | (x))d|Φ n |+λ n R N dθ 1 n = R N u n d(ν -µ) ≤ C. (2.22) It is not difficult to see that {(Φ n , θ 0 n , θ 1 n )} is bounded in M b (R N ) N × M b (R N ) × M b (R N ). Thus, up to a subsequence, (Φ n , θ 0 n , θ 1 n ) converges to some (Φ, θ 0 , θ 1 ) weakly* in M b (R N ) N × M b (R N ) × M b (R N ). It is clear that θ 1 = 0, θ 0 ≥ 0 and -∇ • Φ = ν -(µ -θ 0 ). Now,
R N F (x, Φ |Φ| (x))d|Φ| ≤ lim n→+∞ R N F (x, Φ n |Φ n | (x))d|Φ n | ≤ sup R N ud(ν -µ) : u is 1-d F Lispchitz, u ≥ 0 .
The proof is completed by combining this with (2.21).

Uniqueness of solution θ to the OMK equation

In this subsection, we focus on the uniqueness of solution θ of the OMK equation (P λ ) which is then used to show the uniqueness of active submeasures. The result of uniqueness is somehow optimal in view of Theorem 2.5 and Remark 2.8 (ii). We will give two proofs of the uniqueness. For C 2 Finsler metrics F , an alternative proof will be given in Subsection 2.5.3 basing a combination of PDE and optimal transport theory. We provide right here the proof for general Finsler metric F . Our proof will be based on doubling variables technique due to Kruzkov [START_REF] Kruzkov | First order quasilinear equations in several independent variables[END_REF] (see also [START_REF] Carrillo | Entropy solutions for nonlinear degenerate problems[END_REF] and the references therein). It uses mainly the following result.

, ν ∈ L 1 (R N ) + . Suppose that (θ i , Φ i , u i ), i = 1, 2 are solutions to the same OMK equation (P λ ). Then θ 1 , θ 2 ∈ L 1 (R N ) and, for any ξ ∈ C ∞ c (R N × R N ) such that ξ ≥ 0, we have R N R N (θ 1 (x) -θ 2 (y)) + ξ(x, y)dxdy ≤ R N R N |(∇ x ξ + ∇ y ξ) |d|Φ 1 |(x)dy + R N R N |(∇ x ξ + ∇ y ξ) |d|Φ 2 |(y)dx + R N R N |(ν -µ)(x) -(ν -µ)(y)|ξ(x, y) dxdy.
(2.23)

Before giving the proof of this lemma, let us show how it enables us to prove the main result of uniqueness in section 2.2.

Proof of Theorem 2.4. Fix any α ∈ C ∞ c (R N ), α ≥ 0, let us choose ξ ε (x, y) := ρ ε (x -y)α(x + y)
as test functions in (2.23). Note that ∇ x ξ ε + ∇ y ξ ε = 2ρ ε (xy)∇α(x + y). We have

R N R N |∇ x ξ ε + ∇ y ξ ε |d|Φ 1 |(x)dy = R N R N |∇ x ξ ε + ∇ y ξ ε |dyd|Φ 1 |(x) = 2 R N R N ρ ε (x -y)|∇α(x + y)| dyd|Φ 1 |(x) = 2 R N R N ρ ε (t)|∇α(2x -t)| dtd|Φ 1 |(x) → 2 R N |∇α(2x)|d|Φ 1 |(x).
Similarly,

R N R N |∇ x ξ ε + ∇ y ξ ε |d|Φ 2 |(y)dx → 2 R N |∇α(2y)|d|Φ 2 |(y). Next, since f := ν -µ ∈ L 1 , we have R N R N |f (x) -f (y)|ξ ε (x, y) dxdy = R N R N |f (x) -f (y)|ρ ε (x -y)α(x + y) dxdy
Optimal Partial Transport and Constrained Matching Problems

2.4. OMK equation ≤ α ∞ R N R N |f (x) -f (y)|ρ ε (x -y) dydx = α ∞ R N R N |f (x) -f (x -t)|ρ ε (t) dtdx = α ∞ R N F ε (x)dx → 0, by the fact that F ε (x) := R N |f (x) -f (x -t)|ρ ε (t) dt, F ε → 0 in L 1 . Thus (2.23) leads to R N (θ 1 (x) -θ 2 (x)) + α(2x)dx ≤ 2 R N |∇α(2x)|d|Φ 1 |(x) + 2 R N |∇α(2y)|d|Φ 2 |(y). (2.24) Take a sequence α n ∈ C ∞ c (R N ) such that χ B(0,n) ≤ α n ≤ χ B(0,n+1
) and |∇α n |≤ C. By substituting α n into (2.24) and letting n → +∞, using the finiteness of Φ i , we get Proof of Lemma 2.20. Thanks to Proposition 2.18, we have θ 1 , θ 2 ∈ L 1 (R N ). Now, let us consider the test functions

R N (θ 1 (x) -θ 2 (x)) + dx ≤ 0. Hence θ 1 ≤ θ 2 . Since
ξ ε (x, y) := H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y) where ξ ∈ C ∞ c (R N × R N ), ξ ≥ 0, ρ ∈ C ∞ (R N × R N ) and 0 ≤ ρ ≤ 1.
For each y, considering ξ ε (., y) as a test function, we have

R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)θ 1 (x) dx + R N Φ 1 |Φ 1 | (x).∇ |Φ 1 |,x (H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)) d|Φ 1 |(x) = R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y) (ν -µ)(x)dx.
Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

Integrating with respect to y, we get

R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)θ 1 (x) dxdy + R N R N Φ 1 |Φ 1 | (x).∇ |Φ 1 |,x (H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)) d|Φ 1 |(x)dy = R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y) (ν -µ)(x)dxdy.
(2.25)

Similarly, applying for (θ 2 , Φ 2 , u 2 ), we get

R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)θ 2 (y) dydx + R N R N Φ 2 |Φ 2 | (y).∇ |Φ 2 |,y (H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)) d|Φ 2 |(y)dx = R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y) (ν -µ)(y)dydx.
(2.26)

From (2.25) and (2.26), we have

I 1 (ε) + I 2 (ε) + I 3 (ε) = 0, (2.27)
where

I 1 (ε) := R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)(θ 1 (x) -θ 2 (y)) dxdy - R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y) (ν -µ)(x)dxdy + R N R N H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y) (ν -µ)(y)dxdy; I 2 (ε) := R N R N Φ 1 |Φ 1 | (x).∇ |Φ 1 |,x (H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)) d|Φ 1 |(x)dy
and

I 3 (ε) := - R N R N Φ 2 |Φ 2 | (y).∇ |Φ 2 |,y (H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)) d|Φ 2 |(y)dx.

OMK equation

Recall that

R N ∇g(x)dx = 0 for any g ∈ Lip(R N ) ∩ C c (R N ).
(2.28)

For short, in the following computation, we denote by

H ε := H ε (u 1 (x) -u 2 (y) + ερ(x, y)) and H ′ ε := H ′ ε (u 1 (x) -u 2 (y) + ερ(x, y))
. By the chain rule, we have

I 2 (ε) = R N R N Φ 1 |Φ 1 | (x) ∇ x ξH ε + ∇ |Φ1| u 1 H ′ ε ξ + ε∇ x ρH ′ ε ξ d|Φ 1 |(x)dy = R N R N Φ 1 |Φ 1 | (x) (∇ x ξ + ∇ y ξ)H ε + (∇ |Φ1| u 1 -∇u 2 )H ′ ε ξ + ε(∇ x ρ + ∇ y ρ)H ′ ε ξ d|Φ 1 |(x)dy ≥ R N R N Φ 1 |Φ 1 | (x) (∇ x ξ + ∇ y ξ) H ε d|Φ 1 |(x)dy + ε R N R N Φ 1 |Φ 1 | (x)(∇ x ρ + ∇ y ρ)H ′ ε ξd|Φ 1 |(x)dy, (2.29)
where, in the second equality, we used (2.28) and the fact that

ξ ∈ C ∞ c (R N × R N ): R N R N Φ 1 |Φ 1 | (x) ∇ y ξH ε -∇u 2 (y)H ′ ε ξ + ε∇ y ρH ′ ε ξ d|Φ 1 |(x)dy = R N Φ 1 |Φ 1 | (x) R N ∇ y (H ε (u 1 (x) -u 2 (y) + ερ(x, y))ξ(x, y)) dyd|Φ 1 |(x) = 0.
On the other hand, ε

R N R N Φ 1 |Φ 1 | (x)(∇ x ρ + ∇ y ρ)H ′ ε (u 1 (x) -u 2 (y) + ερ(x, y))ξd|Φ 1 |(x)dy = R N R N Φ 1 |Φ 1 | (x)(∇ x ρ + ∇ y ρ)χ [-ερ≤u 1 (x)-u 2 (y)≤ε(1-ρ)] ξd|Φ 1 |(x)dy → 0.
(2.30) Indeed, since Φ 1 gives no mass on the set [u 1 = u 2 (y)] for each y (using Proposition 1.5 (ii), the nondegeneracy of F and the definition of solution for (P λ )),

F ε (y) := R N Φ 1 |Φ 1 | (x)(∇ x ρ + ∇ y ρ)χ [-ερ≤u 1 (x)-u 2 (y)≤ε(1-ρ)] ξd|Φ 1 |(x) → R N Φ 1 |Φ 1 | (x)(∇ x ρ + ∇ y ρ)χ [u 1 (x)=u 2 (y)] ξd|Φ 1 |(x) = 0; 50
|F ε (y)|≤ R N |(∇ x ρ + ∇ y ρ)|ξd|Φ 1 |(x) ∈ L 1 (R N ).
Using the Lebesgue Dominated Convergence Theorem, we get (2.30). Next, from (2.29) and (2.30), we obtain

lim inf ε I 2 ≥ - R N R N |(∇ x ξ + ∇ y ξ) |d|Φ 1 |(x)dy.
(2.31)

In the same way, we have lim inf

ε I 3 ≥ - R N R N |(∇ x ξ + ∇ y ξ) |d|Φ 2 |(y)dx.
(2.32)

Concerning I 1 (ε), we have the convergence in pointwise (x, y),

H ε (u 1 (x) -u 2 (y) + ερ(x, y)) → Sign + 0 (u 1 (x) -u 2 (y)) + ρ(x, y)χ [u 1 (x)=u 2 (y)] ,
where

Sign + 0 (r) =    1 if r > 0 0 if r ≤ 0.
Since νµ ∈ L 1 , then

I 1 (ε) → R N R N (θ 1 (x) -θ 2 (y)) Sign + 0 (u 1 (x) -u 2 (y)) + ρ(x, y)χ [u 1 (x)=u 2 (y)] ξ dxdy - R N R N ((ν -µ)(x) -(ν -µ)(y)) Sign + 0 (u 1 (x) -u 2 (y)) + ρ(x, y)χ [u 1 (x)=u 2 (y)] ξ dxdy ≥ R N R N (θ 1 (x) -θ 2 (y)) Sign + 0 (u 1 (x) -u 2 (y)) + ρ(x, y)χ [u 1 (x)=u 2 (y)] ξ dxdy - R N R N |(ν -µ)(x) -(ν -µ)(y)|ξ(x, y) dxdy,
where we used the assumption 0 ≤ ρ(x, y) ≤ 1 and therefore

Sign + 0 (u 1 (x) -u 2 (y)) + ρ(x, y)χ [u 1 (x)=u 2 (y)] ≤ 1.

OMK equation vs active submeasures

Now, by density, we can choose ρ(x, y) := Sign + 0 (θ 1 (x)θ 2 (y)), so that

lim inf ε I 1 (ε) ≥ R N R N (θ 1 (x)-θ 2 (y)) + ξ - R N R N |(ν -µ)(x)-(ν -µ)(y)|ξ(x, y) dxdy.
Combining this with (2.27), (2.31) and (2.32), we obtain Lemma 2.20.

OMK equation vs active submeasures 2.5.1 Partial minimum flow problem

Recall that in the connection between balanced MK problem and the Monge-Kantorovich equation the so called minimal flow problem is a key ingredient. For the PMK problem, the definition of minimal flow problem, that we call here the partial minimal flow problem as well as its connection with (PMK) are given in the following proposition.

∈ π m (µ, ν)} = max D(λ, u) : (λ, u) ∈ R + × L λ d F = min    R N F x, Φ |Φ| (x) d|Φ|(x) : (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν)    , (2.33)
where

Ψ m (µ, ν) := (Φ, θ 0 , θ 1 ) ∈ M b (R N ) N × M + b (R N ) × M + b (R N ) : θ 0 (R N ) = µ(R N ) -m, θ 1 (R N ) = ν(R N ) -m and -∇ • Φ = ν -θ 1 -(µ -θ 0 ) in D ′ (R N ) .
The last minimization problem in (2.33) is called the partial minimal flow (PMF) problem. It actually introduces the Beckmann problem (see [START_REF] Beckmann | A continuous model of transportation[END_REF] or Chapter 1) for (PMK) with Finsler distance costs. See here that in the balanced case, i.e.,

m = µ(R N ) = ν(R N ), the PMF problem becomes min R N F (x, Φ |Φ| (x))d|Φ| : Φ ∈ M b (R N ) N , -∇ • Φ = ν -µ in D ′ (R N ) ,
which is a generalization of (1.6) to the case of Finsler distances.

52

Optimal Partial Transport and Constrained Matching Problems If (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν) is an optimal solution to the PMF problem and θ 0 ≤ µ, θ 1 ≤ ν then ρ 0 := µθ 0 and ρ 1 := νθ 1 are active submeasures of the PMK problem. Conversely, if ρ 0 and ρ 1 are active submeasures to the PMK problem then there exists a vector measure Φ such that (Φ, θ 0 , θ 1 ) := (Φ, µρ 0 , νρ 1 ) is a solution to the PMF problem.

Note that we do not have any constraints of type θ 0 ≤ µ or θ 1 ≤ ν in the definition of the PMF problem. However, following Theorem 2.23 below and Proposition 2.18, these constraints are automatically satisfied for any optimal solutions (Φ,

θ 0 , θ 1 ) whenever m ∈ [(µ ∧ ν)(R N ), m max ]. The case m < (µ ∧ ν)(R N )
is not interesting for (PMK) because of the obviousness of solutions.

Proof of Proposition 2.21. The first equality has been shown in Theorem 2.1. Let us prove the second equality. First, for any (λ, u) ∈ R + × L λ d F and a triplet (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν), using Lemma 2.16, we have

R N ud(ν -µ) + λ(m -ν(R N )) = R N ud(ν -µ) -λ R N dθ 1 ≤ R N ud(ν -µ) + R N udθ 0 - R N udθ 1 = R N ∇ |Φ| u(x) Φ |Φ| (x)d|Φ|≤ R N F (x, Φ |Φ| (x))d|Φ|.
This shows that max

(λ,u)∈R + ×L λ d F D(λ, u) ≤ inf F x, Φ |Φ| (x) d|Φ|(x) : (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν) .
Now, let (ρ 0 , ρ 1 ) be a couple of active submeasures for (PMK) w.r.t. m. By Corollary 2.19, there exists

Φ ∈ M b (R N ) N such that -∇ • Φ = ρ 1 -ρ 0 and R N F (x, Φ |Φ| (x))d|Φ| = sup R N ud(ρ 1 -ρ 0 ) : u is 1-d F Lipschitz, u ≥ 0 = min {K(σ) : σ ∈ π m (ρ 0 , ρ 1 )} .
Let us set θ 0 := µρ 0 and θ 1 := νρ 1 .

Optimal Partial Transport and Constrained Matching Problems 53

OMK equation vs active submeasures

Then (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν) and

F (x, Φ |Φ| (x))d|Φ|= min {K(σ) : σ ∈ π m (ρ 0 , ρ 1 )} = max D(λ, u) : (λ, u) ∈ R + × L λ d F .

Link between the OMK equation and the PMK problem

The connection between the OMK equation and (PMK) appears when we deal with the extremal condition between the PMF problem and DPMK problem. Roughly speaking, the optimality condition in the duality of the DPMK and PMF problems corresponds to (P λ ) for some λ.

Theorem 2.23. Let µ, ν ∈ M + b (R N ) be compactly supported. (i) Given m ∈ [0, m max ] and a solution (Φ, θ 0 , θ 1 ) to the PMF problem and (λ, u) is a solution to the DPMK problem. Setting θ := θ 1θ 0 , the triplet (θ, Φ, u) is a solution to the OMK equation (P λ ). Moreover,

θ + = θ 1 and θ -= θ 0 if m ≥ (µ ∧ ν)(R N ).
(ii) Given λ ≥ 0 and (θ, Φ, u) a solution to the OMK equation (P λ ). Then (λ, u) is a solution to the DPMK problem corresponding to m = (µθ -)(R N ) and (Φ, θ 0 , θ 1 ) := (Φ, θ -, θ + ) is a solution to the associated PMF problem.

Proof. (i) From the optimality of (Φ, θ 0 , θ 1 ) and of (λ, u), using Proposition 2.21, we have

R N ud(ν -µ) + λ(m -ν(R N )) = R N F (x, Φ |Φ| (x))d|Φ|, or R N ud(ν -µ) = R N F (x, Φ |Φ| (x))d|Φ|+λ R N dθ 1 .
Thanks to Proposition 2.13, we have that u and (Φ, θ 0 , θ 1 ) are solutions for the duality (2.11). Using Proposition 2.17, we have that (θ, Φ, u) is a solution to the OMK equation (P λ ). Now, let us show that θ + = θ 1 and θ -= θ 0 for the case m ≥ (µ ∧ ν)(R N ). We divide into two cases: If m = (µ ∧ ν)(R N ), then the total cost of the associated optimal partial transport problem is zero. This implies that Φ ≡ 0 and

θ := θ 1 -θ 0 = ν -µ = ν -µ ∧ ν -(µ -µ ∧ ν)
. By the Hahn-Jordan decomposition, we have Using the constraints on the total mass of θ 0 and of θ 1 , we obtain

θ + = ν -µ ∧ ν ≤ θ 1 and θ -= µ -µ ∧ ν ≤ θ 0 . 54
θ + = ν -µ ∧ ν = θ 1 and θ -= µ -µ ∧ ν = θ 0 .
If m > (µ ∧ ν)(R N ) then λ > 0 and the conclusion follows from Proposition 2.17.

(ii) The proof is similar to the one of Proposition 2.17 (ii) with the use of the duality (2.33).

We are now ready to give the proof of the connection between active submeasures and solutions θ of the OMK equation.

Proof of Theorem 2.5. First, let θ λ be a solution of the OMK equation (P λ ). Thanks to Proposition 2.18, 0 ≤ µθ - λ ≤ µ and 0 ≤ νθ + λ ≤ ν. Then, using Theorem 2.23 (ii) and Corollary 2.22, we deduce that ρ 0 := µθ - λ and ρ 1 := νθ + λ are active submeasures. Conversely, let m ∈ [(µ ∧ ν)(R N ), m max ] and (ρ 0 , ρ 1 ) be a couple of active submeasures. Let (λ m , u m ) be a solution of the DPMK problem. Thanks to Corollary 2.22, there exists a flow Φ such that (Φ, µρ 0 , νρ 1 ) is a solution of the corresponding PMF problem. And, thanks to Theorem 2.23 (i), θ λm := νρ 1µ + ρ 0 is a solution of the OMK equation (P λm ) and

θ + λm = ν -ρ 1 , θ - λm = µ -ρ 0 .
Thanks to the above connection, let us give the proof of the uniqueness of active submeasures by using the result of the OMK equation.

Proof of Corollary 2.6. Assume that (ρ 0 , ρ 1 ) and (η 0 , η 1 ) ∈ Sub m (µ, ν) are two pairs of active submeasures. We will show that ρ 0 = η 0 and ρ 1 = η 1 . Let λ m ≥ 0 be fixed such that

λ m ∈ argmax λ≥0 max u D(λ, u) : u ∈ L λ d F .
Let θ 1 , θ 2 be Lebesgue functions with negative and positive parts defined by

θ + 1 = ν -ρ 1 , θ - 1 = µ -ρ 0 , and θ + 2 = ν -η 1 , θ - 2 = µ -η 0 .
Thanks to Theorem 2.5, θ 1 and θ 2 are solutions to the same OMK equation (P λm ). So, using the uniqueness in Theorem 2.4, we deduce that θ 1 = θ 2 and that θ -

1 = θ - 2 , θ + 1 = θ + 2 .
This implies that ρ 0 = η 0 and ρ 1 = η 1 .

Alternative proof of the uniqueness for regular

Finsler metrics

We provide here an alternative proof for the case where Finsler metric is regular in the sense that

• the function (x, v) → F (x, v
) is C 2 outside of the zero section (i.e., {(x, 0)});

• for each x ∈ R N , the function v → F (x, v) 2 has positive definite Hessian at all vector v = 0.

In this case, we make use of the special property on the Lebesgue negligibility of the endpoints of maximal transport rays (see e.g. [START_REF] Bernard | The Monge problem for supercritical Mané potentials on compact manifolds[END_REF]Corollary 15] for Finsler metrics or [1, Corollary 6.1], [5, Theorem 6.2] for the Euclidean metric).

It is not difficult to see that the common mass µ∧ν must be contained in active submeasures. So, without losing generality, we assume that µ and ν are disjoint, i.e., µ ∧ ν = 0. Lemma 2.24. Let (θ, Φ, u) satisfy the OMK equation (P λ ). Then

• µ [u=λ] = ν [u=0] = 0; • L N (supp(Φ) ∩ [u = λ]) = L N (supp(Φ) ∩ [u = 0]) = 0.
Proof. • Let γ be an optimal plan which sends µ [u=λ] to some ν 1 ≤ ν. Thanks to [90, Theorem 5.9], u is also a Kantorovich potential of the optimal transport problem restricted on µ [u=λ] to ν 1 . Using the fact u ≤ λ, we get 0 ≤ min

σ∈π(µ [u=λ] ,ν 1 ) d F (x, y) dσ = u d(ν 1 -µ [u=λ] ) ≤ 0.
Since µ and ν are disjoint, we obtain µ [u=λ] = 0. In much the same way, we also have ν [u=0] = 0.

• We will prove that (2.35)

L N (supp(Φ) ∩ [u = λ]) = 0. ( 2
Since z / ∈ E, we can assume moreover that z = y. From (2.35), we get u(y) > λ, a contradiction.

Alternative proof of Corollary 2.6. Assume that λ > 0. If not, there is nothing to prove. The first equation in the OMK equation implies that

ν -θ + -(µ -θ -) is concentrated on supp(Φ).
(2.36)

Since u = 0 θ --a.e. and the fact that λ > 0, we get θ - [u=λ] = 0. Thanks to Lemma 2.24, (µθ -) [u=λ] = 0.

Combining this with (2.36), the measure (ν . Since the Kantorovich potential u is independent of active submeasures, we get the uniqueness of θ.

-θ + ) [u=λ] is concentrated on supp(Φ) ∩ [u = λ] so that (ν -θ + ) [u=λ] = 0,

Monotonicity

To study the maps m and R defined in section 2.2, we study the monotone and continuous dependence of the solution θ λ of the OMK equation (P λ ) on the parameter λ.

Proposition 2.25 (Monotonicity and continuity of θ λ ). Let µ, ν ∈ M + b (R N ) be compactly supported and absolutely continuous. Suppose that (θ λ , Φ λ , u λ ) is a solution to the OMK equation (P λ ).

(i) Let 0 ≤ λ 1 ≤ λ 2 and θ λ 1 , θ λ 2 be solutions to the OMK equations (P λ 1 ) and (P λ 2 ), respectively. Then

θ + λ 1 ≥ θ + λ 2 and θ - λ 1 ≥ θ - λ 2 .
(ii) If a nonnegative sequence λ n → λ then θ λn → θ λ strongly in L 1 (R N ).

Optimal Partial Transport and Constrained Matching Problems 57 2.6. Monotonicity Lemma 2.26 (Monotonicity of total mass). For any λ ≥ 0, let θ λ be the solution of the OMK equation (P λ ) and

m λ := (µ -θ - λ )(R N ) = (ν -θ + λ )(R N ). If 0 ≤ λ 1 ≤ λ 2 then (µ ∧ ν)(R N ) ≤ m λ 1 ≤ m λ 2 ≤ m max .
Proof. Thanks to Proposition 2.18, we see that µ ∧ ν ≤ µθ - λ and therefore

(µ ∧ ν)(R N ) ≤ m λ . Since µ -θ - λ ≤ µ and ν -θ + λ ≤ ν, we have m λ ≤ m max .
For the monotonicity, due to Theorem 2.23, (λ 1 , u λ 1 ) and (λ 2 , u λ 2 ) are solutions to the DPMK problem w.r.t. m λ 1 and m λ 2 . By optimality, we have

u λ 1 d(ν -µ) + λ 1 (m λ 1 -ν(R N )) ≥ u λ 2 d(ν -µ) + λ 2 (m λ 1 -ν(R N ))
and

u λ 2 d(ν -µ) + λ 2 (m λ 2 -ν(R N )) ≥ u λ 1 d(ν -µ) + λ 1 (m λ 2 -ν(R N )).
Adding both sides, we obtain

λ 1 m λ 1 + λ 2 m λ 2 ≥ λ 2 m λ 1 + λ 1 m λ 2 , or (λ 2 -λ 1 )(m λ 2 -m λ 1 ) ≥ 0.
In order to prove Proposition 2.25, we use the following result whose proof is given in [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF] for general costs.

m i := m λ i ≥ (µ∧ν)(R N ), i = 1, 2. Since λ 1 ≤ λ 2
and Lemma 2.26, we have m 1 ≤ m 2 . Thanks to Theorem 2.27, there exist pairs of active submeasures (ρ λ i 0 , ρ λ i 1 ) corresponding to m i , i = 1, 2 such that

ρ λ 1 0 ≤ ρ λ 2 0 and ρ λ 1 1 ≤ ρ λ 2 1 .
(2.37) By Theorem 2.23 (ii), (λ 1 , u λ 1 ) is a solution to the DPMK with mass m 1 . Setting θ := νρ λ 1 1µ + ρ λ 1 0 . By Theorem 2.23 (i), there is Φ such that (θ, Φ, u λ 1 ) is a solution to the OMK equation (P λ 1 ). By the uniqueness in Theorem 2.4, we get Following the proof of Theorem 2.5, we obtain

θ λ 1 ≡ θ = ν -ρ λ 1 1 -µ + ρ λ 1 0 . 58
θ - λ 1 = µ -ρ λ 1 0 and θ + λ 1 = ν -ρ λ 1 1 .
In the same way, we have

θ - λ 2 = µ -ρ λ 2 0 and θ + λ 2 = ν -ρ λ 2 1 .
Combining these with (2.37), we get θ - [START_REF] Bernard | The Monge problem for supercritical Mané potentials on compact manifolds[END_REF], we have that |θ λn |≤ µ + ν ∈ L 1 and therefore {θ λn } is equi-integrable. By the Dunford-Pettis theorem, up to a subsequence, θ λn converges weakly to some θ ∈ L 1 (R N ). Now, let us show that θ is a solution of the OMK equation (P λ ). Once this is done, by the uniqueness in Theorem 2.4, we deduce that θ ≡ θ λ and thus the whole sequence θ λn → θ λ weakly in L 1 (R N ). By the nondegeneracy of F and the definition of solution for the OMK equation (P λn ), it is clear that {u λn } is bounded and equi-Lipschitz; and that

λ 1 ≥ θ - λ 2 and θ + λ 1 ≥ θ + λ 2 . (ii) Since θ - λn ≤ µ, θ + λn ≤ ν as in Proposition 2.
{Φ λn } is bounded in M b (R N ) N . So, up to subsequence, u λn → u uniformly on each compact subset of R N and Φ λn → Φ weakly* in M b (R N ) N .
Let us show that (θ, Φ, u) is a solution to the OMK equation (P λ ). First, it is clear

that u ∈ L λ d F , u dθ -= lim λn→λ u λn dθ - λn = 0 and (u -λ) dθ + = lim λn→λ (u λn -λ n ) dθ + λn = 0.
Moreover,

ξ dθ+ Φ |Φ| ∇ξ d|Φ|= lim λn→λ ξ dθ λn + Φ λn |Φ λn | ∇ξ d|Φ λn |= ξd(ν-µ) ∀ξ ∈ C ∞ c (R N ), which means that θ -∇ • Φ = ν -µ in D ′ (R N ). It remains to check that Φ |Φ| (x)∇ |Φ| u(x) = F (x, Φ |Φ| (x)) |Φ|-a.e. x in
R N F (x, Φ |Φ| (x))d|Φ|≤ lim inf λn→λ R N F (x, Φ λn |Φ λn | (x))d|Φ λn |. (2.39)
On the other hand,

lim λn→λ R N F (x, Φ λn |Φ λn | (x))d|Φ λn | = lim λn→λ Φ λn |Φ λn | ∇ |Φ λn | u λn d|Φ λn | = lim λn→λ u λn d(ν -µ) + u λn dθ λn = u d(ν -µ) + u dθ = Φ |Φ| (x)∇ |Φ| u(x)d|Φ|.
(2.40)

From (2.39) and (2.40), we deduce (2.38). We have just proved that θ λn → θ λ weakly in L 1 (R N ). At last, by the monotonicity of the first part, we deduce the strong convergence in L 1 (R N ).

Proof of Theorem 2. , 2016] to the optimal transportation with Finsler distances. Our aim here is to show how one can use this method to solve the optimal partial transport problem with Finsler distance costs. A convergence study for the potential together with the flow and the active submeasures is given to validate the approach.

For the purpose of practical implementation, we consider in this part of the thesis the PMK problem with Finsler distance costs on bounded domains. Given a bounded Lipschitz domain Ω ⊂ R N , we are interested in cost functions c = d F with

d F (x, y) := inf ξ∈Lip([0,1];Ω)    1 0 F (ξ(t), ξ(t))dt : ξ(0) = x, ξ(1) = y    ,
where F is a continuous Finsler metric on Ω, i.e., F : Ω × R N -→ [0, +∞) is 3.1. Partial transport and its equivalent formulations continuous and F (x, .) is convex, positively homogeneous of degree 1 in the sense

F (x, tv) = tF (x, v) ∀t > 0, v ∈ R N .
Concerning numerical approximations for the optimal partial transport problem, Barrett & Prigozhin [START_REF] Barrett | Partial L 1 Monge-Kantorovich problem: Variational formulation and numerical approximation[END_REF] studied the case of the Euclidean distance by using an approximation based on nonlinear approximated PDEs and Raviart-Thomas finite elements. Benamou et al. [START_REF] Benamou | Iterative Bregman projections for regularized transportation problems[END_REF] and Chizat et al. [START_REF] Chizat | Scaling algorithms for unbalanced transport problems[END_REF] introduced general numerical frameworks to approximate solutions to linear programs related to the optimal transport. Their idea is based on an entropic regularization of the initial linear programs. This approach needs to use (approximated) values of d F (x, y).

Here, we use a different approach. We first show how one can directly reformulate the unknown quantities (variables) of the optimal partial transport into an infinite-dimensional minimization problem of the form

min φ∈V F(φ) + G(Λφ),
where F, G are l.s.c. convex functionals and Λ ∈ L(V, Z) is a continuous linear operator between two Banach spaces. Thanks to peculiar properties of F and G, an augmented Lagrangian method is effectively used in the same spirit of [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] (see also related works [START_REF] Benamou | Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations[END_REF][START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF][START_REF] Benamou | An augmented Lagrangian approach to Wasserstein gradient flows and applications[END_REF][START_REF] Benamou | Variational mean field games[END_REF]). We just need to solve linear equations or to update explicit formulations. Like the standard optimal transport, it is worth noting that this method uses only elementary operations without evaluating d F .

Partial transport and its equivalent formulations

The equivalent formulations for the PMK problem are presented in the previous chapter with Ω = R N . Here we explain and summarize the results for bounded Lipschitz domains Ω. Although the results remain the same, the technique issues should be mentioned (especially smooth approximation, see Lemmas 3.2 and 3.5, needed in passing rigorously from the Kantorovich-Rubinstein dual formulation to the minimal flow problem).

Assume that F is nondegenerate in the sense that there exist positive constants M 1 , M 2 such that

M 1 |v|≤ F (x, v) ≤ M 2 |v| ∀x ∈ Ω, v ∈ R N .

62

Optimal Partial Transport and Constrained Matching Problems

K(σ * ) = max      D(λ, u) := Ω u d(ν -µ) + λ(m -ν(Ω)) : λ ≥ 0 and u ∈ L λ d F      , (3.1)
where

L λ d F := u ∈ C(Ω) : u(y) -u(x) ≤ d F (x, y), 0 ≤ u(x) ≤ λ for all x, y ∈ Ω . Moreover, σ ∈ π m (µ, ν) and (λ, u) ∈ R + × L λ d F are solutions, respectively, if and only if u(x) = 0 for (µ -π x #σ)-a.e. x ∈ Ω, u(x) = λ for (ν -π y #σ)-a.e. x ∈ Ω and u(y) -u(x) = d F (x, y) for σ-a.e. (x, y) ∈ Ω × Ω.
Proof. The proof follows in the same way of Theorem 2.1.

The DPMK problem (3.1) contains all the informations concerning the optimal partial mass transportation. However, for numerical approximation of the optimal partial transportation and to use the augmented Lagrangian method, we need to rewrite the problem into the form inf φ∈V F(φ) + G(Λφ).

To do that, recall that the polar function F * of F is defined by

F * (x, p) := sup { v, p : F (x, v) ≤ 1} for x ∈ Ω, p ∈ R N .
Note that F * (x, .) is not the Legendre-Fenchel transform. We need the following lemma that gives a smooth approximation of 1-d F Lipschitz continuous function. This result is evident for the Euclidean distance, i.e., Ω is convex and F (x, v) ≡ |v| for x ∈ Ω, v ∈ R N . However, we could not find any rigorous proofs for general Finsler metrics F in the literature. there exists a sequence of functions

u ε ∈ C ∞ c (R N ) such that F * (x, ∇u ε (x)) ≤ 1 ∀x ∈ Ω and u ε ⇒ u uniformly on Ω.
Note that F and F * are defined only in Ω and that the gradient of u is controlled only inside of Ω by (3.2). If we use the standard convolution to define u ε , the value of u ε (x) is affected by the value of u(y) outside of Ω which remains uncontrolled. To overcome this difficulty, if x is near the boundary, we move it a little into inside of Ω before taking the convolution. To do this, we use the smooth partition of unity tool to deal with approximation of u near the boundary.

Proof. Set ∀x ∈ R N , ũ(x) :=    u(x) if x ∈ Ω 0 otherwise.
Step 1: Fix z ∈ ∂Ω. Since Ω is a Lipschitz domain, there exist r z > 0 and a Lipschitz continuous function γ z : R N -1 -→ R such that (up to rotating and relabeling if necessary)

Ω ∩ B(z, r z ) = {x | x N > γ z (x 1 , ..., x N -1 )} ∩ B(z, r z ).
Set U z := Ω ∩ B(z, rz 2 ). For any x ∈ R N , taking

x ε z := x + ελ z e n (3.3)
where we choose a sufficiently large fixed λ z and all small ε, say fixed

λ z ≥ Lip(γ z )+ 1, 0 < ε < r z 2(λ z + 1)
. By this choice and the Lipschitz property of γ z , we see that Step 2: Now, using the compactness of ∂Ω and ∂Ω ⊂ z∈∂Ω B(z, rz 2 ), there exist z 1 , ..., z n ∈ ∂Ω such that

B(x ε z , ε) ⊂ Ω ∩ B(z, r z ) for all x ∈ U z . (3.4) Defining ũε (x) := R N ρ ε (y)ũ(x ε z -y)dy = B(x ε z ,ε) ρ ε (x ε z -y)ũ(
∂Ω ⊂ n i=1 B(z i , r z i 2 ).
For short, we write

r i , U i , x i instead of r z i , U z i , x z i . Taking an open set U 0 ⋐ Ω such that Ω ⊂ n i=1 B(z i , r i 2 ) U 0 .
Let {φ} n i=0 be a smooth partition of unity on Ω, subordinate to

U 0 , B(z 1 , r 1 2 ), ..., B(z n , rn 2 ) , that is,            φ i ∈ C ∞ c (R N ), 0 ≤ φ i ≤ 1 ∀i = 0, ..., n supp(φ i ) ⋐ B(z i , r i 2 ) ∀i = 1, ..., n, supp(φ 0 ) ⋐ U 0 n i=0 φ i (x) = 1 for all x ∈ Ω. Because of Step 1, there exist ũ1 ε , ..., ũn ε ∈ C ∞ c (R N ) such that ũi ε ⇒ u on U i , i = 1, ..., n.
For i = 0, since U 0 ⋐ Ω, we can take ũ0

ε := ρ ε ⋆ ũ ∈ C ∞ c (R N ) and ũ0 ε ⇒ u on U 0 . Set u ε := 1 1 + Cε + w(ε) n i=0 φ i ũi ε ,
where C is to be chosen later and

w(ε) := sup{|F * (x, p) -F * (y, p)|: x, y ∈ Ω, |x -y|≤ M ε, |p|≤ ∇u L ∞ } with constant M := max 1≤i≤n {λ z i +1}, λ z i is given in Step 1.
We show that u ε satisfies all the desired properties. By the construction, u ε ∈ C ∞ c (R N ) and

u ε ⇒ n i=0 φ i u = u on Ω.
Optimal Partial Transport and Constrained Matching Problems

Partial transport and its equivalent formulations

At last, we show that F * (x, ∇u ε (x)) ≤ 1 ∀x ∈ Ω.

For any x ∈ Ω, if x ∈ U i , i = 1, ..., n (near the boundary of Ω), we move x a bit into inside of Ω to x ε i := x ε z i (see (3.3) and (3.4)), if x ∈ U 0 , set x ε 0 = x. We have

∇u ε (x) = 1 1 + Cε + w(ε) n i=0 ∇φ i (x)ũ i ε (x) + n i=0 φ i (x)∇ũ i ε (x) = 1 1 + Cε + w(ε)    n i=0 ∇φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)u(y)dy + n i=0 φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)∇u(y)dy    .
The first sum on the right hand side has a small norm. Indeed, using the fact that n i=0 ∇φ i (x)u(x) = 0 for all x ∈ Ω, we have

n i=0 ∇φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)u(y)dy = n i=0 ∇φ i (x)    B(x ε i ,ε) ρ ε (x ε i -y)u(y)dy -u(x)    . (3.6)
Moreover,

B(x ε i ,ε) ρ ε (x ε i -y)u(u) dy -u(x) ≤ B(x ε i ,ε) ρ ε (x ε i -y) (u(y) -u(x ε i )) dy + |u(x ε i ) -u(x)| ≤ C 1 ε ∀i = 0, ..., n,
where the constant C 1 depends only on Lip(γ z i ) and the Lipschitz constant of u on Ω. Combining this with (3.6) gives

n i=0 ∇φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)u(y)dy ≤ C 2 ε ∀x ∈ Ω,
where C 2 depends only on C 1 and ∇φ i L ∞ .

66

Optimal Partial Transport and Constrained Matching Problems

Chapter 3 : Augmented Lagrangian Method for Optimal Partial Transport By the nondegeneracy of F , we have

F *    x, n i=0 ∇φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)u(y)dy    ≤ C 3 ε for all x ∈ Ω. Fix any x ∈ Ω, if y ∈ B(x ε i , ε) then |x -y|≤ |x -x ε i |+|x ε i -y|≤ M ε. So we obtain F * (x, ∇u ε (x)) ≤ 1 1 + Cε + w(ε) [F * (x, n i=0 ∇φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)u(y)dy) + F * (x, n i=0 φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)∇u(y)dy)] ≤ 1 1 + Cε + w(ε)   C3ε + n i=0 φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)F * (x, ∇u(y))dy    ≤ 1 1 + Cε + w(ε) [C 3 ε + n i=0 φ i (x) B(x ε i ,ε) ρ ε (x ε i -y)F * (y, ∇u(y)) dy + n i=0 φ i (x) B(x ε i ,ε) ρ ε (x ε i -y) (F * (x, ∇u(y)) -F * (y, ∇u(y))) dy] ≤ C 3 ε + 1 + w(ε) 1 + Cε + w(ε) ≤ 1 (choose a constant C ≥ C 3 ).
By the continuity of ∇u ε and of F * , we also have F * (x, ∇u ε (x)) ≤ 1 ∀x ∈ Ω. Proof. Let u be 1-d F Lipschitz. Then u is Lipschitz and u is differentiable a.e. in Ω. Let x ∈ Ω be any point where u is differentiable. We have, for any v ∈ R N ,

∇u(x), v F (x, v) = lim h→0 u(x + hv) -u(x) F (x, hv) ≤ lim sup h→0 d F (x, x + hv) F (x, hv)
Optimal Partial Transport and Constrained Matching Problems Hence, F * (x, ∇u(x)) ≤ 1. Thus u ∈ B F * . Conversely, fix any u ∈ B F * . We divide the argument into two cases. Case 1: If u is smooth then F * (x, ∇u(x)) ≤ 1 ∀x ∈ Ω. For any x, y ∈ Ω and any Lipschitz curve ξ in Ω joining x and y, we have

u(y)-u(x) = 1 0 ∇u(ξ(t)) ξ(t)dt ≤ 1 0 F * (ξ(t), ∇u(ξ(t)))F (ξ(t), ξ(t))dt ≤ 1 0 F (ξ(t), ξ(t))dt.
It follows that u is 1-d F Lipschitz. Case 2: For general Lipschitz continuous function u satisfying F * (x, ∇u(x)) ≤ 1 a.e. x ∈ Ω, thanks to Lemma 3.2, there exist

u ε ∈ B F * C ∞ c (R N ) such that u ε ⇒ u on Ω. According to Case 1 above, u ε is 1-d F Lipschitz and so is u.
As a consequence of Lemmas 3.

K(σ * ) = -inf F(λ, u) + G(Λ(λ, u)) : (λ, u) ∈ V ,
where Λ ∈ L(V, Z) is given by ∞, +∞] are the l.s.c. convex functions given by

Λ(λ, u) := (∇u, -u, u -λ) ∀(λ, u) ∈ V and F : V -→ (-∞, +∞], G : Z -→ (-
F(λ, u) := - Ω u d(ν -µ) -λ(m -ν(Ω)) ∀(λ, u) ∈ V ; 68

Optimal Partial Transport and Constrained Matching Problems

Chapter 3 : Augmented Lagrangian Method for Optimal Partial Transport

G(q, z, w) :=    0 if z(x) ≤ 0, w(x) ≤ 0, F * (x, q(x)) ≤ 1 ∀x ∈ Ω +∞ otherwise for (q, z, w) ∈ Z.
To prove this theorem we need the following lemma.

Lemma 3.5. Let λ ≥ 0 be fixed. For any u ∈ L λ d F , there exists a sequence of smooth functions

u ε ∈ C ∞ c (R N ) L λ d F such that u ε ⇒ u uniformly on Ω. Proof. Since 0 ≤ u ≤ λ, the sequence u ε in the proof of Lemma 3.2 satisfies 0 ≤ u ε ≤ λ. So u ε ∈ C ∞ c (R N ) ∩ L λ d F and u ε ⇒ u on Ω.
Proof of Theorem 3.4. Thanks to Lemmas 3.3 and 3.5, we have

-inf (λ,u)∈V F(λ, u) + G(Λ(λ, u)) = sup    Ω ud(ν -µ) + λ(m -ν(Ω)) : λ ≥ 0, u ∈ C 1 (Ω) ∩ L λ d F    = max D(λ, u) : λ ≥ 0 and u ∈ L λ d F .
Using the duality (3.1), the proof is completed.

To end up this section, by using the Fenchel-Rockafellar duality as in Proposition 2.13, we get the following result that will be useful for the proof of the convergence of our discretization. Theorem 3.6. Under the assumptions of Theorem 3.1, we have

-inf (λ,u)∈V F(λ, u)+G(Λ(λ, u)) = min Ω F (x, Φ |Φ| (x))d|Φ| : (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν) , (3.7
) where

Ψ m (µ, ν) := (Φ, θ 0 , θ 1 ) ∈ M b (Ω) N ×M b (Ω)×M b (Ω) : θ 0 ≥ 0, θ 1 ≥ 0, θ 1 (Ω) = ν(Ω)-m and -∇ • Φ = ν -θ 1 -(µ -θ 0 ) in D ′ (R N ) .

Partial transport and its equivalent formulations

Remark 3.7. The optimality relations for the duality (3.7) reads

                           -∇ • Φ = ν -θ 1 -(µ -θ 0 ) in D ′ (R N ) θ 1 (Ω) = ν(Ω) -m Φ, ∇u ≥ Φ, q ∀q ∈ C(Ω), F * (x, q(x)) ≤ 1 ∀x ∈ Ω λ ∈ R + , u ∈ C 1 (Ω) L λ d F u = 0 θ 0 -a.e. in Ω u = λ θ 1 -a.e. in Ω.
In fact, the optimality condition -Λ * σ ∈ ∂F(φ) gives the first two equations and σ ∈ ∂G(Λφ) gives the last four equations. Moreover, if Φ ∈ L 1 (Ω) N then the condition Φ, ∇u ≥ Φ, q ∀q ∈ C(Ω), F * (x, q(x)) ≤ 1 ∀x ∈ Ω can be replaced by

F (x, Φ(x)) = ∇u(x), Φ(x) for a.e. x ∈ Ω. (3.8)
However, it is not clear in general that Φ belongs to L 1 (Ω) N . In the case where Ω is convex and F (x, v) := |v| the Euclidean norm (or some other uniformly convex and smooth norms), the L p regularity results are known under suitable assumptions on µ and ν (see e.g. [START_REF] Pascale | Integral estimates for transport densities[END_REF][START_REF] Pascale | Regularity properties for Monge transport density and for solutions of some shape optimization problem[END_REF][START_REF] Feldman | Monge's transport problem on a Riemannian manifold[END_REF][START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF]). In the case where Φ is a vector-valued measure, the condition (3.8) should be adapted to the tangential gradient as

Φ |Φ| (x) • ∇ |Φ| u(x) = F x, Φ |Φ| (x)
for |Φ|-a.e. x ∈ Ω.

On the other hand, from the definition of Ψ m (µ, ν), it is expected that Φ is an optimal flow of transporting µθ 0 onto νθ 1 . This requires that θ 0 ≤ µ and θ 1 ≤ ν for optimal solutions (Φ, θ 0 , θ 1 ). These estimates hold whenever m ∈

[(µ ∧ ν)(Ω), m max ]. Proposition 3.8. Let m ∈ [(µ ∧ ν)(Ω), m max ]
and (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν) be optimal. Then θ 0 ≤ µ and θ 1 ≤ ν. Moreover, (µθ 0 , νθ 1 ) is a couple of active submeasures and Φ is an optimal flow of transporting µθ 0 onto νθ 1 .

Proof. The proof follows in the same way as Theorem 2.23 and Proposition 2.18.

Chapter 3 : Augmented Lagrangian Method for Optimal Partial Transport Our next work is to compute an approximation of optimal flow Φ (in fact, approximations of Φ, u, λ, θ 0 , θ 1 ). To do that, we will apply the ALG2 method to the DPMK problem (3.1).

Discretization and convergence

Coming back to the DPMK problem (3.1), our aim now is to give, by using a finite element approximation, the discretized problem associated with (3.1). To begin with, let us consider regular triangulations T h of Ω. For a fixed integer k ≥ 1, P k is the set of polynomials of degree less or equal k. Let E h ⊂ H 1 (Ω) be the space of continuous functions on Ω and belonging to P k on each triangle of T h . We denote by Y h the space of vectorial functions such that their restrictions belong to (P k-1 ) N on each triangle of

T h . Let f = ν -µ and f h ∈ E h such that {f h } converges weakly* to f in M b (Ω).
Considering the finite-dimensional spaces

V h := R × E h , Z h := Y h × E h × E h , we set Λ h (λ, u) := (∇u, -u, u -λ) ∈ Z h for (λ, u) ∈ V h , F h (λ, u) := -u, f h -λ(m -ν(Ω)) ∀(λ, u) ∈ V h and G h (q, z, w) :=    0 if z ≤ 0, w ≤ 0, F * (x, q(x)) ≤ 1 a.e. x ∈ Ω +∞ otherwise for (q, z, w) ∈ Z h .
Then the finite-dimensional approximation of (3.1) reads inf

(λ,u)∈V h F h (λ, u) + G h (Λ h (λ, u)). (3.9)
The following result shows that this is a suitable approximation of (3.1).

Theorem 3.9. Assume that m < ν(Ω). Let (λ h , u h ) ∈ V h be an optimal solution to the approximated problem (3.9) and (Φ h , θ 0 h , θ 1 h ) be an optimal dual solution to (3.9). Then, up to a subsequence, (λ h , u h ) converges in R × C(Ω) to (λ, u) an optimal solution of the DPMK problem (3.1) and

(Φ h , θ 0 h , θ 1 h ) converges weakly* in M b (Ω) N × M b (Ω) × M b (Ω) to (Φ, θ 0 , θ 1 ) ∈ Ψ m (µ, ν) an optimal solution of the PMF problem in (3.7).

Optimal Partial Transport and Constrained Matching Problems

Discretization and convergence

Proof. Since m < ν(Ω), {λ h } is bounded in R and {u h } is bounded in (C(Ω), . ∞ ). From the nondegeneracy of F and the definitions of F h , G h , Λ h , we have that {u h } is equi-Lipschitz and

u h (y) -u h (x) ≤ d F (x, y) ∀x, y ∈ Ω.
Using the Ascoli-Arzela Theorem, up to a subsequence, u h ⇒ u uniformly on Ω and λ h → λ. Obviously, λ ≥ 0 and u ∈ L λ d F . Now, by the optimality of (λ h , u h ) and of (Φ h , θ 0 h , θ 1 h ), we have

-Λ * h (Φ h , θ 0 h , θ 1 h ) = -(m -ν(Ω), f h ) in V * h and F h (λ h , u h ) + G h (Λ h (λ h , u h )) = -F * h (-Λ * h (Φ h , θ 0 h , θ 1 h )) -G * h (Φ h , θ 0 h , θ 1 h ). More concretely, Φ h , ∇v -θ 0 h , v + θ 1 h , v -s = s(m -ν(Ω)) + f h , v ∀(s, v) ∈ V h , (3.10) θ 0 h ≥ 0, θ 1 h ≥ 0, θ 1 h (Ω) = ν(Ω) -m (3.11)
and

u h , f h + λ h (m -ν(Ω)) = sup { q, Φ h : q ∈ Y h , F * (x, q(x)) ≤ 1 a.e.
x ∈ Ω} .

(3.12) In (3.10), taking v = 0 and s = 1 (respectively, v = s = 1), we see that {θ 1 h } (respectively, {θ 0 h }) is bounded in M b (Ω). Moreover, using (3.12) and the boundedness of (λ h , u h ) we deduce that

{Φ h } is bounded in M b (Ω) N . So, up to a subsequence, (Φ h , θ 0 h , θ 1 h ) ⇀ (Φ, θ 0 , θ 1 ) weakly* in M b (Ω) N × M b (Ω) × M b (Ω).
Using (3.10) and (3.11), it is clear that (Φ, θ 0 , θ 1 ) satisfies

Φ, ∇v -θ 0 , v + θ 1 , v -s = s(m -ν(Ω)) + f, v ∀(s, v) ∈ V and θ 0 ≥ 0, θ 1 ≥ 0, θ 1 (Ω) = ν(Ω) -m, F (x, Φ |Φ| (x))d|Φ|= u, ν -µ + λ(m -ν(Ω)). (3.13)
We fix q ∈ C(Ω) N such that F * (x, q(x)) ≤ 1 ∀x ∈ Ω, and we consider q h ∈ Y h such that q hq L ∞ (Ω) → 0 as h → 0. We see that

F * (x, q h (x)) = F * (x, q(x)) + F * (x, q h (x)) -F * (x, q(x)) ≤ 1 + O(h) for a.e. x ∈ Ω.
By taking

q h 1 + O(h)
, we can assume that q h ∈ Y h , F * (x, q h (x)) ≤ 1 for a.e. x ∈ Ω and q hq L ∞ (Ω) → 0 as h → 0. Using (3.12), we have

q, Φ = q h , Φ h + q, Φ -Φ h + q -q h , Φ h ≤ sup { q h , Φ h : q h ∈ Y h , F * (x, q h (x)) ≤ 1, a.e. x ∈ Ω} + O(h) = u h , f h + λ h (m -ν(Ω)) + O(h).
Letting h → 0, we get q, Φ ≤ u, νµ + λ(mν(Ω)) for any q ∈ C(Ω) N , F * (x, q(x)) ≤ 1 ∀x ∈ Ω.

Taking supremum in q, we obtain

Ω F (x, Φ |Φ| (x))d|Φ|≤ u, ν -µ + λ(m -ν(Ω)).
At last, thanks to the duality equality (3.7), this implies (3.13), the optimality of (λ, u) and of (Φ, θ 0 , θ 1 ).

Remark 3.10. In the case m = m max (called the unbalanced transport), the DPMK problem has a simpler formulation. So for the purpose of implementation, we distinguish the two cases: the partial transport and the unbalanced transport.

In the unbalanced case, let us assume that m = m max = ν(Ω) (i.e., µ(Ω) ≥ ν(Ω)), the DPMK problem (3.1) can be written as max

   Ω ud(ν -µ) : u ∈ Lip(Ω), u ≥ 0, F * (x, ∇u(x)) ≤ 1 a.e. x ∈ Ω    . (3.14)
3.3. Solving the discretized problems By using

V h := E h , Z h := Y h × E h , Λ h u := (∇u, -u) and G h (q, z) :=    0 if z ≤ 0, F * (x, q(x)) ≤ 1 for a.e. x ∈ Ω +∞ otherwise,
a finite-dimensional approximation can be given by inf

u∈V h -u, f h + G h (Λ h u). (3.15)
As in Theorem 3.9, we can prove the convergence of this finite dimensional approximation to the original one (3.14). More precisely, we have Proposition 3.11. Assume that m = ν(Ω). Let u h ∈ V h be an optimal solution to the approximated problem (3.15) and (Φ h , θ 0 h ) be an optimal dual solution to (3.15). Then, up to a subsequence and translation by constant, u h converges to u an optimal solution of the DPMK problem (3.14) and (Φ h , θ 0 h ) converges to (Φ, θ 0 ) an optimal solution of the PMF problem in (3.7) with θ 1 = 0.

Solving the discretized problems

Our task now is to solve the finite dimensional problems (3.9) and (3.15). We use the ALG2 method (see Chapter 1) for the discretized problems. To simplify the notations, let us drop out the subscript h in (λ h , u h ) and (Φ h , θ 0 h , θ 1 h ). Thanks to Remark 3.10, we treat separately the case where m = ν(Ω) and the case where m < ν(Ω).

Partial transport (m < ν(Ω))

Given (q i , z i , w i ), (Φ i , θ 0 i , θ 1 i ) at the iteration i, we compute

• Step 1: (λ i+1 , u i+1 ) = argmin (λ,u)∈V h F h (λ, u) + (Φ i , θ 0 i , θ 1 i ), Λ h (λ, u) + r 2 |Λ h (λ, u) -(q i , z i , w i )| 2 = argmin (λ,u)∈V h -u, f h -λ(m -ν(Ω)) + Φ i , ∇u + θ 0 i , -u + θ 1 i , u -λ + r 2 |∇u -q i | 2 + r 2 |u + z i | 2 + r 2 |u -λ -w i | 2 .

74

Optimal Partial Transport and Constrained Matching Problems

(q i+1 , z i+1 , w i+1 ) = argmin (q,z,w)∈Z h G h (q, z, w) -(Φ i , θ 0 i , θ 1 i ), (q, z, w) + r 2 |Λ h (λ i+1 , u i+1 ) -(q, z, w)| 2 = argmin (q,z,w)∈Z h I [F * (.,q(.))≤1] (q) + I [z≤0] (z) + I [w≤0] (w) -Φ i , q -θ 0 i , z -θ 1 i , w + r 2 |∇u i+1 -q| 2 + r 2 |u i+1 + z| 2 + r 2 |u i+1 -λ i+1 -w| 2 .
• Step 3: Update the multiplier

(Φ i+1 , θ 0 i+1 , θ 1 i+1 ) = (Φ i , θ 0 i , θ 1 i ) + r(∇u i+1 -q i+1 , -u i+1 -z i+1 , u i+1 -λ i+1 -w i+1 ).
Before giving numerical results, let us take a while to comment the above iteration. Overall, Step 1 is a quadratic programming. Step 2 can be computed easily in many cases and Step 3 updates obviously.

• In Step 1, we split the computation of the couple (λ i+1 , u i+1 ) into two steps: We first minimize w.r.t. u to compute u i+1 and then we use u i+1 to compute λ i+1 . More precisely, we proceed for Step 1 as follows:

1. For u i+1 ,

u i+1 ∈ argmin u∈E h -u, f h + Φ i , ∇u + θ 0 i , -u + θ 1 i , u + r 2 |∇u -q i | 2 + r 2 |u + z i | 2 + r 2 |u -λ i -w i | 2 .
This is equivalent to

r ∇u i+1 , ∇v + 2r u i+1 , v = f h , v -Φ i , ∇v + θ 0 i , v -θ 1 i , v + r q i , ∇v -r z i , v + r λ i + w i , v ∀v ∈ E h .
Remark here that the equation is linear with a symmetric positive definite coefficient matrix.

For λ i+1 , it is computed explicitly

λ i+1 ∈ argmin s∈R -s(m -ν(Ω)) + θ 1 i , u i+1 -s + r 2 u i+1 -s -w i , u i+1 -s -w i = - ν(Ω) -m - Ω θ 1 i + r Ω (w i -u i+1 ) r Ω 1 .

Solving the discretized problems

• In Step 2, the variables q, z, w are independent. So, we solve them separately:

1. For z i+1 and w i+1 , if we choose P 2 finite element for z i+1 and w i+1 , at vertex x k ,

z i+1 (x k ) = Proj [r∈R: r≤0] -u i+1 (x k ) + θ 0 i (x k ) r = min -u i+1 (x k ) + θ 0 i (x k ) r , 0 and
w i+1 (x k ) = Proj [r∈R: r≤0] u i+1 (x k ) -λ i+1 + θ 1 i (x k ) r = min u i+1 (x k ) -λ i+1 + θ 1 i (x k ) r , 0 .
2. For q i+1 , if we choose P 1 finite element for q i+1 then, at each vertex x l ,

q i+1 (x l ) = Proj B F * (x l ,.) ∇u i+1 (x l ) + Φ i (x l ) r ,
where B F * (x,.) := q ∈ R N : F * (x, q) ≤ 1 the unit ball for F * (x, .).

It remains to explain how we compute the projection onto B F * (x l ,.) . This issue is recently discussed in [START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF] for Riemann-type Finsler distances and for crystalline norms. For the convenience of the reader, we retake here the case where the unit ball of F (x, .) is (not necessarily symmetric) convex polygon. For short, we ignore the dependence of x in F and F * . Given d 1 , ..., d k = 0 such that, for any 0 = v ∈ R N , max 1≤i≤k { v, d i } > 0. We consider the nonsymmetric Finsler metric given by

F (v) := max 1≤i≤k { v, d i } for any v ∈ R N .
It is not difficult to see that the unit ball B * corresponding to F * is exactly the convex hull of {d i },

B * = conv(d i , i = 1, ..., k).
Thus we need to compute the projection onto the convex hull of finite points. In dimension 2, the projection onto B * can be performed as follows: Compute the successive vertices S 1 , ..., S n . If q / ∈ B * then compute the projections of q onto the segments [S i , S i+1 ] and compare among these projections to chose the right one. Another way is as the one in [START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF]: Compute outward orthogonal vectors v 1 , ..., v n (Fig. 3.1). If q belongs to [S i , S i+1 ] + R + v i then the projection coincides with the one on the line through S i , S i+1 . If q belongs to the sector Thanks to Remark 3.10, we can reduce the algorithm in this particular case by ignoring the variable λ. With similar considerations for Λ h u = (∇u, -u), we get the following iteration

S i + R + v i-1 + R + v i the projection is S i .
• Step 1: u i+1 ∈ argmin u∈E h -u, f h + Φ i , ∇u + θ 0 i , -u + r 2 |∇u -q i | 2 + r 2 |u + z i | 2 .
Equivalently,

r ∇u i+1 , ∇v +r u i+1 , v = f h , v -Φ i , ∇v + θ 0 i , v +r q i , ∇v -r z i , v ∀v ∈ E h .
• Step 2:

1. For z i+1 , choosing P 2 finite element for z i+1 , then at each vertex x k ,

z i+1 (x k ) = Proj [r∈R: r≤0] -u i+1 (x k ) + θ 0 i (x k ) r = min -u i+1 (x k ) + θ 0 i (x k ) r , 0 .
2. For q i+1 , choosing P 1 finite element, at vertex x l ,

q i+1 (x l ) = Proj B F * (x l ,.) ∇u i+1 (x l ) + Φ i (x l ) r . • Step 3: (Φ i+1 , θ 0 i+1 ) = (Φ i , θ 0 i ) + r(∇u i+1 -q i+1 , -u i+1 -z i+1 ).
3.4. Numerical experiments

Numerical experiments

We use the FreeFem++ software [START_REF] Hecht | New development in Freefem++[END_REF] and base on [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF][START_REF] Benamou | Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations[END_REF]. We use P 2 finite element for u i , z i , w i , θ 0 i , θ 1 i and P 1 finite element for Φ i , q i .

Stopping criterion

In computational version, the measures µ and ν are approximated by nonnegative regular functions that we denote again by µ and ν. We use the stopping criteria:

• For the partial transport:

1. MIN-MAX := min min

Ω u(x), λ -max Ω u(x), min Ω θ 0 (x), min Ω θ 1 (x) .
2. Max-Lip := sup Ω F * (x, ∇u(x)).

DIV :=

∇ • Φ + ν -θ 1 -µ + θ 0 L 2 . 4. DUAL := F (x, Φ(x)) -Φ(x) • ∇u L 2 .
5. MASS := (νθ 1 )dxm .

• For the unbalanced transport: We change 1. MIN-MAX := min min Ω u(x), min Ω θ 0 (x) .

DIV :=

∇ • Φ + ν -µ + θ 0 L 2 .
We expect MIN-MAX ≥ 0, Max-Lip ≤ 1; DIV, DUAL and MASS are small.

Some examples

In all the examples below, we take Ω = [0, 1] × [0, 1]. We test for the Riemannian case and the crystalline case. For the latter, we consider the Finsler metric of the form Ω and ν = δ (0.5,0.5) the Dirac mass at (0.5, 0.5). The Finsler metric is the Euclidean one. The optimal flow is given in Fig. 3.2. The stopping criterion at each iteration is given in Fig. 3.3. Example 3.13. We take µ and ν as in the previous example, and the Finsler metric given by F (x, v) The optimal flow is given in Fig. 3.4 and the stopping criterion at each iteration is given in Fig. 3.5. 2 . We test for different Finsler metrics. On each figure below, the subfigure at left illustrates the unit ball of F and the subfigure at right gives the numerical result (see Figs 3.6, 3.7, 3.8 and 3.9). The stopping criteria are summarized in Table 3 with L satisfying some conditions such that, in contrast to the previous chapters, the class c L includes c(x, y) = |x -y| 2 as a particular case. Our main aims are to develop rigorously the variational approach to provide equivalent dynamical formulations and use them to supply numerical approximations. For the uniqueness, using basically the idea of [START_REF] Philippis | BV estimates in optimal transportation and applications[END_REF], we establish the uniqueness of active submeasures in the case where the densities are absolutely continuous.

F (x, v) = max 1≤i≤k { v, d i } with given directions d 1 , ..., d k such that for any 0 = v ∈ R 2 , max 1≤i≤k { v, d i } > 0.
:= |v 1 |+|v 2 |, for v = (v 1 , v 2 ) ∈ R

Numerical experiments

Recall that the PMK problem reads as follows min

   K(γ) := R N ×R N c L (x, y)dγ : γ ∈ π m (µ, ν)    . (4.2)
To introduce and comment our main results, let us take a while to focus on the typical situation where the cost is given by

L(x, z) := k(x) |z| q q for any (x, z) ∈ R N × R N (4.3)
with q > 1 and k being a (positive) continuous function. Recall here that if k ≡ 1 and q = 2, the cost function c L corresponds to the quadratic case:

c L (x, y) = |y -x| 2 for any x, y ∈ R N .
This is more or less the most studied case in the literature (cf. [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF][START_REF] Chen | On the regularity of the free boundary in the optimal partial transport problem for general cost functions[END_REF][START_REF] Dávila | Dynamics of optimal partial transport[END_REF][START_REF] Figalli | The optimal partial transport problem[END_REF][START_REF] Indrei | Free boundary regularity in the optimal partial transport problem[END_REF]). However, let us mention here that our approach is variational and goes after our program of studying the optimal partial transportation from the theoretical and numerical viewpoints of Chapters 2 and 3. To begin with, it is not difficult to see that using standard results concerning the Eulerian formulation of the optimal mass transport problem in the balanced case, i.e. equal mass for the source and the target, an Eulerian formulation associated with the problem (4.2)-( 4.3) can be given by minimizing

Q k(x) |υ(t, x)| q q dρ(t, x) (4.4)
among all the couples (ρ, υ)

∈ M + b (Q)×L 1 ρ (Q) N satisfying the continuity equation ∂ t ρ + ∇ • (υρ) = 0 in Q := [0, 1] × R N (4.5)
in a weak sense with ρ(0) ≤ µ and ρ(1) ≤ ν and ρ(0)(R N ) = m. However, to use the augmented Lagrangian method, we will prove rigorously that in fact the minimization problem of the type (4.4)-(4.5) is the Fenchel-Rockafellar dual of a new dual problem to (4.2). Indeed, using the general duality result on the optimal partial transportation in Chapter 2, we prove that a dynamical formulation of the dual problem of (4.2) consists in maximizing

R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) (4.6)
among the couples (λ, u) ∈ [0, ∞) × Lip(Q), where u satisfies the following constrained Hamilton-Jacobi equation

       ∂ t u(t, x) + k -α (x) |∇xu(t,x)| q ′ q ′ ≤ 0 for a.e. (t, x) ∈ Q -λ ≤ u(0, x), u(1, x) ≤ 0 ∀x ∈ R N . (4.7)
Here q ′ := q q-1 denotes the usual conjugate of q and α = q ′ q . Then, even if the regularity of the solutions here creates an obstruction to the application of the Optimal Partial Transport and Constrained Matching Problems 4.1. Introduction general theory, we will prove that the minimization problem (4.4) remains to be the Fenchel-Rockafellar dual of the maximization problem (4.6)-(4.7). Using these equivalents, we overbalance the problem into the scope of augmented Lagrangian methods and give numerical approximations to the optimal partial transport problem. In particular, we will see that this approach does not need to evaluate c L (x, y), for each pair of endpoints x and y, but requires only some values of L. Also, the method provides at the same time active submeasures and the associated optimal transportation.

In addition, let us mention that the Fenchel-Rockafellar duality between the maximization problem (4.6) and the minimization problem (4.4) brings up (as optimality condition) a new type of "constrained" Mean Field Game (MFG) system. For the particular case (4.3), this system aims to find (ρ, υ)

∈ M + b (Q) × L 1 ρ (Q) N satisfying both the usual MFG system associated with the cost (4.2)-(4.3):                  ∂ t u(t, x) + k -α (x) |∇xu(t,x)| q ′ q ′ ≤ 0 for a.e. (t, x) in Q ∂ t ρ + ∇ • (υρ) = 0 in (0, 1) × R N υ(t, x) = k(x) -α |∇ x u(t, x)| q ′ -2 ∇ x u(t, x) ρ-a.e. (t, x) in Q (4.8)
and the following non-standard initial boundary values:

ρ(0) -µ ∈ ∂I [-λ,+∞) (u(0, .)) and ν -ρ(1) ∈ ∂I (-∞,0] (u(1, .)). (4.9)
In other words, these initial boundary values may be written as: -λ ≤ u(0, .), u(1, .) ≤ 0, ρ(0) ≤ µ, ρ(1) ≤ ν, ρ(0) = µ in the set [u(0, .) > -λ] and ρ(1) = ν in the set [u(1, .) < 0]. In the system (4.8), λ is an arbitrary non-negative parameter and the couple (ρ(0), ρ( 1)

) ∈ M + b (R N ) × M + b (R N ) is unknown.
Once the system is solved with the optimal λ for (4.4), the couple (ρ(0), ρ(1)) gives the active submeasures and ρ gives the optimal transportation. Actually, for a given λ ≥ 0, (4.8)-(4.9) is a new type of constrained MFG system. In this direction, one can see some variant of constrained MFG systems and their connection with the Mean Field Games under congestion effects in the paper [START_REF] Santambrogio | A modest proposal for MFG with density constraints[END_REF]. However, let us mention that (4.8)-(4.9) is different from the class of MFG systems introduced in [START_REF] Santambrogio | A modest proposal for MFG with density constraints[END_REF]. In particular, one sees that the constraints in (4.9) focus only the state at time t = 0 and t = 1. As to the constraints in [START_REF] Santambrogio | A modest proposal for MFG with density constraints[END_REF], they are maintained on all the trajectory for every time t ∈ [0, 1] to handle some Chapter 4: Optimal Partial Transport with Lagrangian costs kind of congestion.

At last, let us mention that the main difficulty in the study of the above variational approach of the problem (4.2) for general Lagrangian L remains in the regularity of solutions of the optimization problems like (4.4)-(4.5) and (4.6)-(4.7).

To handle this difficulty we prove some new results concerning approximation of the solutions of general constrained Hamilton-Jacobi equation like (4.7) by regular function. Moreover, we show how to use the notion of tangential gradient to study MFG system like (4.8)-(4.9) in the general case. In particular, when

m = µ(R N ) = ν(R N ) and L(x, v) = L(v) is independent
of x, this MFG system reduces to the PDE as in the work of Jimenez [START_REF] Ch | Dynamic formulation of optimal transport problems[END_REF].

To avoid unnecessary difficulties, in our theoretical study, we will work with Ω = R N in the definition (4.1) of c L . Throughout this chapter, we drop the subscript L and write simply c instead of c L .

Assumption (A): Assume that the Lagrangian L : R N × R N → [0, +∞) is continuous and satisfies:

• L(x, .
) is convex and L(x, 0) = 0 for each fixed x ∈ R N ; • (Superlinearity) for any R > 0, there exists a function θ R : R

+ → R + such that θ R (t) t → +∞ as t → +∞ and L(x, v) ≥ θ R (|v|) ∀x ∈ B(0, R).
For example, the function L(x, v) := k(x) |v| q q , q > 1 satisfies the above assumption whenever k is (positive) continuous.

As usual, the convex conjugate H of L is defined by

H(x, p) := sup v∈R N { p, v -L(x, v)} for any x ∈ R N , p ∈ R N .
Note that, under the assumption (A) on L, the function H(., .) is continuous in both variables and that c(., .) is locally Lipschitz.

We set Q := [0, 1] × R N . The usual derivatives of u are denoted by ∂ t u, ∇ x u, and ∇ t,x u := (∂ t u, ∇ x u). Recall that the continuity equation

∂ t ρ + ∇ • (υρ) = 0, ρ(0) = µ, ρ(1) = ν is understood in the sense of distribution, i.e. Q ∂ t φdρ + Q ∇ x φ • υdρ = R N φ(1, .)dρ(1) - R N φ(0, .)dρ(0) = R N φ(1, .)dν - R N φ(0, .)dµ
-div t,x (ρ, υρ) = δ 1 ⊗ ν -δ 0 ⊗ µ.

Uniqueness of active submeasures

The existence of active submeasures follows from Chapter 2. The present section concerns the uniqueness.

Theorem 4.1 (Uniqueness). Assume moreover that L(x, v) = L(v) is independent of x and that L(v) = 0 if and only if v = 0. If µ, ν ∈ L 1 and m ∈ [µ∧ν(R N ), m max ]
then there is at most one couple of active submeasures.

The idea of the proof is based on the recent paper [75, Proposition 5.2]. For completeness, we give here an adaptation to our case. Lemma 4.2. Assume that L satisfies the assumption (A). Let (ρ 0 , ρ 1 ) be a couple of active submeasures and γ ∈ π(ρ 0 , ρ 1 ) be an optimal plan. If (x * , y * ) ∈ supp(γ)

then ρ 0 = µ a.e. on B c (y * , R) := {t ∈ R N : c(t, y * ) < R} and ρ 1 = ν a.e. on B c (x * , R) := {w ∈ R N : c(x * , w) < R)}, where R := c(x * , y * ) = c L (x * , y * ).
Proof. We prove that ρ 1 = ν a.e. on B c (x * , R). If the conclusion is not true then there exists a compact set K ⋐ B c (x * , R) with a positive Lebesgue measure such that ρ 1 < ν a.e. on K. The proof consists in the construction of a better plan γ. Since (x * , y * ) ∈ supp(γ), we have

0 < γ(B(x * , r) × B(y * , r)) ≤ B(y * ,r)
νdx → 0 as r → 0, where B(x, r) is the ball w.r.t. the Euclidean norm. Now, geometrically speaking, instead of transporting mass from x * to around y * , we can give more mass on K. To be more precise, we construct a new plan γ as follows

γ := γ -γ B(x * ,r)×B(y * ,r) +η with η := π x #(γ B(x * ,r)×B(y * ,r) ) ⊗ (ν -ρ 1 ) K K (ν -ρ 1 )dx .
π y #γ ≤ π y #γ + γ(B(x * , r) × B(y * , r)) K (ν -ρ 1 )dx (ν -ρ 1 ) K ≤ ρ 1 + (ν -ρ 1 ) K ≤ ν
for all sufficiently small r. It follows that γ ∈ π m (µ, ν). Furthermore, we have c(x, y)dγ

= c(x, y)dγ - B(x * ,r)×B(y * ,r) c(x, y)dγ + B(x * ,r)×K c(x, y)dη ≤ c(x, y)dγ - inf (x,y)∈B(x * ,r)×B(y * ,r) c(x, y) - sup (x,y)∈B(x * ,r)×K c(x, y) γ(B(x * , r) × B(y * , r)).
< c(x, y)dγ for small r,

where we used the fact that inf

(x,y)∈B(x * ,r)×B(y * , r) c(x, y) - sup (x,y)∈B(x * ,r)×K c(x, y)
> 0 for small r.

This holds because of the definition of K and the continuity of c.

The next lemma provides an expression for active submeasures.

Lemma 4.3. Under the assumptions of Theorem 4.1, let (ρ 0 , ρ 1 ) be couple of active submeasures. Then

ρ 0 = χ B c 0 µ and ρ 1 = χ B c 1 ν for some measurable sets B 0 , B 1 .
Proof. Since L(x, v) = L(v), we get c(x, y) := c L (x, y) = L(y-x). Thus c(x, y) = 0 if and only if x = y. This implies that the common mass µ ∧ ν must belong to active submeasures, i.e., µ ∧ ν ≤ ρ 0 and µ ∧ ν ≤ ρ 1 . So without loss of generality, we can assume that the initial measures µ and ν are disjoint, i.e., µ ∧ ν = 0. Now, let us define B 0 := Leb(µ) ∩ Leb(ν) ∩ Leb(ρ 0 ) ∩ {ρ 0 < µ} (1) and B 1 := Leb(µ) ∩ Leb(ν) ∩ Leb(ρ 1 ) ∩ {ρ 1 < ν} (1) .

Here, Leb(g) is the set of Lebesgue points of g and A (1) is the set of points of

Optimal Partial Transport and Constrained Matching Problems

Chapter 4: Optimal Partial Transport with Lagrangian costs

Equivalent formulations

In the present section, under the general assumptions of section 4.1, we introduce and study the equivalent formulations for the PMK problem of the type (4.4)-(4.5) and also (4.6)-(4.7).

Dual formulation

We start with the Kantorovich-type dual formulation. It follows from Theorem 2.9 that the DPMK problem can be rewritten as max

(λ,φ,ψ) ψ dν -φ dµ + λ(m -µ(R N )) : λ ∈ R + , (φ, ψ) ∈ Φ λ c (µ, ν) , (4.11)
where

Φ λ c (µ, ν) := (φ, ψ) ∈ L 1 µ × L 1 ν : -λ ≤ φ, ψ ≤ 0, ψ(y) -φ(x) ≤ c(x, y) ∀x, y ∈ R N .
Moreover, we have

     K(γ) := R N ×R N c(x, y)dγ      = max (λ,u)    R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : λ ∈ R + , u ∈ K λ c    , (4.12)
where

K λ c := u ∈ Lip(Q) : ∂ t u(t, x) + H(x, ∇ x u(t, x)) ≤ 0 for a.e. (t, x) ∈ Q, -λ ≤ u(0, x) and u(1, x) ≤ 0 ∀x ∈ R N .
Note that if u ∈ K λ c and u is smooth then we get

∂ t u(t, x) + ∇ x u(t, x), v ≤ L(x, v) ∀(t, x) ∈ Q, v ∈ R N . (4.13)
In general, for any u ∈ K λ c , we can approximate u by smooth functions satisfying a similar estimate for (4.13). This is the content of the following lemma. Although we obtain here only the estimate at the limit, this is enough for later use.

Optimal Partial Transport and Constrained Matching Problems

u ε ∈ C ∞ (R × R N ) such that u ε converges uniformly to u on Q and lim sup ε→0 (∂ t u ε (t, x) + ∇ x u ε (t, x), v ) ≤ L(x, v) ∀(t, x) ∈ Q, v ∈ R N (4.14)
and, for all ξ ∈ Lip([0, 1]; R N ),

lim sup ε→0 1 0 ∂ t u ε (t, ξ(t)) + ∇ x u ε (t, ξ(t)), ξ(t) dt ≤ 1 0 L(ξ(t), ξ(t))dt. (4.15)
Proof. Let α ε , β ε be standard mollifiers on R and R N , respectively, such that

supp(α ε ) ⊂ [-ε, ε]. (4.16)
Set η ε (t, x) := α ε (t)β ε (x). Let ũ be a Lipschitz extension of u on R × R N . By means of convolution in both time and spacial variables, let us define

ũε := η ε ⋆ ũ and u ε (t, x) := ũε (ε + (1 -2ε)t, (1 -2ε)x) for (t, x) ∈ R × R N .
Let us show that u ε satisfies all the requirements. First, since ũ is Lipschitz, u ε converges uniformly to u on Q. Now, for all t ∈ [0, 1], using (4.16), we have

u ε (t, x) = R R N α ε (ε + (1 -2ε)t -s)β ε ((1 -2ε)x -y)ũ(s, y)dy ds = 1 0 R N α ε (ε + (1 -2ε)t -s)β ε ((1 -2ε)x -y)u(s, y)dy ds.
Fix any v ∈ R N , for all t ∈ [0, 1], we have Recall that (the Reverse Fatou's Lemma) if there exists an integrable function g on a measure space (X, η) such that g ε ≤ g for all ε, then lim sup

∂ t u ε (t, x) + v, ∇u ε (t, x) = (1 -2ε) 1 0 R N α ε (ε + (1 -2ε)t -s)β ε ((1 -2ε)x -y)∂ s u(s, y) dy ds + (1 -2ε) v, 1 0 R N α ε (ε + (1 -2ε)t -s)β ε ((1 -2ε)x -y)∇ y u(s, y) dy ds ≤ (1 -2ε) 1 0 R N α ε (ε + (1 -2ε)t -s)β ε ((1 -2ε)x -y)L(y, v) dy ds = (1 -2ε) R N β ε ((1 -2ε)x -y)L(y, v) dy. ( 4
ε g ε dη ≤ lim sup ε g ε dη.
In our case, on X := [0, 1] with the Lebesgue measure, the functions g ε (t

) := ∂ t u ε (t, ξ(t)) + ∇ x u ε (t, ξ(t)), ξ(t)
∂ t u ε (t, ξ(t)) + ∇ x u ε (t, ξ(t)), ξ(t) dt ≤ 1 0 lim sup ε→0 ∂ t u ε (t, ξ(t)) + ∇ x u ε (t, ξ(t)), ξ(t) dt ≤ 1 0 L(ξ(t), ξ(t))dt.
Note that we can do even better in the case where L(x, v) = L(v) is independent of x. Indeed, from our argument (4.17), we can choose u ε such that

∂ t u ε (t, x) + ∇ x u ε (t, x), v ≤ L(x, v) ∀(t, x) ∈ Q, v ∈ R N
without passing ε to 0. Now, we are ready to prove the duality (4.12). We check directly that the maximization is less than the minimum in (4.12) with the help of Lemma 4.6. For the converse inequality, we make use of the theory of Hamilton-Jacobi equations.

Proof of Theorem 4.5. Fix any u ∈ K λ c . Let u ε be the sequence of smooth functions given in Lemma 4.6. Fix any ξ ∈ Lip([0, 1]; R N ) such that ξ(0) = x, ξ(1) = y. By Optimal Partial Transport and Constrained Matching Problems

(u ε (1, ξ(1)) -u ε (0, ξ(0))) = lim ε→0 1 0 ∂ t u ε (t, ξ(t)) + ∇ x u ε (t, ξ(t)), ξ(t) dt ≤ 1 0 L(ξ(t), ξ(t))dt.
Since ξ is arbitrary, we get

u(1, y) -u(0, x) ≤ c(x, y) ∀x, y ∈ R N .
In view of (4.11), we deduce that

K(σ * ) ≥ sup (λ,u)    R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : λ ∈ R + , u ∈ K λ c    . (4.19)
Conversely, let (φ, ψ) ∈ Φ λ c (µ, ν) be a maximizer in (4.11). Set These imply that u * ∈ K λ c and that

u * (1, y) -u * (0, x) ≥ ψ(y) -φ * (x) ∀x, y ∈ R N . Thus R N u * (1, .)dν - R N u * (0, .)dµ + λ(m -µ(R N )) ≥ ψdν -φ * dµ + λ(m -µ(R N )) = K(σ * ).
Combining this with (4.19), the duality (4.12) holds and u * is a solution of the maximization problem on the right hand side of (4.12).

Eulerian formulation by Fenchel-Rockafellar duality

As we said in the introduction, the Fenchel-Rockafellar duality is an important ingredient of our analysis, especially for the numerical analysis by augmented Lagrangian methods.

Theorem 4.7. Under the assumptions of Theorem 4.5, we have max

   R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : (λ, u) ∈ R + × K λ c    = min    Q L(x, υ(t, x))dρ(t, x) : (ρ, υ, θ 0 , θ 1 ) ∈ B c    , (4.20)
where

B c := (ρ, υ, θ 0 , θ 1 ) ∈ M + b (Q) × L 1 ρ (Q) N × M + b (R N ) × M + b (R N ) : θ 0 (R N ) = µ(R N ) -m, -div t,x (ρ, υρ) = δ 1 ⊗ (ν -θ 1 ) -δ 0 ⊗ (µ -θ 0 ) .

Equivalent formulations

Roughly speaking, the minimization in (4.20) is the Fenchel-Rockafellar dual of the maximization problem. However, the interesting point to note here is that the maximization problem in (4.20) does not satisfy the sufficient conditions to use directly the dual theory of Fenchel-Rockafellar. To overcome this difficulty, we approximate the maximization problem by a suitable supremum problem. To this end, for general Lagrangian L, we make use of the smooth approximations given in Lemma 4.6.

Proof of Theorem 4.7. Let us first show that max

   R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : (λ, u) ∈ R + × K λ c    ≤ inf    Q L(x, υ)dρ : (ρ, υ, θ 0 , θ 1 ) ∈ B c    . (4.21)
Fix any u ∈ K λ c and (ρ, υ, θ 0 , θ 1 ) ∈ B c . Let u ε be the sequence of smooth functions given in Lemma 4.6. Taking u ε as a test function in the continuity equation

-div t,x (ρ, υρ) = δ 1 ⊗ (ν -θ 1 ) -δ 0 ⊗ (µ -θ 0 ), we have Q ∂ t u ε dρ+ Q ∇ x u ε (t, x)•υ(t, x)dρ = R N u ε (1, .)d(ν -θ 1 )- R N u ε (0, .)d(µ-θ 0 ). Since θ 0 (R N ) = µ(R N ) -m, we get R N u ε (1, .)dν - R N u ε (0, .)dµ + λ(m -µ(R N )) = R N u ε (1, .)dν - R N u ε (0, .)dµ -λ R N dθ 0 = R N u ε (1, .)d(ν -θ 1 ) - R N u ε (0, .)d(µ -θ 0 ) + R N u ε (1, .)dθ 1 -(u ε (0, .) + λ) dθ 0 = Q (∂ t u ε + ∇ x u ε • υ) dρ + R N u ε (1, .)dθ 1 -(u ε (0, .) + λ) dθ 0 .
R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) ≤ Q L(x, υ(t, x))dρ + R N u(1, .)dθ 1 - R N (u0, .) + λ) dθ 0 ≤ Q L(x, υ(t, x))dρ(t, x).
This implies the desired inequality (4.21). Let us now prove the converse inequality. Obviously, we have

max    R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : (λ, u) ∈ R + × K λ c    ≥ sup    R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : (λ, u) ∈ R + × K λ c , u ∈ C 1,1 (Q)    .
It is sufficient to show that

sup    R N u(1, .)dν - R N u(0, .)dµ + λ(m -µ(R N )) : (λ, u) ∈ R + × K λ c , u ∈ C 1,1 (Q)    = min      Q L(x, υ(t, x))dρ : (ρ, υ, θ 0 , θ 1 ) ∈ B c      . (4.23)
This will be proved by using the Fenchel-Rockafellar dual theory. Indeed, the supremum problem in (4.23) can be written as

-inf (λ,u)∈V F(λ, u) + G(Λ(λ, u)),
where

F(λ, u) := - R N u(1, .)dν + R N u(0, .)dµ -λ(m -µ(R N )) for (λ, u) ∈ V := R × C 1,1 (Q), Λ(λ, u) := (∇ t,x u, -λ -u(0, .), u(1, .)) ∈ Z := C b (Q) N +1 × C b (R N ) × C b (R N ), G(q, z, w) :=    0 if z(x) ≤ 0, w(x) ≤ 0 and q 1 (t, x) + H(x, q N (t, x)) ≤ 0 ∀(t, x) ∈ Q +∞ otherwise
Optimal Partial Transport and Constrained Matching Problems 97 4.3. Equivalent formulations with q := (q 1 , q N ) ∈ C b (Q) × C b (Q) N for all (q, z, w) ∈ Z. Now, using the Fenchel-Rockafellar dual theory, we have inf

(λ,u)∈V F(λ, u) + G(Λ(λ, u)) = max (Φ,θ 0 ,θ 1 )∈M b (Q) N +1 ×M b (R N )×M b (R N )
-F * (-Λ * (Φ, θ 0 , θ 1 )) -G * (Φ, θ 0 , θ 1 ) .

(4.24) The proof is completed by computing explicitly these quantities.

• Let us compute F * (-Λ * (Φ, θ 0 , θ 1 )). Since F is linear, F * (-Λ * (Φ, θ 0 , θ 1 )) is finite (and is equal to 0 whenever finite) if and only if

-Λ * (Φ, θ 0 , θ 1 ), (λ, u) = F(λ, u) = -u(1, .) dν + u(0, .) dµ -λ(m -µ(R N ))
for all (λ, u) ∈ V . Equivalently,

-∇ t,x u, Φ -θ 0 , -λ -u(0, .) -θ 1 , u(1, .) = -u(1, .), ν + u(0, .), µ -λ(m -µ(R N ))
for all (λ, u) ∈ V. This implies that -∇ t,x u, Φ = u(0, .), µθ 0u(1, .), νθ 1 for all test functions u ∈ C 1,1 (Q) and that θ 0 (R N ) = µ(R N )m.

Recall that Φ ∈ M b (Q) N +1 , writing Φ = (ρ, E), the above computation gives

-div t,x (ρ, E) = δ 1 ⊗ (ν -θ 1 ) -δ 0 ⊗ (µ -θ 0 ), and θ 0 (R N ) = µ(R N ) -m.
• For G * (Φ, θ 0 , θ 1 ), since H(., .) is continuous, using the same arguments as in [START_REF] Santambrogio | Optimal Transport for Applied Mathematicians[END_REF]Proposition 5.18], we have

G * (Φ, θ 0 , θ 1 ) =      Q L(x, υ(t, x))dρ if θ 0 ≥ 0, θ 1 ≥ 0, Φ = (ρ, E), ρ ≥ 0, E ≪ ρ, E = υρ +∞ otherwise.
Substituting F * and G * into (4.24), we obtain the needed equality (4.23).

98

Optimal Partial Transport and Constrained Matching Problems

Optimality condition and constrained MFG system

To write down the optimality condition for the duality (4.20), we need to use the notion of tangential gradient to a measure.

Optimality condition for the duality (4.20) is related to the following PDE system: Similarly, the condition -θ 0 ∈ ∂I [-λ,+∞) (u(0, .)) reads as u(0, .) ≥ -λ, θ 0 ≥ 0 and R N (u(0, .) + λ) dθ 0 = 0. Theorem 4.8. Assume that (ρ, υ, θ 0 , θ 1 ) ∈ B c and (λ, u) ∈ R + × K λ c are optimal for the two problems in the duality (4.20). Then (ρ, υ, θ 0 , θ 1 , u) satisfies the system (PDE λ ). Conversely, if (ρ, υ, θ 0 , θ 1 , u) is a solution of (PDE λ ), then (ρ, υ, θ 0 , θ 1 ) and (λ, u) are solutions to the duality (4.20) w.r.t. m = µ(R N )θ 0 (R N ). Remark 4.9. For the standard optimal transport problem, i.e., m = µ(R N ) = ν(R N ) (in this case θ 0 = θ 1 = 0), the optimality conditions (PDE λ ) can be reduced 4.3. Equivalent formulations to the following system:

                                             -div t,x (ρ, υρ) = δ 1 ⊗ (ν -θ 1 ) -δ 0 ⊗ (µ -θ 0 ) L(x, υ(t, x)) = ∇ ρ u(t, x) • (1, υ(t, x)) ρ-a.e. (t, x) in Q ∂ t u(t, x) + H(x, ∇ x u(t, x)) ≤ 0 a.e. (t, x) in Q -θ 0 ∈ ∂I [-λ,+∞) (u(0, .)) θ 1 ∈ ∂I (-∞,0] (u(1, .)) (ρ, υ, θ 0 , θ 1 ) ∈ M + b (Q) × L 1 ρ (Q) N × M + b (R N ) × M + b (R N ), ( PDE
         -div t,x (ρ, υρ) = δ 1 ⊗ ν -δ 0 ⊗ µ L(x, υ(t, x)) = ∇ ρ u(t, x) • (1, υ(t, x)) ρ-a.e. in Q ∂ t u(t, x) + H(x, ∇ x u(t, x)) ≤ 0 a.e. in Q. (4.25)
In particular, if L(x, v) = L(v) is independent of the variable x then the system (4.25) recovers the same PDE as in the work of Jimenez [START_REF] Ch | Dynamic formulation of optimal transport problems[END_REF].

Remark 4.10. If m = µ(R N ) = ν(R N ) and assume moreover that ρ ≪ L N +1 , then the conditions (4.25) can be rewritten as

               -div t,x (ρ, υρ) = δ 1 ⊗ ν -δ 0 ⊗ µ ∂ t u(t, x) + H(x, ∇ x u(t, x)) ≤ 0 a.e. (t, x) in Q ∂ t u(t, x) + H(x, ∇ x u(t, x)) = 0 ρ-a.e. (t, x) in Q υ(t, x) ∈ ∂H(x, ∇ x u(t, x)) ρ-a.e. (t, x) in Q,
where ∂H is the subdifferential of H w.r.t. the second variable. Indeed, the condition L (x, υ(t, x)) = ∇ ρ u(t, x) • (1, υ(t, x)) ρ-a.e. implies that L (x, υ(t, x)) = ∇ t,x u(t, x) • (1, υ(t, x)) ρL N +1 -a.e. in Q = ∂ t u(t, x) + υ(t, x) • ∇ x u(t, x) ρL N +1 -a.e. in Q.

This implies that

L (x, υ(t, x)) ≤ ∂ t u + H(x, ∇ x u(t, x)) + L(x, υ(t, x)) ≤ L (x, υ(t, x)) ρL N +1 -a.e. in Q.

Hence ∂ t u(t, x) + H(x, ∇ x u(t, x)) = 0 ρ-a.e. in Q and υ(t, x) ∈ ∂H(x, ∇ x u(t, x)) ρ-a.e. in Q.

To prove Theorem 4.8, we need a similar estimate for (4.13) for any u ∈ K λ c . Since u is not smooth in general, we will characterize the estimate (4.13) via the tangential gradient instead of the usual one.

(Q) × L 1 ρ (Q) N satisfying the continuity equation -div t,x (ρ, υρ) = δ 1 ⊗ ρ 1 -δ 0 ⊗ ρ 0 , 100
Q ∇ ρ u • (1, υ)ξ dρ = lim ε→0 Q ∇ ρ u ε • (1, υ)ξ dρ = lim ε→0 Q ∇ t,x u ε • (1, υ)ξ dρ ≤ Q L(x, υ(t, x))ξ dρ ∀ξ ∈ D(R N +1 ), ξ ≥ 0.
Thus the result of the lemma follows.

Proof of Theorem 4.8. Let (ρ, υ, θ 0 , θ 1 ) ∈ B c and (λ, u) ∈ R + × K λ c be admissible elements, respectively. Let u ǫ be the sequence given by Lemma 4.6. By (4.22) and Lemma 4.11, we have u(1, .) dνu(0, . (u(0, .) + λ)dθ 0 = 0. These show that (ρ, υ, θ 0 , θ 1 , u)

) dµ + λ(m -µ(R N )) = lim ǫ→0 u ǫ dν -u ǫ dµ + λ(m -µ(R N )) = lim ǫ→0   Q (∂ t u ε + ∇ x u ε • υ) dρ + R N u ε (1, .)dθ 1 - R N (u ε (0, .) + λ) dθ 0   = lim ǫ→0 Q (∂ t u ε + ∇ x u ε • υ) dρ + R N u(1, .)dθ 1 - R N (u(0, .) + λ) dθ 0 ≤ lim ǫ→0 Q ∇ t,x u ε • (1, υ)dρ = Q ∇ ρ u • (1, υ)dρ ≤ Q L(x, υ(t, x))dρ.
satisfies the system (PDE λ ).

2. Conversely, if (ρ, υ, θ 0 , θ 1 , u) satisfies the system (PDE λ ), the inequalities in (4.26) are equalities. Using the duality (4.20), we obtain the desired optimalities. This remark allows us to solve the PMK problem by using numerical methods for approximation of the Fenchel-Rockafellar dual problem.

Numerical approximation

We will apply the ALG2 algorithm to the dual formulation on the right hand side of (4.12) in order to give numerical approximations for the optimal partial transport problem. We will solve for active submeasures ρ 0 = µθ 0 , ρ 1 = νθ 1 and the optimal movement of density ρ t from ρ 0 to ρ 1 .

Recall that the dual maximization formulation in (4.12) can be rewritten as

inf {F(λ, u) + G(Λ(λ, u)) : (λ, u) ∈ V } , where F(λ, u) := -u(1, .) dν + u(0, .) dµ-λ(m-µ(R N )) for (λ, u) ∈ V := R×C 1,1 (Q), Λ(λ, u) := (∇ t,x u, -λ -u(0, .), u(1, .)) ∈ Z := C b (Q) N +1 × C b (R N ) × C b (R N ) 102
Optimal Partial Transport and Constrained Matching Problems and, for all (q, z, w) ∈ Z,

G(q, z, w) :=    0 if z(x) ≤ 0, w(x) ≤ 0 and q = (q 1 (t, x), q N (t, x)) ∈ K x ∀(t, x) ∈ Q +∞ otherwise with K x := (a, b) ∈ R × R N : a + H(x, b) ≤ 0 , x ∈ R N .
Let us discuss the details of computation. Actually, in computation, we replace V, Z by finite-dimensional spaces, for example, using Lagrangian piecewise polynomials. We denote by P i the space of piecewise polynomials of degree i, i = 1, 2. We will use V = (R, P 2 ) and Z = (P N +1 1 , P 2 , P 2 ), where P N 1 := ( N times P 1 , ..., P 1 ). We use L 2 -norm for P 1 , P 2 , P N +1 1 .

• Step 1: We split into two steps: First using λ i to compute u i+1 and then using u i+1 to calculate λ i+1 .

1. For u i+1 , we solve min u -( u(1, .), νu(0, .), µ ) + (σ i , θ 0 i , θ 1 i ), (∇ t,x u, -u(0, .), u(1, .))

+ r 2 |(∇ t,x u, -λ i -u(0, .), u(1, .)) -(q i , z i , w i )| 2 .
This is a quadratic problem which is equivalent to a linear equation with a positivedefinite coefficient matrix. So this step can be solved effectively by many solvers. The linear equation is detailed as (by taking derivative w.r.t. u) r ∇ t,x u i+1 , ∇ t,x φ + r u i+1 (1, .), φ(1, .) + r u i+1 (0, .), φ(0, .) = φ(1, .), νφ(0, .), µ -(σ i , θ 0 i , θ 1 i ), (∇ t,x φ, -φ(0, .), φ(1, .)) + r (q i , z i , w i ) , (∇ t,x φ, -φ(0, .), φ(1, .))r λ i , φ(0, .) for all (t, φ) ∈ V.

For

λ i+1 , min λ∈R -λ(m -µ(Ω)) + (σ i , θ 0 i , θ 1 i ), (0, -λ, 0) + r 2 |-λ -u i+1 (0, .) -z i | 2 ,
which is equivalent to

λ i+1 = m -µ(Ω) + Ω θ 0 i -r Ω (z i + u i+1 (0, .)) r Ω 1 .
• Step 2: Since the function G(q, z, w) has the form of G 1 (q) + G 2 (z) + G 3 (w), we solve separately for the variables q, z, w.

1. For z i+1 ,

z i+1 ∈ argmin z∈P 2 I [z≤0] -θ 0 i , z + r 2 |-λ i+1 -u i+1 (0, .) -z| 2 = Proj {[z∈P 2 :z≤0]} -λ i+1 -u i+1 (0, .) + θ 0 i r .
This is computed in pointwise, i.e., given a grid with vertices x j , then

z i+1 (x j ) = Proj {[s∈R:s≤0]} -λ i+1 -u i+1 (0, .)(x j ) + θ 0 i (x j ) r = min -λ i+1 -u i+1 (0, .)(x j ) + θ 0 i (x j ) r , 0 .
2. For w i+1 , similarly,

w i+1 = Proj {[w∈P 2 :w≤0]} u i+1 (1, .) + θ 1 i r .
3. For q i+1 , similarly,

q i+1 = Proj Kx ∇ t,x u i+1 + σ i r .
• Step 3: Update Lagrangian multipliers.

Some examples

In all the examples below, we work on the square Ω = [0, 1] × [0, 1] in R 2 and use the discretization size 36 × 36 × 9 for the spatial-time variable. We test the examples for costs of the form

c(x, y) = inf ξ    1 0 L(ξ(t), ξ(t)dt : ξ ∈ Lip([0, 1]; Ω), ξ(0) = x, ξ(1) = y    , with L(x, v) = k(x)|v| 2 , k ∈ C(Ω), k(x) > 0 for all x ∈ Ω, v ∈ R 2 .
For this cost, the last projection in the Step 2 (the projection on K x ) is converted to a problem on R and the latter is computed easily by the bisection method. The active submeasures and the optimal displacement are given in Figure 4.1. Timestep 0 and timestep 9 (ρ 0 and ρ 1 ) are active submeasures of the source and the target, respectively. The intermediate timesteps show the optimal movement of density from ρ 0 to ρ 1 .

IsoValue

(x, v) = k(x)|v| 2 with k(x 1 , x 2 ) = 1 + 15 exp(-45(x 1 -0.5) 2 -45(x 2 -0.5) 2 ), µ = 20 exp(-60(x 1 -0.2) 2 -60(x 2 -0.8) 2 ), ν = 20 exp(-60(x 1 -0.8) 2 -60(x 2 -0.2) 2 ), and
m = m max 2 .
This cost means that we have to pay much if we transport through around (0. This last chapter deals with some theoretical and numerical aspects for an optimal matching problem with constraints. It is known that the uniqueness of optimal matching measure does not hold even with L p sources and targets. In this chapter, the uniqueness is proved under geometric conditions. On the other hand, we also introduce a dual formulation with a linear cost functional on convex set and show that its Fenchel-Rockafellar dual formulation gives right solution to the optimal matching problem. Based on our formulations, a numerical approximation is given. We compute at the same time the optimal matching measure, optimal flows and Kantorovich potentials. The convergence of discretization is studied in detail.

Introduction

Optimal matching problem (see [START_REF] Carlier | Matching for teams[END_REF][START_REF] Chiappori | Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness[END_REF][START_REF] Ekeland | An optimal matching problem[END_REF] and the references therein) deals with the problem to transport two measures of commodities into a prescribed location and to match them there in such a way to minimize the total cost of both transportations. The problem with uniformly convex costs is studied in [START_REF] Carlier | Duality and existence for a class of mass transportation problems and economic applications[END_REF][START_REF] Carlier | Matching for teams[END_REF][START_REF] Chiappori | Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness[END_REF][START_REF] Ekeland | An optimal matching problem[END_REF] with applications in economic theory. The case where costs are governed by the Euclidean distance is studied in [START_REF] Mazón | An optimal matching problem for the Euclidean distance[END_REF] with connection to p-Laplacian type equations.

Optimal constrained matching problem (see [START_REF] Barrett | Partial L 1 Monge-Kantorovich problem: Variational formulation and numerical approximation[END_REF][START_REF] Mazón | An optimal matching problem with constraints[END_REF]), which is a variant from the optimal matching problem and the partial transport problem, consists in transporting two kinds of goods and matching them into a target set with constraints on the amount of matter at the target. Mathematically, the optimal matching problem with constraints for the Euclidean costs can be modeled as follows: Let Ω be a bounded, convex set of R N and f 1 , f 2 ∈ M + b (Ω) represent source measures of the same mass, i.e., f 1 (Ω) = f 2 (Ω). The constraint on the target set is represented by a measure Θ ∈ M + b (Ω), which must satisfy

f 1 (Ω) = f 2 (Ω) < Θ(Ω).
The optimal matching problem reads

W (f 1 , f 2 ; Θ) := inf (γ 1 ,γ 2 )∈π(f 1 ,f 2 ;Θ)   Ω×Ω |x -y|dγ 1 + Ω×Ω |x -y|dγ 2   , (5.1)
with

π(f 1 , f 2 ; Θ) := (γ 1 , γ 2 ) ∈ M + b (Ω × Ω) 2 : π y #γ 1 = π y #γ 2 ≤ Θ, π x #γ i = f i , i = 1, 2 .
An optimal solution (γ 1 , γ 2 ) is called a couple of optimal plans and ρ := π y #γ 1 = π y #γ 2 is called an optimal matching measure. Obviously, we can write (5.1) as follows

W (f 1 , f 2 ; Θ) = inf ρ∈M + b (Ω) W 1 (f 1 , ρ) + W 1 (f 2 , ρ) : ρ ≤ Θ, ρ(Ω) = f 1 (Ω) , (OM)
where W 1 (., .) is the 1-Wasserstein distance.

The problem can be also reformulated by saying that masses moving from f 1 to f 2 are forced to pass through an unknown (optimal) distribution less than Θ and the transportation cost should be optimal. In applications, f 1 and f 2 can be distributions of consumers while Θ would be a distribution of commodities.

Using the direct method, it is not difficult to prove the existence of an optimal matching measure. Our main interest lies in the uniqueness and numerical approximation of solution. As we will see, the uniqueness of optimal matching measure does not hold even with regular f 1 , f 2 , Θ. An additional geometric condition, as well as the absolute continuity of the measure Θ, is needed for the uniqueness. Concerning numerical computation, we develop the variational study of the problem.

The optimal constrained matching problem (OM) is recently studied theoretically in [START_REF] Mazón | An optimal matching problem with constraints[END_REF] in connection with p-Laplacian type systems by using PDE Optimal Partial Transport and Constrained Matching Problems

Main results

techniques. Inspiring from the work of Evans and Gangbo [START_REF] Evans | 136 Optimal Partial Transport and Constrained Matching Problems Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance[END_REF] on the optimal transport theory, the authors in [START_REF] Mazón | An optimal matching problem with constraints[END_REF] show that an optimal matching measure and associated Kantorovich potentials can be obtained from limits in p-Laplacian type equations as p → +∞. In [START_REF] Barrett | Partial L 1 Monge-Kantorovich problem: Variational formulation and numerical approximation[END_REF], Barrett and Prigozhin use approximated nonlinear PDEs and Raviart-Thomas elements to give a numerical approximation to the problem (5.1) in the case where Θ = CL N D , i.e., Θ is a constant C on the destination set D.

In this chapter, we focus more on variational aspects and the uniqueness of optimal matching measure. We introduce some equivalent formulations for the problem (5.1). We give a sufficient condition to ensure the uniqueness of optimal matching measure and show that a solution of the Fenchel-Rockafellar dual formulation is the right solution to the optimal matching problem under a suitable geometric condition. Numerical aspects are also studied with the help of the equivalent formulations. We show the convergence of discretization and give details in solving the discretized problems.

It is important to mention at the beginning that the optimal constrained matching problem behaves differently from the optimal partial transport. Firstly, in contrast to the PMK problem, the Fenchel-Rockafellar duality does not give the right solution, in general. Secondly, the uniqueness of optimal matching measure does not hold even with regular sources and targets.

The chapter is organized as follows: In the following section we present our main results such as the uniqueness of optimal matching measure, dual maximization problem, connection between a minimal matching flow problem and (OM), the convergence of discretization and a numerical example illustrating our approach. The proofs are discussed in the next sections. More precisely, section 5.3 is devoted to the duality issue while the uniqueness is discussed in section 5.4. Numerical analysis of the problem is given in section 5.5 with a study of the convergence of discretization. In the last section, we give some numerical examples.

Main results

Throughout this chapter, Ω ⊂ R N is a bounded convex domain and It is not difficult to see that the feasible set π(f 1 , f 2 ; Θ) is closed under the weak convergence of Radons measures. This observation gives easily the existence of a couple of optimal plans (γ 1 , γ 2 ) and thus an optimal matching measure ρ := π y #γ 1 = π y #γ 2 . However, in general the uniqueness of optimal matching measures does not hold. For instance, let

f 1 , f 2 , Θ ∈ M + b (Ω) are nonnegative Radon measures such that f 1 (Ω) = f 2 (Ω) < Θ(Ω).
f 1 = L [0, 1], f 2 = L [5, 6] and Θ = L [2, 4],
where L is the Lebesgue measure on R. We see that there are infinitely many optimal matching measures with the total cost W (f 1 , f 2 ; Θ) = 5 (one can verify this by using the duality in Theorem 5.3 below).

Here, we prove that under additional conditions on the supports of Θ, f i , for i = 1, 2 and the absolute continuity of Θ, there is a unique optimal matching measure. Let us fix the assumption

S(f 1 , f 2 ) ∩ supp(Θ) = ∅, (H)
where

S(f 1 , f 2 ) := z = (1 -t)x + ty : x ∈ supp(f 1 ), y ∈ supp(f 2 ) and t ∈ [0, 1] .
Theorem 5.1. Assume that Θ ∈ L 1 and that (H) holds. There exists a unique optimal matching measure ρ.

Notice that the absolute continuity of Θ is necessary for the uniqueness. Indeed, taking f 1 = δ (0,-1) , f 2 = δ (0,1) and Θ = δ (-1,0) + δ (1,0) in R 2 , then S(f 1 , f 2 ) ∩ supp(Θ) = ∅ and there are again infinitely many optimal matching measures of form ρ = αδ (-1,0) + βδ (1,0) with α ≥ 0, β ≥ 0, α + β = 1. So, the conditions in Theorem 5.1 are somehow optimal for the uniqueness. Now, to build numerical computation of the solution to the optimal matching problem (OM), our main objective is to prove rigorously all the necessary materials to use the augmented Lagrangian method. Our approach is variational. To this aim, we introduce a suitable dual formulation to (OM) which moves the problem into the scope of the general formulation

inf u∈V F(u) + G(Λu), (5.2)
where V and Z are two Hilbert spaces, F : V -→ (-∞, +∞] and G : Z -→ (-∞, +∞] are convex and l.s.c., and Λ ∈ L(V, Z) the space of continuous linear operators. Once such a dual formulation is given, the ALG2 method (see Chapter 1) can be applied to give numerical solutions to both the problem (5.2) and the Fenchel-Rockafellar dual problem of (5.2):

sup σ∈Z * (-F * (-Λ * σ) -G * (σ)) . (5.3)
Optimal Partial Transport and Constrained Matching Problems

Main results

Recall that the necessary and sufficient condition for optimality of (5.2) and (5.3) reads as -Λ * σ ∈ ∂F(u) and σ ∈ ∂G(Λu).

(5.4)

It is expected that the Fenchel-Rockafellar dual form (5.3) will give informations on the original matching problem. We will see that this is again true under the necessary geometric condition (H).

We come back to the duality issue for (OM). As usual, let us denote by Lip 1 (Ω) the set of 1-Lipschitz functions on Ω. By extension, we usually identify Lip 1 (Ω) with Lip 1 (Ω). Let us recall that the duality issue was already studied in [START_REF] Mazón | An optimal matching problem with constraints[END_REF] with the following result:

Theorem 5.2 ([68]). Assume that f 1 , f 2 ∈ L ∞ (Ω). One has W (f 1 , f 2 ; Θ) = max -u 1 df 1 -u 2 df 2 -(u 1 + u 2 ) -dΘ : u 1 , u 2 ∈ Lip 1 (Ω) .
(5.5) However, even if the problem (5.5) falls into the scope of (5.2), unfortunately the corresponding F is nonlinear on its variable u := (u 1 , u 2 ) and (5.5) is not very useful for numerical computation. Here, we introduce a new dual formulation with the following linear cost functional: max (u 1 + u 2 )dΘu 1 df 1u 2 df 2 : (u 1 , u 2 ) ∈ K , (

where K := {(u 1 , u 2 ) ∈ Lip 1 (Ω) × Lip 1 (Ω) : u 1 + u 2 ≤ 0} .

Using the Fenchel-Rockafellar dual theory to the maximization problem (5.6), we also introduce the minimal matching flow (MMF) problem:

min |Φ 1 |(Ω) + |Φ 2 |(Ω) : (Φ 1 , Φ 2 , ν) ∈ Ψ(f 1 , f 2 ; Θ) , (MMF)
where

Ψ(f 1 , f 2 ; Θ) := (Φ 1 , Φ 2 , ν) ∈ M b (Ω) N ×M b (Ω) N ×M + b (Ω) : -∇•Φ i = Θ-ν-f i in D ′ (R N ) .
As usual, the divergence constraint is understood in the sense of distributions, i.e.

∇φ,

Φ i (C(Ω) N ,M b (Ω) N ) = Ω ∇φ • Φ i |Φ i | d|Φ i |= Ω φd(Θ -ν -f i ),

Main results

This is extensively used to give numerical approximations for some variants of the optimal mass transport problem (see for instance [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF][START_REF] Benamou | Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations[END_REF][START_REF] Benamou | A numerical solution to Monge's problem with a Finsler distance as cost[END_REF][START_REF] Igbida | Augmented Lagrangian method for optimal partial transportation[END_REF]). For the optimal matching problem, we need to compute moreover the optimal matching measure. As an immediate consequence of the duality equalities in Theorem 5.3, the following result shows how this can be carried out.

Corollary 5.5. Let ρ be an optimal matching measure and Φ i be optimal flows for transporting f i onto ρ, i = 1, 2. Then (Φ 1 , Φ 2 , ν) := (Φ 1 , Φ 2 , Θρ) is an optimal solution for the associated problem (MMF). Conversely, if (Φ 1 , Φ 2 , ν) is an optimal solution for the problem (MMF) and ν ≤ Θ, then ρ := Θ-ν is an optimal matching measure and Φ i is an optimal flow of transporting f i onto ρ, i = 1, 2.

This result shows that the connection between (MMF) and (OM) lies in the condition ν ≤ Θ for an optimal solution (Φ 1 , Φ 2 , ν) of (MMF). Unfortunately, this does not hold in general as shown in the following example. Example 5.6. On R, taking f 1 = δ 0 , f 2 = δ 4 , Θ = δ 1 + δ 3 , where δ i is the Dirac mass at i on R (see Fig. 5.1). Let ν = δ 2 and Φ 1 be the optimal flow of transporting f 1 + ν onto Θ (the corresponding plan is described as follows: f 1 = δ 0 → δ 1 , ν = δ 2 → δ 3 ) and Φ 2 be the optimal flow of transporting f 2 + ν onto Θ (the corresponding plan is described as follows: f 2 = δ 4 → δ 3 , ν = δ 2 → δ 1 ). Then (Φ 1 , Φ 2 , ν) is an optimal solution of the problem (MMF). Indeed, it is not difficult to see that the total cost of matching f 1 and f 2 into Θ is 4. The cost of the problem (MMF) corresponding to this choice of (Φ 1 , Φ 2 , ν) is also 4. From our duality results, we have the optimality of (Φ 1 , Φ 2 , ν), but ν Θ. However, under the assumption (H), we prove that the constraint ν ≤ Θ is fulfilled. More precisely, we have Theorem 5.7. Let f 1 , f 2 , Θ ∈ M + b (Ω) be Radon measures. Assume that (H) holds. Let (Φ 1 , Φ 2 , ν) ∈ Ψ(f 1 , f 2 ; Θ) be an optimal solution for the problem (MMF) and set ρ := Θν. Then ρ ≥ 0 and it is an optimal matching measure.

where F, G and Λ are given in section 5.2. Now, using the Fenchel-Rockafellar duality, we have (5.13)

Thus, it is enough to compute explicitly the above quantities. Since F is linear, F * (-Λ * (Φ 1 , Φ 2 , ν)) is finite (and is thus equal to 0) if and only if

-Λ * (Φ 1 , Φ 2 , ν), (u 1 , u 2 ) = F(u 1 , u 2 ) = u 1 df 1 + u 2 df 2 -(u 1 + u 2 )dΘ
for all (u 1 , u 2 ) ∈ C 1 (Ω) × C 1 (Ω), or

-Φ 1 , ∇u 1 -Φ 2 , ∇u 2 -ν, u 1 + u 2 = u 1 df 1 + u 2 df 2 -(u 1 + u 2 )dΘ
for all (u 1 , u 2 ) ∈ C 1 (Ω) × C 1 (Ω). This implies that (by taking (u 1 , u 2 ) = (u 1 , 0) and (u 1 , u 2 ) = (0, u 2 ) as test functions)

-∇ • Φ i = Θ -ν -f i in D ′ (R N ), i = 1, 2.
Next, it is easy to see that

G * (Φ 1 , Φ 2 , ν) =    |Φ 1 |(Ω) + |Φ 2 |(Ω) if ν ≥ 0, +∞, otherwise.
Therefore the proof is completed by substituting F * and G * into (5.13).

Following immediately from (5.12), we see that (5.15)

Moreover, if ν is optimal for the right hand side of (5.15) then there exist 0 ≤ θ 1 , θ 2 ≤ Θ, θ 1 (Ω) = θ 2 (Ω) = f 1 (Ω) such that

W 1 (f 1 , θ 2 ) = W 1 (f 1 , θ 1 ) + W 1 (θ 1 , θ 2 ), (5.16
)

W 1 (f 2 , θ 1 ) = W 1 (f 2 , θ 2 ) + W 1 (θ 1 , θ 2 )
(5.17 and W 1 (ν, Θθ 1 ) + W 1 (ν, Θθ 2 ) = W 1 (θ 1 , θ 2 ).

(5.18)

Proof. The existence of minimizers follows from the direct method. Now, fix any ρ ∈ M + b (Ω) with ρ ≤ Θ, ρ(Ω) = f 1 (Ω) and set ν := Θρ. By (5.12), we have

W 1 (f 1 , ρ) + W 1 (f 2 , ρ) = W 1 (f 1 + ν, Θ) + W 1 (f 2 + ν, Θ).
This shows that the left hand side of (5.15) is greater than or equal to the right hand side. Conversely, take ν ∈ M + b (Ω) with ν(Ω) = Θ(Ω)f 1 (Ω). Consider the optimal plan γ i between f i + ν and Θ. It sends f i to some θ i ≤ Θ, i = 1, 2 such that W 1 (f 1 +ν, Θ) = W 1 (f 1 , θ 1 )+W 1 (ν, Θ-θ 1 ), W 1 (f 2 +ν, Θ) = W 1 (f 2 , θ 2 )+W 1 (ν, Θ-θ 2 ),

f 1 (Ω) = θ 1 (Ω) = θ 2 (Ω).
By triangular inequality and W 1 (Θθ 1 , Θθ 2 ) = W 1 (θ 1 , θ 2 ), we get

W 1 (f 1 + ν, Θ) + W 1 (f 2 + ν, Θ) = W 1 (f 1 , θ 1 ) + W 1 (ν, Θ -θ 1 ) + W 1 (f 2 , θ 2 ) + W 1 (ν, Θ -θ 2 ) ≥ W 1 (f 1 , θ 1 ) + W 1 (f 2 , θ 2 ) + W 1 (θ 1 , θ 2 ) ≥ max i=1,2 {W 1 (f 1 , θ i ) + W 1 (f 2 , θ i )} ≥ min i=1,2 {W 1 (f 1 , θ i ) + W 1 (f 2 , θ i )} ≥ min ρ∈M + b (Ω)
W 1 (f 1 , ρ) + W 1 (f 2 , ρ) : ρ ≤ Θ, ρ(Ω) = f 1 (Ω) .

(5.19)

Optimal Partial Transport and Constrained Matching Problems

Proofs of the equivalent formulations

Thus the proof of the equality (5.15) is done. At last, if ν is optimal then all the inequalities in (5.19) become equalities. This implies (5.16), (5.17) and (5.18).

Proof of Theorem 5.3. The duality (5.7) follows from Lemma 5.9, (5.14) and Lemma 5.10. It remains to show the optimality conditions (5.8) and (5.9). Let us begin with the proof of (5.8). For any admissible (u 1 , u 2 ) ∈ K and (γ 1 , γ 2 ) ∈ π(f 1 , f 2 ; Θ), taking ρ := π y #γ 1 = π y #γ 2 , we have

(u 1 + u 2 )dΘ -u 1 df 1 -u 2 df 2 ≤ (u 1 + u 2 )dρ -u 1 df 1 -u 2 df 2 = (u 1 (y) -u 1 (x)) dγ 1 + (u 2 (y) -u 2 (x)) dγ 2 ≤ |x -y|dγ 1 + |x -y|dγ 2 .
(5.20)

From the duality equalities (5.7), we deduce that (γ 1 , γ 2 ) and (u 1 , u 2 ) are optimal if and only if all the inequalities in (5. This condition is equivalent to (5.8).

For the proof of (5.9), we see that, for any admissible (Φ 1 , Φ 2 , ν) ∈ Ψ(f 1 , f 2 ; Θ), by the integration by parts formula, we have

-u 1 df 1 -u 2 df 2 + (u 1 + u 2 )dΘ ≤ -u 1 df 1 -u 2 df 2 + (u 1 + u 2 )d(Θ -ν) = u 1 d(Θ -ν -f 1 ) + u 2 d(Θ -ν -f 2 ) = Ω Φ 1 |Φ 1 | • ∇ |Φ 1 | u 1 d|Φ 1 |+ Ω Φ 2 |Φ 2 | • ∇ |Φ 2 | u 2 d|Φ 2 | ≤ |Φ 1 |(Ω) + |Φ 2 |(Ω).
(5.21)

Thanks to (5.7), (u 1 , u 2 ) and (Φ 1 , Φ 2 , ν) are optimal if and only if all the inequalities in (5.21) become equalities. This is equivalent to the system (5.9).

We end up this section by giving the proof of Theorem 5.7 concerning relation between (MMF) and (OM).

Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance Proof of Theorem 5.7. Assume that (Φ 1 , Φ 2 , ν) is optimal for (MMF) which implies that ν is optimal for the alternative formulation of (OM) given in Lemma 5.10. Take θ 1 and θ 2 given by Lemma 5.10. Then (5.16) and (5.17) mean that θ 2 is on a geodesic joining θ 1 to f 2 and θ 1 is on a geodesic joining θ 2 to f 1 . The assumption (H) imposes that θ 1 = θ 2 . To convince the reader, take γ f 1 ,1 , γ 1,2 and γ 2,f 2 the optimal plans from f 1 to θ 1 , from θ 1 to θ 2 and from θ 2 to f 2 . Using the gluing lemma (see e.g. [START_REF] Villani | Topics in Optimal Transportation[END_REF]Lemma 7.6]), we build γ f 1 ,1,2 obtained by gluing γ f 1 ,1 to γ 1,2 and γ 1,2,f 2 obtained by gluing γ 1,2 to γ 2,f 2 . Then, it holds

W 1 (f 1 , θ 1 ) + W 1 (θ 1 , θ 2 ) = Ω 3 |x 1 -z 1 |+|z 1 -z 2 |dγ f 1 ,1,2 (x 1 , z 1 , z 2 ) = W 1 (f 1 , θ 2 ) ≤ Ω 3 |x 1 -z 2 |dγ f 1 ,1,2 (x 1 , z 1 , z 2 ).
By triangular inequality and the continuity of the integrands, we get (5.23) If there exists (z 1 , z 2 ) ∈ supp(γ 1,2 ) such that z 1 = z 2 then, using (5.22) and (5.23), there are x 1 ∈ supp(f 1 ), x 2 ∈ supp(f 2 ) such that z 1 ∈ [x 1 , z 2 ], z 2 ∈ [z 1 , x 2 ] and therefore z 1 , z 2 ∈ [x 1 , x 2 ] (by z 1 = z 2 ), a contradiction with the assumption (H). This shows that θ 1 = θ 2 . At last, by (5.18), we obtain ν = Θ-θ i ≤ Θ, i = 1, 2.

Uniqueness of optimal matching measure

This section concerns the proof for the uniqueness of optimal matching measure. Let ρ be an optimal matching measure. Following Corollary 5.5 and Theorem 5.3, setting ν := Θρ, we have On the other hand, using the optimality of (u 1,h , u 2,h ), (Φ 1,h , Φ 2,h , ν h ) and the duality equality for (5.11), we have

         -∇ • Φ i = Θ -ν -f i in D ′ (R N ), i = 1, 2 Φ i |Φ i | = ∇ |Φ i | u i |Φ i |-
F h (u 1,h , u 2,h )+G h (Λ h (u 1,h , u 2,h )) = -F * h (-Λ * h (Φ 1,h , Φ 2,h , ν h ))-G * h (Φ 1,h , Φ 2,h , ν h ),
or more explicitly,

f 1,h , u 1,h + f 1,h , u 2,h -Θ h , u 1,h + u 2,h
=sup { Φ 1,h , q : q ∈ Y h , |q(x)|≤ 1, a.e. x ∈ Ω} sup { Φ 2,h , q : q ∈ Y h , |q(x)|≤ 1, a.e. x ∈ Ω} .

(5.30)

Using the boundedness of (u 1,h , u 2,h ), we obtain that Φ 1,h and Φ 2,h are bounded in L 1 (Ω) N . Thus, up to a subsequence,

(Φ 1,h , Φ 2,h , ν h ) ⇀ (Φ 1 , Φ 2 , ν) weakly* in M b (Ω) N × M b (Ω) N × M b (Ω).
Then (Φ 1 , Φ 2 , ν) is feasible for the problem (MMF). Indeed, thanks to (5.29) and the nonnegativity of ν h , we obtain that The optimal matching measure and optimal flows are given in Fig. Problèmes de transport partiel optimal et d'appariement avec contrainte Résumé : Cette thèse est consacrée à l'analyse mathématique et numérique pour les problèmes de transport partiel optimal et d'appariement avec contrainte (constrained matching problem). Ces deux problèmes présentent de nouvelles quantités inconnues, appelées parties actives. Pour le transport partiel optimal avec des coûts qui sont donnés par la distance finslerienne, nous présentons des formulations équivalentes caractérisant les parties actives, le potentiel de Kantorovich et le flot optimal. En particulier, l'EDP de condition d'optimalité permet de montrer l'unicité des parties actives. Ensuite, nous étudions en détail des approximations numériques pour lesquelles la convergence de la discrétisation et des simulations numériques sont fournies. Pour les coûts lagrangiens, nous justifions rigoureusement des caractérisations de solution ainsi que des formulations équivalentes. Des exemples numériques sont également donnés. Le reste de la thèse est consacré à l'étude du problème d'appariement optimal avec des contraintes pour le coût de la distance euclidienne. Ce problème a un comportement différent du transport partiel optimal. L'unicité de solution et des formulations équivalentes sont étudiées sous une condition géométrique. La convergence de la discrétisation et des exemples numériques sont aussi établis. Les principaux outils que nous utilisons dans la thèse sont des combinaisons des techniques d'EDP, de la théorie du transport optimal et de la théorie de dualité de Fenchel-Rockafellar. Pour le calcul numérique, nous utilisons des méthodes du lagrangien augmenté.

Φ 1 , ∇u + Φ 2 , ∇v + ν, u+v = -f 1 , u -f 2 , v + Θ, u+v ∀(u, v) ∈ V := C 1 (Ω)×C 1 (Ω),
Mots clés : Transport optimal, transport partiel optimal, problème d'appariement optimal, dualité de Fenchel-Rockafellar, équation de Monge-Kantorovich, doublant des variables, méthodes du lagrangien augmenté.

Optimal Partial Transport and Constrained Matching Problems

Abstract: The manuscript deals with the mathematical and numerical analysis of the optimal partial transport and optimal constrained matching problems. These two problems bring out new unknown quantities, called active submeasures. For the optimal partial transport with Finsler distance costs, we introduce equivalent formulations characterizing active submeasures, Kantorovich potential and optimal flow. In particular, the PDE of optimality condition allows to show the uniqueness of active submeasures. We then study in detail numerical approximations for which the convergence of discretization and numerical simulations are provided. For Lagrangian costs, we derive and justify rigorously characterizations of solution as well as equivalent formulations. Numerical examples are also given. The rest of the thesis presents the study of the optimal constrained matching with the Euclidean distance cost. This problem has a different behaviour compared to the partial transport. The uniqueness of solution and equivalent formulations are studied under geometric condition. The convergence of discretization and numerical examples are also indicated. The main tools which we use in the thesis are the combinations of PDE techniques, optimal transport theory and Fenchel-Rockafellar dual theory. For numerical computation, we make use of augmented Lagrangian methods.

Keywords: Optimal transport, optimal partial transport, optimal matching, Fenchel-Rockafellar duality, Monge-Kantorovich equation, doubling variables, augmented Lagrangian methods.

Fig. 1 :

 1 Fig. 1: The optimal mass transport problem

Theorem 0. 1 .

 1 Let µ, ν ∈ M + b (R N ) be Radon measures with compact supports and m ∈ [0, m max ]. Then the problem (PMK) with c = d F has an optimal plan σ * and the Kantorovich-Rubinstein type duality can be written as K(σ * ) = max (λ,u)∈[0,+∞)×L λ d F D(λ, u) := u d(νµ) + λ(mν(R N )) , (0.1)

.

  , u) : u ∈ L λ d F For any fixed λ ≥ 0, the primal-dual optimality condition associated with the maximization problem max u D(λ, u) : u ∈ L λ d F

  λ≥0 max u D(λ, u) : u ∈ L λ d F , General Introduction the measure θ λm defined by θ - λm := µρ 0 and θ + λm := νρ 1 ,is a solution of the OMK equation (P λm ).

Chapter 4 ,

 4 we extend our results to Lagrangian costs c = c L with c L (x, y) := inf ξ t), ξ(t))dt : ξ(0) = x, ξ(1) = y, ξ ∈ Lip([0, 1]; R N )

µ 2 Optimal

 2 Partial Transport and Constrained Matching Problems 1.2. Optimal Transport Φ |Φ| Radon-Nikodym derivative of Φ w.r.t. |Φ| supp(µ) the support of µ, i.e. the set {x ∈ X : µ(B(x, r)) > 0 ∀r > 0} π x , π y the projections on the first component and the second component, i.e. π x , π y defined on X × Y and π x (x, y) = x, π y (x, y) = y. T # µ the push-forward measure of µ by T L p µ the Lebesgue spaces w.r.t. µ δ x

Theorem 1 . 1 .

 11 (cf.[START_REF] Villani | Optimal Transport, Old and New[END_REF] Chapter 5]) Let c be an l.s.c. cost function and µ

Example 1 . 2 .

 12 (see e.g. [50, Theorem 3.1] or [21, Example 2.4]) Let η = H k S

1. 4 .

 4 Fenchel-Rockafellar duality and ALG2 method It remains to verify that

Theorem 2 . 1 .

 21 Let µ, ν ∈ M + b (R N ) be Radon measures with compact supports and m ∈ [0, m max ]. Then the PMK problem (PMK) with c = d F has an optimal plan σ * and the Kantorovich-Rubinstein type duality can be written as

Theorem 2 . 5 (

 25 Active submeasures and OMK equation). Let µ, ν ∈ M + b (R N ) be compactly supported. (i) For any λ ≥ 0 and θ λ a solution of the OMK equation (P λ ), the couple

Chapter 2 :

 2 Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

(2. 13 )

 13 Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation On the other hand, there is a sequence ε n → 0 such that lim sup ε→0 F * (x, Du ε (x)) = lim εn→0 F * (x, Du εn (x)).(2.14)

40

  Optimal Partial Transport and Constrained Matching ProblemsChapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

44

  Optimal Partial Transport and Constrained Matching ProblemsChapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

Chapter 2 :

 2 Optimal Partial Transport and Obstacle Monge-Kantorovich Equation Lemma 2.20. Let λ ≥ 0 and µ

  θ 1 and θ 2 have the same role, we obtain θ 1 = θ 2 . Now, we give the proof of Lemma 2.20. Let us consider the Lipschitz continuous function of real variable H ε (r) := min(r + /ε, 1) for any r ∈ R.

  Optimal Partial Transport and Constrained Matching Problems Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation and moreover,

Proposition 2 . 21 (

 221 Partial minimal flow problem). Let µ, ν ∈ M + b (R N ) be compactly supported. For any m ∈ [0, m max ], we have min {K(σ) : σ

Chapter 2 :

 2 Optimal Partial Transport and Obstacle Monge-Kantorovich Equation Corollary 2.22.

  Optimal Partial Transport and Constrained Matching ProblemsChapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

. 34 )

 34 We denote by E the set of right endpoints of maximal transport rays w.r.t. u. It is well-known that L N (E) = 0 (see e.g.[START_REF] Bernard | The Monge problem for supercritical Mané potentials on compact manifolds[END_REF] Corollary 15]). To prove (2.34), it is enough to show that supp(Φ)∩ [u = λ] ⊂ E.Assume on the contrary that there exists z ∈ supp(Φ) ∩ [u = λ] such that z / ∈ E.56Optimal Partial Transport and Constrained Matching Problems Chapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation From z ∈ supp(Φ), there is (x, y) ∈ supp(µ) × supp(ν) such that    u(y) = u(x) + d F (x, y) u(y) = u(z) + d F (z, y).

  where we used Lemma 2.24 and the absolute continuity of ν. Since u = λ θ + -a.e., we get θ + = ν [u=λ] . In the same way, we get θ -= µ [u=0]

Theorem 2 .

 2 [START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF] Theorem 3.4]) Let Γ m opt be the set of optimal transport plans of the mass m ≥ 0. There is a curve m ∈ [0, m max ] -→ γ m ∈ Γ m opt along which the left and right marginals γ m+ε dominate those of γ m whenever ε > 0.Proof of Proposition 2.25. (i) Set

  Optimal Partial Transport and Constrained Matching ProblemsChapter 2 : Optimal Partial Transport and Obstacle Monge-Kantorovich Equation

7 .

 7 The fact that m λ ∈ [(µ ∧ ν)(R N ), m max ] and the monotonicity of m λ are given in Lemma 2.26 while the continuity of m λ follows from the continuity of θ λ . Let us show the surjectivity of m λ . Fix any m ∈ [(µ ∧ ν)(R N ), m max ]. Let (ρ 0 , ρ 1 ) be a couple of active submeasures w.r.t. m. Taking λ := λ m as in Theorem 2.5 (ii), then m λ = m. Finally, for the properties of R, we use again Theorem 2.5 and Proposition 2.25.

Chapter 3 :Theorem 3 . 1 .

 331 Augmented Lagrangian Method for Optimal Partial Transport Following Chapter 2, to study the PMK problem we use the DPMK problem. Let µ, ν ∈ M + b (Ω) be Radon measures and m ∈ [0, m max ]. The PMK problem with c = d F has a solution σ * ∈ π m (µ, ν) and

Lemma 3 . 2 .

 32 Let Ω be a bounded Lipschitz domain and F be a continuous nondegenerate Finsler metric on Ω. For any Lipschitz continuous function u on Optimal Partial Transport and Constrained Matching Problems

3. 1 .

 1 Partial transport and its equivalent formulations Ω satisfying F * (x, ∇u(x)) ≤ 1 a.e. x ∈ Ω, (3.2)

  y)dy for all x ∈ R N , (3.5) Optimal Partial Transport and Constrained Matching Problems Chapter 3 : Augmented Lagrangian Method for Optimal Partial Transport where ρ ε is the standard mollifier on R N . Obviously, ũε ∈ C ∞ c (R N ). Using (3.4), (3.5) and the continuity of u on Ω, we get ũε ⇒ u on U z .

Lemma 3 . 3 .

 33 Let F be a continuous nondegenerate Finsler metric on a bounded Lipshitz domain Ω. Then the set of 1-d F Lipschitz functions coincides with the set B F * := u : Ω -→ R | u is Lipschitz and F * (x, ∇u(x)) ≤ 1 a.e. x ∈ Ω .

3. 1 .lim sup h→0 1 0F

 11 Partial transport and its equivalent formulations≤ (x + thv, hv)dt F (x, hv) = 1.

  2 and 3.3, for any 1-d F Lipschitz continuous function u, there exists a sequence of 1-d F Lipschitz continuous functions u ε ∈ C ∞ c (R N ) and u ε ⇒ u uniformly on Ω. By virtue of Lemma 3.3, the DPMK problem (3.1) can be written as max {D(λ, u) : 0 ≤ u(x) ≤ λ, u is Lipschitz continuous, F * (x, ∇u(x)) ≤ 1 a.e. x ∈ Ω} . Moreover, we have Theorem 3.4. Under the assumptions of Theorem 3.1, setting V := R × C 1 (Ω) and Z := C(Ω) N × C(Ω) × C(Ω), we have

Chapter 3 :

 3 Augmented Lagrangian Method for Optimal Partial Transport • Step 2:

Fig. 3 . 1 :

 31 Fig. 3.1: Illustration of the projection

Fig. 3 . 2 :Fig. 3 . 3 :

 3233 Fig. 3.2: Optimal flow for µ = 3, ν = δ (0.5,0.5) , F (x, v) = |v|.

2 .

 2 This corresponds to the crystalline norm with d 1 = (1, 1), d 2 = (-1, 1), d 3 = (-1, -1) and d 4 = (1, -1).

Fig. 3 . 4 :Fig. 3 . 5 :

 3435 Fig. 3.4: Optimal flow for µ = 3, ν = δ (0.5,0.5) , F (x, (v 1 , v 2 )) = |v 1 |+|v 2 |.

Fig. 3 . 7 :

 37 Fig. 3.7: Case 2: The crystalline case with d 1 = (1, 1), d 2 = (-1, 1), d 3 = (-1, -1) and d 4 = (1, -1).

Fig. 3 . 8 :

 38 Fig. 3.8: Case 3: The crystalline case withd 1 = (1, 0), d 2 = ( 1 5 , 1 5 ), d 3 = (-1 5 , 1 5 ), d 4 = (-1 5 , -1 5) and d 5 = (15 , -1 5 ) makes the transport more expensive in the direction of the vector (1, 0).

Fig. 3 . 9 :

 39 Fig. 3.9: Case 4: The crystalline case with d 1 = (1, -1), d 2 = (1, -4 5 ), d 3 = (-4 5 , 1), d 4 = (-1, 1) and d 5 = (-1, -1) makes the transport cheaper in the direction of the vector (1, 1).

Fig. 3

 3 Fig. 3.10: Optimal flows

( 4 . 10 )

 410 Optimal Partial Transport and Constrained Matching Problems

4. 2 .

 2 Uniqueness of active submeasures for any compactly supported smooth function φ ∈ C ∞ c (Q). As before, we denote (4.10) by

88

  Optimal Partial Transport and Constrained Matching ProblemsChapter 4: Optimal Partial Transport with Lagrangian costs Then π x #γ = ρ 0 and

Theorem 4 . 5 .

 45 Let µ, ν ∈ M + b (R N ) be compactly supported and m ∈ [0, m max ].Suppose that L satisfies the assumption (A). Then min γ∈πm(µ,ν)

Lemma 4 . 6 .

 46 Fix any u ∈ K λ c . There exists a sequence of smooth functions

4. 3 .

 3 Equivalent formulations using (4.15), we have u(1, y)u(0, x) = lim

  ε→0

φ 1 (

 1 x) := sup y∈supp(ν) (ψ(y)c(x, y)) and φ * (x) := max{φ 1 (x), -λ} for x ∈ supp(µ). Since c(., y) is locally Lipschitz w.r.t. the variable x, φ * is Lipschitz on the compact set supp(µ). Moreover, φ * is non-positive (since ψ ≤ 0 and c ≥ 0) and (φ * , ψ) is also a maximizer of the DPMK problem. By extension, we can assume that φ * is non-positive and Lipschitz on R N . Now, we setu * (t, x) := inf ξ s), ξ(s))ds + φ * (ξ(0)) : ξ ∈ Lip([0, t]; R N ), ξ(t) = x    .Then (see e.g.[START_REF] Evans | Partial Differential Equations[END_REF] Chapter 10] or [28, Chapter 6]) u * is Lipschitz on Q and u * is a viscosity solution of the Hamilton-Jacobi equation∂ t u(t, x) + H(x, ∇ x u(t, x)) = 0 with u * (0, x) = φ * (x). It is not difficult to see that u * (1, y) ≤ φ * (y) ≤ 0, u * (0, x) = 94Optimal Partial Transport and Constrained Matching Problems Chapter 4: Optimal Partial Transport with Lagrangian costs φ * (x) ≥ -λ ∀x, y ∈ R N and that u * (1, y) = inf ξ s), ξ(s))ds + φ * (ξ(0)) : ξ ∈ Lip([0, 1]; R N ), ξ(1) = y y) + φ * (x)} ≥ ψ(y) ∀y ∈ R N .

( 4 . 22 )

 422 Letting ε → 0, using Lemma 4.6 and the fact that u(1, .) ≤ 0, u(0, .) + λ ≥ 0, we 96Optimal Partial Transport and Constrained Matching Problems Chapter 4: Optimal Partial Transport with Lagrangian costs have

Chapter 4 :

 4 Optimal Partial Transport with Lagrangian costs

  λ ) where the condition θ 1 ∈ ∂I (-∞,0] (u(1, .)) means that u(1, .) ≤ 0 and θ 1 , φu(1, .) ≤ 0 ∀φ ∈ C b (R N ), φ ≤ 0, or equivalently u(1, .) ≤ 0, θ 1 ≥ 0 and R N u(1, .)dθ 1 = 0.

Lemma 4 . 11 .

 411 Let u be a Lipschitz function on Q and ∂ t u(t, x)+H(x, ∇ x u(t, x)) ≤ 0 a.e. (t, x) ∈ Q. For any (ρ, υ) ∈ M + b

(4. 26 ) 1 .

 261 From the assumptions on optimalities and the duality (4.20), the inequalities Optimal Partial Transport and Constrained Matching Problems4.4. Numerical approximation in (4.26) become equalities. These imply that Q∇ ρ u • (1, υ)dρ = Q L(x, υ(t, x))dρ,or equivalently L(x, υ(t, x)) = ∇ ρ u(t, x) • (1, υ(t, x)) ρ-a.e. in Q (byLemma 4.

Remark 4 .

 4 [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF]. A solution (Φ * , θ 0 * , θ 1 * ) of the Fenchel-Rockafellar dual formulation (4.24) gives a couple of inactive submeasures and therefore active submeasures ρ * 0 = µθ 0 * and ρ * 1 = νθ 1 * .

Chapter 4 :

 4 Optimal Partial Transport with Lagrangian costs

Example 4 . 13 .

 413 The source and the target are Gaussian distributions of the same mass for the Lagrangian L(x, v) = |v| 2 . We want to transport optimally a half of Chapter 4: Optimal Partial Transport with Lagrangian costs the mass. More details, µ = 10 exp(-40(x 1 -0.25) 2 -40(x 2 -0.75) 2 ), ν = 10 exp(-40(x 1 -0.75) 2 -40(x 2 -0.25) 2 ).

Fig. 4 . 1 :

 41 Fig. 4.1: Active submeasures and their displacement

110

  Optimal Partial Transport and Constrained Matching ProblemsChapter 5: Optimal Constrained Matching Problem for the Euclidean Distance

Fig. 5 . 1 :

 51 Fig. 5.1: Example of ν Θ

inf (u 1

 1 ,u 2 )∈C 1 (Ω)×C 1 (Ω) F(u 1 , u 2 ) + G(Λ(u 1 , u 2 )) = max (Φ 1 ,Φ 2 ,ν)∈M b (Ω) N ×M b (Ω) N ×M b (Ω) {-F * (-Λ * (Φ 1 , Φ 2 , ν)) -G * (Φ 1 , Φ 2 , ν)} .

min |Φ 1 W 1 W 1

 111 |(Ω) + |Φ 2 |(Ω) : (Φ 1 , Φ 2 , ν) ∈ Ψ(f 1 , f 2 ; Θ) (f 1 + ν, Θ) + W 1 (f 2 + ν, Θ) : ν(Ω) = Θ(Ω)f 1 (Ω) . (5.14)This proposes an alternative formulation of (OM) that we prove directly in the following lemma.118Optimal Partial Transport and Constrained Matching Problems Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance Lemma 5.10. Assume that f 1 , f 2 , Θ ∈ M + b (Ω) are Radon measures. We have min ρ∈M + b (Ω)W 1 (f 1 , ρ) + W 1 (f 2 , ρ) : ρ ≤ Θ, ρ(Ω) = f 1 ((f 1 + ν, Θ) + W 1 (f 2 + ν, Θ) : ν(Ω) = Θ(Ω)f 1 (Ω) .

  )

(u 1 + 1 (u 2

 112 u 2 ) dΘ = (u 1 + u 2 ) dρ (u 1 (y)u 1 (x)) dγ 1 = |x -y|dγ (y)u 2 (x)) dγ 2 = |x -y|dγ 2 .

|x 1 -

 1 z 1 |+|z 1z 2 |= |x 1z 2 |, i.e., z 1 ∈ [x 1 , z 2 ] for all (x 1 , z 1 , z 2 ) ∈ supp(γ f 1 ,1,2 ).

(5. 22 )

 22 In the same way,|z 1z 2 |+|z 2x 2 |= |z 1x 2 |, i.e., z 2 ∈ [z 1 , x 2 ] for all (z 1 , z 2 , x 2 ) ∈ supp(γ 1,2,f 2 ).

  . the feasibility of (Φ 1 , Φ 2 , ν). Now, we show the optimality of (u * 1 , u * 2 ) and (Φ 1 , Φ 2 , ν). Thanks to Theorem 5.3, it is sufficient to show thatf 1 , u * 1f 2 , u * 2 + Θ, u * 1 + u * 2 ≥ |Φ 1 |(Ω) + |Φ 2 |(Ω).(5.31)5.6. Numerical experimentsExample 5.15. We takef 1 = 4χ [(x-0.2) 2 +(y-0.8) 2 <0.01] , f 2 = 2χ [(x-0.8) 2 +(y-0.8) 2 <0.01] + 2χ [(x-0.2) 2 +(y-0.2) 2 <0.01] , Θ = 4χ [(x-0.5) 2 +(y-0.5) 2 <0.04] .

  5.3. Stopping criterion is given in Fig. 5.4.

Fig. 5 . 3 :

 53 Fig. 5.3: Optimal matching measure and optimal flows

Fig. 5 . 5 :

 55 Fig. 5.5: Optimal matching measure and optimal flows

Fig. 5 . 7 :

 57 Fig. 5.7: Optimal matching measure and optimal flows

Fig. 5 . 8 :

 58 Fig. 5.8: Stopping criterion

  R N . Thanks to Lemma 2.16, this is equivalent to Since Φ λn → Φ weakly* in M b (R N ) N , we have (see e.g. [2, Theorem 2.38])

								2.6. Monotonicity
	R N	F (x,	Φ |Φ|	(x))d|Φ|≤	R N	Φ |Φ|	(x)∇ |Φ| u(x)d|Φ|.	(2.38)
	Optimal Partial Transport and Constrained Matching Problems	59

  .1. Case 1: F (x, v) = |v|.

	Chapter 3 : Augmented Lagrangian Method for Optimal Partial Transport
		IsoValue
		-4.21111
		-3.74444
		-3.27778
		-2.81111
		-2.34444
		-1.87778
		-1.41111
		-0.944444
		-0.477778
		-0.0111111
		0.455556
		0.922222
		1.38889
		1.85556
		2.32222
		2.78889
		3.25556
		3.72222
		4.18889
		4.65556
		Vec Value
		0
		0.0369496
		0.0738992
		0.110849
		0.147798
		0.184748
		0.221697
		0.258647
		0.295597
		0.332546
		0.369496
		0.406445
		0.443395
		0.480345
		0.517294
		0.554244
		0.591193
		0.628143
		0.665092
	(a) The unit ball of F	0.702042
	(b) Optimal flow
	Fig. 3.6: (a) The unit ball of F	IsoValue -4.21111 -3.74444 -3.27778 -2.81111 -2.34444 -1.87778 -1.41111 -0.944444 -0.477778 -0.0111111 0.455556 0.922222 1.38889 1.85556 2.32222 2.78889 3.25556 3.72222 4.18889 4.65556 Vec Value 0 0.0308273 0.0616546 0.0924819 0.123309 0.154137 0.184964 0.215791 0.246619 0.277446 0.308273 0.3391 0.369928 0.400755 0.431582 0.46241 0.493237 0.524064 0.554892 0.585719
	(b) Optimal flow

  3.10.

	Chapter 4: Optimal Partial Transport with Lagrangian costs
	IsoValue -2.11111 -1.88889 -1.66667 -1.44444 -1.22222 -1 -0.777778 -0.555556 -0.333333 -0.111111 0.111111 0.333333 0.555556 0.777778 1 1.22222 1.44444 1.66667 1.88889 2.11111	IsoValue -2.11111 -1.88889 -1.66667 -1.44444 -1.22222 -1 -0.777778 -0.555556 -0.333333 -0.111111 0.111111 0.333333 0.555556 0.777778 1 1.22222 1.44444 1.66667 1.88889 2.11111	IsoValue -2.11111 -1.88889 -1.66667 -1.44444 -1.22222 -1 -0.777778 -0.555556 -0.333333 -0.111111 0.111111 0.333333 0.555556 0.777778 1 1.22222 1.44444 1.66667 1.88889 2.11111
	Vec Value 0 0.00883173 0.0176635 0.0264952 0.0353269 0.0441586 0.0529904 0.0618221 0.0706538 0.0794856 0.0883173 0.097149 0.105981 0.114812 0.123644 0.132476 0.141308 0.150139 0.158971 0.167803	Vec Value 0 0.0127298 0.0254596 0.0381893 0.0509191 0.0636489 0.0763787 0.0891084 0.101838 0.114568 0.127298 0.140028 0.152757 0.165487 0.178217 0.190947 0.203676 0.216406 0.229136 0.241866	Vec Value 0 0.0167022 0.0334044 0.0501066 0.0668088 0.083511 0.100213 0.116915 0.133618 0.15032 0.167022 0.183724 0.200426 0.217129 0.233831 0.250533 0.267235 0.283938 0.30064 0.317342
	(a) m 1	(b) m 2	(c) m 3
	IsoValue -2.11111 -1.88889 -1.66667 -1.44444 -1.22222 -1 -0.777778 -0.555556 -0.333333 -0.111111 0.111111 0.333333 0.555556 0.777778 1 1.22222 1.44444 1.66667 1.88889 2.11111	IsoValue -2.11111 -1.88889 -1.66667 -1.44444 -1.22222 -1 -0.777778 -0.555556 -0.333333 -0.111111 0.111111 0.333333 0.555556 0.777778 1 1.22222 1.44444 1.66667 1.88889 2.11111	IsoValue -2.11111 -1.88889 -1.66667 -1.44444 -1.22222 -1 -0.777778 -0.555556 -0.333333 -0.111111 0.111111 0.333333 0.555556 0.777778 1 1.22222 1.44444 1.66667 1.88889 2.11111
	Vec Value 0 0.0219044 0.0438088 0.0657132 0.0876176	Vec Value 0 0.0254916 0.0509833 0.0764749 0.101967	Vec Value 0 0.031821 0.063642 0.095463 0.127284
	0.109522	0.127458	0.159105
	0.131426	0.15295	0.190926
	0.153331	0.178441	0.222747
	0.175235	0.203933	0.254568
	0.197139	0.229425	0.286389
	0.219044	0.254916	0.31821
	0.240948	0.280408	0.350031
	0.262853	0.3059	0.381852
	0.284757	0.331391	0.413673
	0.306661	0.356883	0.445494
	0.328566	0.382375	0.477315
	0.35047	0.407866	0.509136
	0.372375	0.433358	0.540957
	0.394279	0.45885	0.572778
	0.416183	0.484341	0.604599
	(d) m 4	(e) m 5	(f ) m 6

  .17) 92 Optimal Partial Transport and Constrained Matching Problems Chapter 4: Optimal Partial Transport with Lagrangian costs Letting ε → 0, we obtain (4.14). Next, let us fix any ξ ∈ Lip([0, 1]; R N ). Using (4.14) with x = ξ(t), v = ξ(t), we have u ε (t, ξ(t)) + ∇ x u ε (t, ξ(t)), ξ(t) ≤ L(ξ(t), ξ(t)) for a.e. t ∈ [0, 1]. (4.18)

	lim sup

ε→0

∂ t

  for a.e. t ∈ [0, 1] are bounded by a common constant depending Lipschitz constants of u and of ξ. Applying the Reverse Fatou's

	Lemma and (4.18), we deduce that
	1
	lim sup
	ε→0
	0

  Optimal Partial Transport and Constrained Matching Problems Chapter 4: Optimal Partial Transport with Lagrangian costs we have ∇ ρ u(t, x) • (1, υ(t, x)) ≤ L(x, υ(t, x)) ρ-a.e. (t, x) in Q. Proof. Let u ε be the sequence as in Lemma 4.6. Since -div t,x (ρ, υρ) = δ 1 ⊗ ρ 1δ 0 ⊗ ρ 0 , we see that (1, υ(t, x)) ∈ T ρ (t, x) for ρ-a.e. (t, x), where T ρ (t, x) is the tangential space w.r.t. ρ. Using Lemma 4.6 and the continuity of the tangential gradient operator (see e.g. Chapter 1 or [62, Proposition 4.5]), we have

  25) 2 -40(x 2 -0.75) 2 ).

	The result is given in Figure 4.2. IsoValue -0.526316 0.263158 0.789474 1.31579 1.84211 2.36842 2.89474 3.42105 3.94737 4.47368 5 5.52632 6.05263 6.57895 7.10526 7.63158 8.15789 8.68421 9.21053 10.5263 Source Timestep 0 IsoValue -0.264929 0.116464 0.370725 0.624987 0.879249 1.13351 1.38777 1.64203 1.8963 2.15056 2.40482 2.65908 2.91334 3.1676 3.42187 3.67613 3.93039 4.18465 4.43891 5.07457 Timestep 3 Timestep 4 IsoValue -0.277858 0.122348 0.389152 0.655956 0.922759 1.18956 1.45637 1.72317 1.98997 2.25678 2.52358 2.79039 3.05719 3.32399 3.5908 3.8576 4.1244 4.39121 4.65801 Timestep 7 Timestep 8 Optimal Partial Transport and Constrained Matching Problems 4.5. Some examples IsoValue -0.430252 0.0908771 0.438296 0.785716 1.13314 1.48055 1.82797 2.17539 2.52281 2.87023 3.21765 3.56507 3.91249 4.25991 4.60733 4.95475 5.30217 5.64959 5.99701 6.86555 IsoValue -0.302817 0.136771 0.42983 0.722888 1.01595 1.30901 1.60206 1.89512 2.18818 2.48124 2.7743 3.06736 3.36042 3.65347 3.94653 4.23959 4.53265 4.82571 5.11877 5.85141 Timestep 1 IsoValue -0.276234 0.124799 0.392154 0.65951 0.926865 1.19422 1.46158 1.72893 1.99629 2.26364 2.531 2.79835 3.06571 3.33306 3.60042 3.86778 4.13513 4.40249 4.66984 5.33823 Timestep 2 IsoValue -0.256217 0.113175 0.359436 0.605697 0.851958 1.09822 1.34448 1.59074 1.837 2.08326 2.32952 2.57579 2.82205 3.06831 3.31457 3.56083 3.80709 4.05335 4.29961 4.91527 IsoValue -0.256183 0.112651 0.358541 0.60443 0.85032 1.09621 1.3421 1.58799 1.83388 2.07977 2.32566 2.57155 2.81744 3.06332 3.30921 3.5551 3.80099 4.04688 4.29277 4.9075 Timestep 5 IsoValue -0.263155 0.117339 0.371001 0.624664 0.878326 1.13199 1.38565 1.63931 1.89298 2.14664 2.4003 2.65396 2.90763 3.16129 3.41495 3.66861 3.92228 4.17594 4.4296 5.06376 Timestep 6 IsoValue -0.302171 0.136641 0.429183 0.721724 1.01427 1.30681 1.59935 1.89189 2.18443 2.47697 2.76951 3.06206 3.3546 3.64714 3.93968 4.23222 4.52476 4.8173 5.10985 IsoValue -0.384869 0.135835 0.48297 0.830106 1.17724 1.52438 1.87151 2.21865 2.56578 2.91292 3.26005 3.60719 3.95433 4.30146 4.6486 4.99573 5.34287 5.69 6.03714 Timestep 9 IsoValue -0.526316 0.263158 0.789474 1.31579 1.84211 2.36842 2.89474 3.42105 3.94737 4.47368 5 5.52632 6.05263 6.57895 7.10526 7.63158 8.15789 8.68421 9.21053 5.32502 5.8412 6.90498 10.5263

Target Fig. 4.2: Active submeasures and their displacement Example 4.15. In this example, we take L

  Optimal Partial Transport and Constrained Matching Problems 5.5. Numerical analysis for the problem ν h ∈ ∂I {z∈E h :z≤0} (u 1,h + u 2,h ), we get ν h ≥ 0 and u 1,h + u 2,h , ν h = 0. Since ν h = 0, there exists x h ∈ Ω such that u 1,h (x h ) + u 2,h (x h ) = 0. Combining this with the fact u 1,h = u 2,h , we imply that {u 1,h } and {u 2,h } are bounded in C(Ω). Since u 1,h , u 2,h are 1-Lipschitz functions, up to a subsequence (using the Ascoli-Arzela Theorem),u 1,h ⇒ u * 1 , u 2,h ⇒ u * 2 uniformly on Ω.It is clear that u * 1 , u * 2 are 1-Lipschitz and u * 1 + u * 2 ≤ 0 on Ω.

a.e. in Ω, i = 1, 2 u 1 + u 2 = 0 ν-a.e. in Ω,

(5.24)

The supports of active submeasures are called active regions in[START_REF] Caffarelli | Free boundaries in optimal transport and Monge-Ampère obstacle problems[END_REF][START_REF] Figalli | The optimal partial transport problem[END_REF].

Optimal Partial Transport and Constrained Matching Problems

> 1. It is known that if u ∈ C 1 (R N ) then u(y)u(x) ≤ d F (x, y) ∀x, y ∈ R N if and only if F * (x, ∇u(x)) ≤ 1 ∀x ∈ R N .Optimal Partial Transport and Constrained Matching Problems

Optimal Partial Transport and Constrained Matching Problems

Remerciements

4.2. Uniqueness of active submeasures density 1 w.r.t. A. We see that B c 0 = (Leb(µ) ∩ Leb(ν) ∩ Leb(ρ 0 )) c ∪ ({ρ 0 < µ} (1) ) c = Z ∪ {ρ 0 = µ}, with L N (Z) = 0. So ρ 0 = µ a.e. on B c 0 . Next, we show that ρ 0 = 0 on B 0 . Indeed, if ρ 0 (x) > 0 for some x ∈ B 0 then x ∈ supp(ρ 0 ). Hence there exists y ∈ supp(ρ 1 ) such that (x, y) ∈ supp(γ) for some optimal plan γ ∈ π(ρ 0 , ρ 1 ). Since µ ∧ ν = 0, we can take y = x and thus R := c(x, y) = L(yx) > 0. Since B c (y, R) is convex, it has the cone property, i.e. there is a finite cone with vertex at x contained in B c (y, R). It follows that there exists a sequence of subsets of B c (y, R) shrinking to x nicely (see e.g. [START_REF] Rudin | Real and complex analysis[END_REF]Theorem 7.10]). Using Lemma 4.2, ρ 0 = µ a.e. on B c (y, R), we obtain ρ 0 (x) = µ(x), which is impossible. Consequently, the proof of the expression ρ 0 = χ B c 0 µ is completed. In much the same way, we get ρ 1 = χ B c 1 ν.

Proof of Theorem 4.1. Let (ρ 0 , ρ 1 ) and (ρ 0 , ρ1 ) be couples of active submeasures. By Lemma 4.3, we have ρ 0 = χ B c 0 µ, ρ 1 = χ B c 1 ν, ρ0 = χ Bc 0 µ and ρ1 = χ Bc 1 ν. By the convexity of the total cost, we see that 1 2 (ρ 0 , ρ 1 ) + 1 2 (ρ 0 , ρ1 ) is also an optimal couple. If (ρ 0 , ρ 1 ) = (ρ 0 , ρ1 ) then 1 2 (ρ 0 , ρ 1 )+ 1 2 (ρ 0 , ρ1 ) does not admit any expression as in Lemma 4.3, a contradiction. Remark 4.4. (i) Following the proof, Theorem 4.1 is still true for any general cost c (not necessary to be of the form c L ) if we have the following properties:

• c is continuous.

• c(x, y) = 0 if and only if x = y.

• The balls w.r.t. c defined by B c (y, R) := {t ∈ R N : c(t, y) < R} and B c (x, R) := {w ∈ R N : c(x, w) < R)} are regular in the sense that given any point on the boundary of a ball, there exists a sequence of subsets of the ball which shrinks nicely to that point.

(ii) In the case where L(x, v) = L(v) is strictly convex, Figalli [START_REF] Figalli | The optimal partial transport problem[END_REF] studied the strict convexity of the function that associates to each m ∈ (µ ∧ ν(R N ), m max ] the total Monge-Kantorovich cost to deduce the uniqueness.

(iii) When L(x, .) is positively 1-homogeneous, i.e., L(x, tv) = tL(x, v) ∀x ∈ R N , v ∈ R N , t > 0, the uniqueness can be obtained via PDE techniques applied to the OMK equation (see Chapter 2).

Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance for any smooth compactly supported function φ ∈ C ∞ c (R N ). Our main result concerning duality and quivalent formulations is summarized in the following theorem.

Theorem 5.3. Let f 1 , f 2 , Θ be Radon measures. We have

(5.7) Moreover, we have that

f 2 ; Θ) and (u 1 , u 2 ) ∈ K are optimal for the optimal constrained matching problem (5.1) and the maximization problem (5.6), respectively, if and only if

(5.8)

f 2 ; Θ) are optimal for (5.6) and (MMF), respectively, if and only if the following system holds

(5.9)

Remark 5.4. If Θ is absolutely continuous, the optimality condition (5.9) can be simplified by using the usual gradient instead of the tangential gradient. In fact, in this case, it is known that Φ i is also absolutely continuous (see for instance [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF]) and that u is then differentiable |Φ i |-a.e.. By regularization via convolution, we can use u as test function in the first equation of (5.9), and using the duality (5.7), we get

Roughly speaking, the dual maximization formulation (5.6), the problem (MMF) and the system (5.9) correspond to (5.2), (5.3) and the optimality condition (5.4), respectively. In the optimal mass transportation problem, these three formulations contain all the informations concerning the optimal transportation.

Optimal Partial Transport and Constrained Matching Problems

Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance Before ending up this section let us show how we use the ALG2 method to solve numerically the optimal matching problem (OM). For any u = (u 1 , u 2 ) ∈

and for any (p, q, s)

Then the problem inf u∈V

provides all informations on the optimal matching problem. Indeed, u 1 , u 2 give Kantorovich potentials and dual variables Φ 1 , Φ 2 , ν give information on optimal flows and optimal matching measure. To solve numerically the problem (5.10) and its Fenchel-Rockafellar dual formulation (MMF), we consider a regular triangulation T h of Ω. As before, we fixe an integer k ≥ 1, and we consider P k the set of polynomials of degree less or equal than k. Let E h ⊂ H 1 (Ω) be the space of continuous functions on Ω and belonging to P k on each triangle of T h . We denote by Y h the space of vectorial functions such that their restrictions belong to (P k-1 ) N on each triangle of

We approximate the problem (5.10) by the following finite-dimensional problem: For any (u

The finite-dimensional approximation of (5.10) is given by Optimal Partial Transport and Constrained Matching Problems

(5.11)

Note that the cost functional does not change under the translation ũ1 :=

In particular, the new couple

The next theorem shows that (5.11) is a suitable approximation of (5.10) in the sense that primal and dual solutions converge to a solution of (5.10) (i.e., a solution of the maximization problem (5.6)) and a solution of (MMF).

Theorem 5.8. Let (u 1,h , u 2,h ) ∈ V h be an optimal solution to the approximated problem (5.11)

h , ν h ) be an optimal dual solution to (5.11). Then, up to a subsequence, (u 1,h , u 2,h ) converges uniformly to (u * 1 , u * 2 ) an optimal solution of the dual maximization problem (5.6) and (Φ 1,h , Φ 2,h , ν h ) converges weakly* to (Φ 1 , Φ 2 , ν) an optimal solution of (MMF).

At last, we solve the finite-dimensional problem (5.11). The details of the method are given in section 5.5. Here, we just give an illustration of our numerical results on the following example (see Fig.

Proofs of the equivalent formulations

The present section deals with the proofs of dual formulations as well as the connection between the minimal matching flow and the optimal constrained matching problem. To begin with, let us recall that for

(5.12)

Optimality condition reads as

Coming back to the optimal constrained matching problem, we start with the Fenchel-Rockafellar duality between (5.6) and (MMF). Lemma 5.9. Let f 1 , f 2 , Θ ∈ M + b (Ω) be Radon measures. We have

Keeping in mind the use of augmented Lagrangian methods for numerical approximation, we use the Fenchel-Rockafellar duality to prove Lemma 5.9.

Proof of Lemma 5.9. We observe that, using the standard smooth approximation by convolution,

Optimal Partial Transport and Constrained Matching Problems

where Φ i and u i are optimal flows and Kantorovich potentials, respectively. To prove the uniqueness of optimal matching measures under the assumption (H), we establish precise expression of ν w.r.t. Θ and u i , for i = 1, 2. More precisely, we have (5.24). Under the assumption (H), we have ν ≤ Θ and

where the set

The proof of this result follows as a consequence of the following lemmas.

Lemma 5.12. Let u, v be 1-Lipschitz functions on Ω such that u + v ≤ 0 on Ω. Assume that u(y 1 )-u(x 1 ) = |y 1 -x 1 | and that u(z)+v(z) = 0 for some z ∈ [x 1 , y 1 ] the segment joining x 1 to y 1 . Then

(5.25)

, then z, y 1 and x 2 are aligned.

Proof. We first prove that we get, for x 2 as in the hypothesis,

This implies that z, y 1 and x 2 are aligned.

We need the following behaviors of f i and Φ

is the Lebesgue measure on R N .

Proof. (i) Thanks to Theorem 5.7, we have ν ≤ Θ. Let us show that f 1 [u 1 + u 2 = 0] = 0. Assume on the contrary that the conclusion is not true. Then there exist x 1 ∈ [u 1 + u 2 = 0] and y 1 ∈ supp(Θν) such that (x 1 , y 1 ) ∈ supp(γ 1 ), where γ 1 is the optimal plan from f 1 to Θν. Since u 1 is a Kantorovich potential for W 1 (f 1 , Θν), we get

Similarly, since y 1 ∈ supp(Θν), there is

By Lemma 5.12, we deduce that x 1 , y 1 , x 2 are aligned which contradicts with (H).

In much the same way, we get f 2 [u 1 + u 2 = 0] = 0.

(ii) Now, we prove that Assume on the contrary that there exists z ∈ supp(Φ 1 )

and u 1 (y 1 ) = u 1 (x 1 ) + |y 1x 1 |. On the other hand, since y 1 ∈ supp(Θν), there exists x 2 ∈ supp(f 2 ) such that

Since u 1 (z) + u 2 (z) = 0, using Lemma 5.12, we deduce that z, y 1 and x 2 are on a straight line. Thus x 1 , y 1 and x 2 are aligned (by z ∈ [x 1 , y 1 [). This is again a contradiction with (H).

Proof of Proposition 5.11. We use notations of the above lemmas. By Theorem 5.7, we have ν ≤ Θ. Following directly from the PDE (5.24), we have

This implies that the measure 2(Θν)

In particular, 2(Θν)

. Since (Θν) ∈ L 1 , using Lemma 5.13 (ii) and the fact that supp(

in Ω, we deduce that

We can now conclude the proof for the uniqueness of optimal matching measures with the following arguments.

124

Optimal Partial Transport and Constrained Matching Problems Proof of Theorem 5.1. We fix a maximizer (u 1 , u 2 ) of the maximization problem (5.6). Then if ρ 1 and ρ 2 are optimal matching measures then ν i := Θρ i , i = 1, 2 satisfies the PDE (5.24). Thanks to Proposition 5.11, we get

Remark 5.14. Following from the proof, the unique optimal matching measure has the form

for any maximizer (u 1 , u 2 ) of the dual problem (5.6).

Numerical analysis for the problem

The present section concerns on numerical aspects of the matching problem.

Convergence of the discretization

Proof of Theorem 5.8. The optimality condition of (5.11) is

Writing these in detail, we have

Choosing test functions u ≡ 1, v ≡ 0 in (5.29) and using the fact that f 1,h (Ω) < Θ h (Ω), we have that ν h = 0 and {ν h } is bounded in L 1 (Ω). Since

Optimal Partial Transport and Constrained Matching Problems To this aim, let q 1 , q 2 ∈ C(Ω) N be such that |q 1 (x)|≤ 1, |q 2 (x)|≤ 1 ∀x ∈ Ω and q 1,h , q 2,h ∈ Y h be such that q i,hq i L ∞ (Ω) → 0 as h → 0, i = 1, 2. By the fact that

and, taking

1+O(h) if necessary, we can assume that q i,h ∈ Y h , |q i,h (x)|≤ 1 a.e. x ∈ Ω and q i,hq i L ∞ (Ω) → 0 as h → 0, i = 1, 2.

We see that

Similarly,

Combining these with (5.30) gives

Letting h → 0 and taking supremum in q 1 , q 2 , we get the inequality (5.31).

Solving the discretized problem

Our task is now to solve the finite-dimensional problem (5.11). We use the ALG2 method (see Chapter 1) to our discretized problem (5.11). To simplify the notations, let us drop out the subscript

Optimal Partial Transport and Constrained Matching Problems 127 5.5. Numerical analysis for the problem

• Step 3:

Let us give more details of the above iteration.

• In Step 1: We split the variables u 1 and u 2 , i.e. first minimizing w.r.t. u 1 and using u i+1

This is a quadratic problem with the associated linear equation:

• In Step 2: Since the function G(p, q, s) has the form of G 1 (p) + G 2 (q) + G 3 (s), we solve them separately. This is computed in pointwise, i.e., at vertices x k of a given grid,

128

Optimal Partial Transport and Constrained Matching Problems

Chapter 5: Optimal Constrained Matching Problem for the Euclidean Distance 2. For p i+1 and q i+1 , similarly, at each vertice x l , p i+1 (x l ) = Proj B(0,1) ∇u i+1 1 (x l ) + Φ i 1 (x l ) r and q i+1 (x l ) = Proj B(0,1) ∇u i+1 2 (x l ) + Φ i 2 (x l ) r .

Numerical experiments

We base on [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF][START_REF] Benamou | Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations[END_REF][START_REF] Igbida | Augmented Lagrangian method for optimal partial transportation[END_REF]] and on FreeFem++ [START_REF] Hecht | New development in Freefem++[END_REF] to give some numerical examples. We use P 2 finite element for u i 1 , u i 2 , s i , ν i and P 1 finite element for Φ i 1 , Φ i 2 , p i , q i .

Stopping criterion

The measures f 1 , f 2 and Θ are approximated by nonnegative regular functions that we denote again by f 1 , f 2 and Θ. We use the PDE of optimality condition as stopping criteria: 3. DIV := Div 1 +Div 2

2

, where

4. DUAL := Dual 1 +Dual 2

2

, with

We expect that MIN ≥ 0, Lip ≤ 1; DIV and DUAL are small.

Some examples

In all the examples below, we take Ω = [0, 1] × [0, 1] and work on a grid 60 × 60. Computation time for each example is about 8 minutes on a PC Mac OSX 10.9.