×

On the uniqueness and numerical approximations for a matching problem. (English) Zbl 1381.49029

Summary: The paper deals with some theoretical and numerical aspects for an optimal matching problem with constraints. It is known that the uniqueness of the optimal matching measure does not hold even with \(L^p\) sources and targets. In this paper, the uniqueness is proven under geometric conditions. On the other hand, we also introduce a dual formulation with a linear cost functional on a convex set and show that its Fenchel-Rockafellar dual formulation gives the right solution to the optimal matching problem. Basing on our formulations, a numerical approximation is given via an augmented Lagrangian method. We compute at the same time the optimal matching measure, optimal flows, and Kantorovich potentials. The convergence of the discretization is also studied in detail.

MSC:

49M25 Discrete approximations in optimal control
49Q20 Variational problems in a geometric measure-theoretic setting
65M60 Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs
65K10 Numerical optimization and variational techniques
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
49N15 Duality theory (optimization)

Software:

FreeFem++
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Ambrosio, {\it Lecture Notes on Optimal Transport Problems}, Lecture Notes Math. 1812, Springer, Berlin, 2003, pp. 1-52. · Zbl 1047.35001
[2] L. Ambrosio and A. Pratelli, {\it Existence and Stability Results in the \({L}^1\) Theory of Optimal Transportation}, Lecture Notes Math. 1813, Springer, Berlin, 2003, pp. 123-160. · Zbl 1065.49026
[3] J. W. Barrett and L. Prigozhin, {\it Partial \({L}^1\) Monge-Kantorovich problem: Variational formulation and numerical approximation}, Interfaces Free Bound., 11 (2009), pp. 201-238. · Zbl 1219.35371
[4] J. Benamou and Y. Brenier, {\it A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem}, Numer. Math., 84 (2000), pp. 375-393. · Zbl 0968.76069
[5] J. D. Benamou and G. Carlier, {\it Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations}, J. Optim. Theory Appl., 167 (2015), pp. 1-26. · Zbl 1326.49074
[6] G. Bouchitté, G. Buttazzo, and P. Seppercher, {\it Energies with respect to a measure and applications to low dimensional structures}, Calc. Var. Partial Differ. Equ., 5 (1997), pp. 37-54. · Zbl 0934.49011
[7] G. Carlier, {\it Duality and existence for a class of mass transportation problems and economic applications}, Adv. Math. Econ., 5 (2003), pp. 1-21. · Zbl 1176.90409
[8] G. Carlier and I. Ekeland, {\it Matching for teams}, Econom. Theory, 42 (2010), pp. 397-418. · Zbl 1183.91112
[9] P. A. Chiappori, R. J. McCann, and L. P. Nesheim, {\it Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness}, Econom. Theory, 42 (2010), pp. 317-354. · Zbl 1183.91056
[10] J. Eckstein and D. P. Bertsekas, {\it On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators}, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073
[11] I. Ekeland, {\it An optimal matching problem}, ESAIM Control Optim. Calc. Var., 11 (2005), pp. 57-71. · Zbl 1106.49054
[12] I. Ekeland and R. Teman, {\it Convex Analysis and Variational Problems}, North-Holland, Amsterdam, 1976.
[13] L. C. Evans and W. Gangbo, {\it Differential equations methods for the Monge-Kantorovich mass transfer problem}, Mem. Amer. Math. Soc., 137, 1999. · Zbl 0920.49004
[14] A. Figalli., {\it The optimal partial transport problem}, Arch. Ration. Mech. Anal., 195 (2010), pp. 533-560. · Zbl 1245.49059
[15] R. Glowinski and P. L. Tallec, {\it Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics}, Stud. Appl. Numer. Math. 9, SIAM, Philadelphia, 1989. · Zbl 0698.73001
[16] F. Hecht, {\it New development in Freefem++}, J. Numer. Math., 20 (2012), pp. 251-266. · Zbl 1266.68090
[17] N. Igbida and V. T. Nguyen, {\it Augmented Lagrangian method for optimal partial transportation}, IMA J. Numer. Anal., 2017, . · Zbl 1477.49043
[18] N. Igbida and V. T. Nguyen, {\it Optimal partial mass transportation and obstacle Monge-Kantorovich equation}, J. Differential Equations, submitted. · Zbl 1401.35355
[19] J. M. Mazón, J. D. Rossi, and J. Toledo, {\it An optimal matching problem for the Euclidean distance}, SIAM J. Math. Anal., 46 (2014), pp. 233-255. · Zbl 1297.49006
[20] J. M. Mazón, J. D. Rossi, and J. Toledo, {\it An optimal matching problem with constraints}, submitted. · Zbl 1391.35150
[21] C. Villani, {\it Optimal Transport, Old and New}, Grundlehren Math. Wiss. 338, Springer, Berlin, 2009. · Zbl 1156.53003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.