A least-squares method for optimal transport using the Monge-Ampère equation. (English) Zbl 1342.65149
Summary: In this article we introduce a novel numerical method to solve the problem of optimal transport and the related elliptic Monge-Ampère equation. It is one of the few numerical algorithms capable of solving this problem efficiently with the proper transport boundary condition. The computation time scales well with the grid size and has the additional advantage that the target domain may be nonconvex. We present the method and several numerical experiments.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 35J20 | Variational methods for second-order elliptic equations |
| 35J25 | Boundary value problems for second-order elliptic equations |
| 35J96 | Monge-Ampère equations |
| 65N99 | Numerical methods for partial differential equations, boundary value problems |
| 49K20 | Optimality conditions for problems involving partial differential equations |
| 49Q20 | Variational problems in a geometric measure-theoretic setting |
References:
| [1] | S. Angenent, S. Haker, and A. Tannenbaum, {\it Minimizing flows for the Monge-Kantorovich problem}, SIAM J. Math. Anal., 35 (2003), pp. 61-97. · Zbl 1042.49040 |
| [2] | 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 |
| [3] | J. Benamou, B. Froese, and A. Oberman, {\it A viscosity solution approach to the Monge-Ampère formulation of the optimal transportation problem}, arXiv:1208.4873. · Zbl 1349.65554 |
| [4] | J. Benamou, B. Froese, and A. Oberman, {\it Numerical solution of the optimal transportation problem using the Monge-Ampère equation}, J. Comput. Phys., 260 (2014), pp. 107-126. · Zbl 1349.65554 |
| [5] | A. Caboussat, R. Glowinski, and D. Sorensen, {\it A least-squares method for the numerical solution of the Dirichlet problem for the elliptic Monge-Ampère equation in dimension two}, ESAIM Control Optim. Calc. Var., 19 (2013), pp. 780-810. · Zbl 1272.65089 |
| [6] | R. Courant and D. Hilbert, {\it Methods of Mathematical Physics}, Vol. 1, Wiley, New York, 1989. · Zbl 0729.00007 |
| [7] | H. Elman, D. Silvester, and A. Wathen, {\it Finite Elements and Fast Iterative Solvers}, Oxford University Press, New York, 2005. · Zbl 1083.76001 |
| [8] | L. Evans, {\it Partial differential equations and Monge-Ampere mass transfer}, in Current Developments in Mathematics, Cambridge MA (1997), International Press, Boston, 1999, pp. 65-126. · Zbl 0954.35011 |
| [9] | B. Froese, {\it A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions}, SIAM J. Sci. Comput., 34 (2012), pp. A1432-A1459. · Zbl 1252.65180 |
| [10] | B. Froese and A. Oberman, {\it Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher}, SIAM J. Numer. Anal., 49 (2011), pp. 1692-1714. · Zbl 1255.65195 |
| [11] | B. Froese and A. Oberman, {\it Fast finite difference solvers for singular solutions of the elliptic Monge-Ampère equation}, J. Comput. Phys., 230 (2011), pp. 818-834. · Zbl 1206.65242 |
| [12] | B. Froese and A. Oberman, {\it Convergent filtered schemes for the Monge-Ampère partial differential equation}, SIAM J. Numer. Anal., 51 (2013), pp. 423-444. · Zbl 1268.35070 |
| [13] | E. Haber, T. Rehman, and A. Tannenbaum, {\it An efficient numerical method for the solution of the \(L_2\) optimal mass transfer problem.}, SIAM J. Sci. Comput., 32 (2010), pp. 197-211. · Zbl 1428.49034 |
| [14] | J. Marsden and A. Tromba, {\it Vector Calculus}, 4th ed., W. H. Freeman, New York, 1996. · Zbl 0322.26010 |
| [15] | R. Mattheij, S. Rienstra, and J. ten Thije Boonkkamp, {\it Partial Differential Equations}, SIAM, Philadelphia, 2005. · Zbl 1090.35001 |
| [16] | A. Oberman, {\it Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems}, SIAM J. Numer. Anal., 44 (2006), pp. 879-895. · Zbl 1124.65103 |
| [17] | A. Oberman, {\it Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian}, Discrete Contin. Dyn. Syst. Ser. B, 10 (2008), pp. 221-238. · Zbl 1145.65085 |
| [18] | ORA, {\it Ora Lighttools}, http://optics.synopsys.com/lighttools (accessed August 19, 2014). |
| [19] | W. Press, B. Flannery, S. Teukolsky, and W. Vetterling, {\it Numerical Recipes in Fortran}77, 2nd ed., Cambridge University Press, Cambridge, UK, 1996. · Zbl 0892.65001 |
| [20] | C. Prins, {\it Inverse Methods for Illumination Optics}, Ph.D. thesis, Eindhoven University of Technology, Eindhoven, the Netherlands, 2014. |
| [21] | C. Prins, J. ten Thije Boonkkamp, J. van Roosmalen, T. Tukker, and W. IJzerman, {\it A Monge-Ampère solver for free-form reflector design}, SIAM J. Sci. Comput., 36 (2014), pp. B640-B660. · Zbl 1308.65183 |
| [22] | J. Tignol, {\it Galois’s Theory of Algebraic Equations}, Longman Scientific and Technical, Harlow, UK, 1988. · Zbl 0663.12020 |
| [23] | N. Trudinger and X. Wang, {\it On the second boundary value problem for Monge-Ampère type equations and optimal transportation}, Ann. Sc. Norm. Super. Pisa Cl. Sci., 8 (2009), pp. 143-174. · Zbl 1182.35134 |
| [24] | C. Villani, {\it Topics in Optimal Transportation}, AMS, Providence, RI, 2003. · Zbl 1106.90001 |
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.
