A damped Newton algorithm for generated Jacobian equations. (English) Zbl 1484.49073
Summary: Generated Jacobian Equations have been introduced by N. S. Trudinger [Discrete Contin. Dyn. Syst. 34, No. 4, 1663–1681 (2014; Zbl 1279.35052)] as a generalization of Monge-Ampère equations arising in optimal transport. In this paper, we introduce and study a damped Newton algorithm for solving these equations in the semi-discrete setting, meaning that one of the two measures involved in the problem is finitely supported and the other one is absolutely continuous. We also present a numerical application of this algorithm to the near-field parallel reflector problem arising in non-imaging problems.
MSC:
| 49Q22 | Optimal transportation |
| 35J66 | Nonlinear boundary value problems for nonlinear elliptic equations |
| 35J25 | Boundary value problems for second-order elliptic equations |
Keywords:
generated Jacobian equations; optimal transport; damped Newton algorithm; non-imaging problemsCitations:
Zbl 1279.35052References:
| [1] | Abedin, F.; Gutiérrez, CE, An iterative method for generated Jacobian equations, Calc. Var. Partial. Differ. Equ., 56, 4, 101 (2017) · Zbl 1376.49037 · doi:10.1007/s00526-017-1200-2 |
| [2] | Berman, R.J.: Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport. Found. Comput. Math. 1-42 (2020) |
| [3] | Boissonnat, J.-D., Wormser, C., Yvinec, M.: Curved voronoi diagrams. In: Effective Computational Geometry for Curves and Surfaces, Springer, pp. 67-116 (2007). https://hal.archives-ouvertes.fr/hal-00488446 · Zbl 1116.65021 |
| [4] | Caffarelli, L. A.; Kochengin, S.; Oliker, V. I., On the numerical solution of the problem of reflector design with given far-field scattering data, Contemp. Math, 226, 13-32 (1999) · Zbl 0917.65104 · doi:10.1090/conm/226/03233 |
| [5] | Galichon, A.; Kominers, SD; Weber, S., Costly concessions: an empirical framework for matching with imperfectly transferable utility, J. Polit. Econ., 127, 6, 2875-2925 (2019) · doi:10.1086/702020 |
| [6] | Guillen, N., A primer on generated Jacobian equations: geometry, optics, economics, Not. Am. Math. Soc., 66, 1-10 (2019) · Zbl 1435.35367 · doi:10.1090/noti1956 |
| [7] | Guillen, N.; Kitagawa, J., Pointwise estimates and regularity in geometric optics and other generated Jacobian equations, Commun. Pure Appl. Math., 70, 6, 1146-1220 (2017) · Zbl 1375.35234 · doi:10.1002/cpa.21691 |
| [8] | Gutiérrez, CE; Tournier, F., Regularity for the near field parallel refractor and reflector problems, Calc. Var. Partial. Differ. Equ., 54, 1, 917-949 (2015) · Zbl 1334.78007 · doi:10.1007/s00526-014-0811-0 |
| [9] | Jiang, F.; Trudinger, NS, On pogorelov estimates in optimal transportation and geometric optics, Bull. Math. Sci., 4, 3, 407-431 (2014) · Zbl 1307.90023 · doi:10.1007/s13373-014-0055-5 |
| [10] | Kitagawa, J., An iterative scheme for solving the optimal transportation problem, Calc. Var. Partial. Differ. Equ., 51, 1-2, 243-263 (2014) · Zbl 1297.49051 · doi:10.1007/s00526-013-0673-x |
| [11] | Kitagawa, J.; Mérigot, Q.; Thibert, B., Convergence of a newton algorithm for semi-discrete optimal transport, J. Eur. Math. Soc., 21, 9, 2603-2651 (2019) · Zbl 1439.49053 · doi:10.4171/JEMS/889 |
| [12] | Kochengin, SA; Oliker, VI, Determination of reflector surfaces from near-field scattering data, Inverse Prob., 13, 2, 363 (1997) · Zbl 0871.35107 · doi:10.1088/0266-5611/13/2/011 |
| [13] | Machado, DCMP; Mérigot, Q.; Thibert, B., Far-field reflector problem and intersection of paraboloids, Numer. Math., 134, 2, 389-411 (2016) · Zbl 1354.78003 · doi:10.1007/s00211-015-0780-z |
| [14] | Mérigot, Q.; Meyron, J.; Thibert, B., An algorithm for optimal transport between a simplex soup and a point cloud, SIAM J. Imaging Sci., 11, 2, 1363-1389 (2018) · Zbl 1401.49068 · doi:10.1137/17M1137486 |
| [15] | Merigot, Q., Thibert, B.: Optimal transport: discretization and algorithms. In: Handbook of Numerical Analysis, vol. 22. Elsevier (2021) (to appear) · Zbl 07412767 |
| [16] | Nöldeke, G.; Samuelson, L., The implementation duality, Econometrica, 86, 4, 1283-1324 (2018) · Zbl 1396.91572 · doi:10.3982/ECTA13307 |
| [17] | Oliker, VI; Prussner, LD, On the numerical solution of the equation \(\frac{{\partial^2 z}}{{\partial x^2 }}\frac{{\partial^2 z}}{{\partial y^2 }} - \left( {\frac{{\partial^2 z}}{{\partial x\partial y}}} \right)^2 = f\) and its discretizations I, Numerische Mathematik, 54, 3, 271-293 (1989) · Zbl 0659.65116 · doi:10.1007/BF01396762 |
| [18] | Oliker, V.: Mathematical aspects of design of beam shaping surfaces in geometrical optics. In: Kirkilionis, M., Krömker, S., Rannacher, R., Tomi, F. (eds.) Trends in Nonlinear Analysis, pp. 193-224. Springer (2003) · Zbl 1062.78002 |
| [19] | Trudinger, NS, On the local theory of prescribed Jacobian equations, Discrete Contin. Dyn. Syst. A, 34, 4, 1663-1681 (2014) · Zbl 1279.35052 · doi:10.3934/dcds.2014.34.1663 |
| [20] | Romijn, LB; ten Thije Boonkkamp, JHM; Anthonissen, MJH; Ijzerman, WL, An iterative least-squares method for generated Jacobian equations in freeform optical design, SIAM J. Sci. Comput., 43, 2, B298-B322 (2021) · Zbl 1465.78001 · doi:10.1137/20M1338940 |
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.
