• Previous Article
    Optimal resource allocation in the difference and differential Stackelberg games on marketing networks
  • JDG Home
  • This Issue
  • Next Article
    A substitute for the classical Neumann–Morgenstern characteristic function in cooperative differential games
April  2020, 7(2): 123-140. doi: 10.3934/jdg.2020008

Discrete processes and their continuous limits

Department of Computer Science, University of British Columbia, V6T1Z4, Canada

Received  September 2019 Published  April 2020

Fund Project: Supported in part by NSERC Discovery Grant 84306

The possibility that a discrete process can be fruitfully approximated by a continuous one, with the latter involving a differential system, is fascinating. Important theoretical insights, as well as significant computational efficiency gains may lie in store. A great success story in this regard are the Navier-Stokes equations, which model many phenomena in fluid flow rather well. Recent years saw many attempts to formulate more such continuous limits, and thus harvest theoretical and practical advantages, in diverse areas including mathematical biology, economics, finance, computational optimization, image processing, game theory, and machine learning.

Caution must be applied as well, however. In fact, it is often the case that the given discrete process is richer in possibilities than its continuous differential system limit, and that a further study of the discrete process is practically rewarding. Furthermore, there are situations where the continuous limit process may provide important qualitative, but not quantitative, information about the actual discrete process. This paper considers several case studies of such continuous limits and demonstrates success as well as cause for caution. Consequences are discussed.

Citation: Uri M. Ascher. Discrete processes and their continuous limits. Journal of Dynamics & Games, 2020, 7 (2) : 123-140. doi: 10.3934/jdg.2020008
References:
[1]

H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Statist. Math. Tokyo, 11 (1959), 1-16.  doi: 10.1007/BF01831719.  Google Scholar

[2]

U. Ascher, On symmetric schemes and differential-algebraic equations, SIAM J. Sci. Statist. Comput., 10 (1989), 937-949.  doi: 10.1137/0910054.  Google Scholar

[3]

U. AscherJ. Christiansen and R. D. Russell, Collocation software for boundary-value ODEs, ACM Trans. Math. Software, 7 (1981), 209-222.  doi: 10.1145/355945.355950.  Google Scholar

[4]

U. Ascher and C. Greif, A First Course in Numerical Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. doi: 10.1137/1.9780898719987.  Google Scholar

[5]

U. AscherE. Haber and H. Huang, On effective methods for implicit piecewise smooth surface recovery, SIAM J. Sci. Comput., 28 (2006), 339-358.  doi: 10.1137/040617261.  Google Scholar

[6]

U. AscherH. Huang and K. van den Doel, Artificial time integration, BIT, 47 (2007), 3-25.  doi: 10.1007/s10543-006-0112-x.  Google Scholar

[7]

U. Ascher, R. Mattheij and R. Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. doi: 10.1137/1.9781611971231.  Google Scholar

[8]

U. Ascher and L. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. doi: 10.1137/1.9781611971392.  Google Scholar

[9]

U. Ascher and S. Reich, The midpoint scheme and variants for Hamiltonian systems: Advantages and pitfalls, SIAM J. Sci. Comput., 21 (1999), 1045-1065.  doi: 10.1137/S1064827597316059.  Google Scholar

[10]

U. Ascher and H. Huang, Numerical analysis in visual computing: What we can learn from each other, Vietnam J. Math, 46 (2018) 745-759. doi: 10.1007/s10013-018-0299-6.  Google Scholar

[11]

D. Baraff and A. Witkin, Large steps in cloth simulation, In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, Association for Computing Machinery, New York, New York, 1998, 43-54. doi: 10.1145/280814.280821.  Google Scholar

[12]

C. Barnes, E. Shechtman, A. Finkelstein and D. Goldman, Patchmatch: A randomized correspondence algorithm for structural image editing, ACM Trans. Graph., 27 (2009), Art. 24, 11 pp. doi: 10.1145/1576246.1531330.  Google Scholar

[13]

J. Barzilai and J. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.  doi: 10.1093/imanum/8.1.141.  Google Scholar

[14]

A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997.ch1.  Google Scholar

[15]

M. Betancourt, M. Jordan and A. Wilson, On symplectic optimization, preprint, 2018, arXiv: 1802.03653v2. Google Scholar

[16]

M. Burger, M. Di Francesco, P. A. Markowich and M. T. Wolfram, On a mean field game optimal control approach modeling fast exit scenarios in human crowds, In 52nd IEEE Conference on Decision and Control, Florence, 2013, 3128-3133. doi: 10.1109/CDC.2013.6760360.  Google Scholar

[17]

D. Calvetti and L. Reichel, Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms, 29 2002, 45-65. doi: 10.1023/A:1014899604567.  Google Scholar

[18]

D. Calvetti, L. Reichel, and Q. Zhang., Iterative exponential filtering for large discrete ill-posed problems., Numer. Math., 83: 535-556, 1999. doi: 10.1007/s002119900077.  Google Scholar

[19]

A. Chambolle and T. Pock, An introduction to continuous optimization for imaging, Acta Numer., 25 (2016), 161-319.  doi: 10.1017/S096249291600009X.  Google Scholar

[20]

T. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. doi: 10.1137/1.9780898717877.  Google Scholar

[21]

D. Chen, D. Levin, L. Matusic and D. Kaufman, Dynamics-aware numerical coarsening for fabrication design, ACM Trans. Graphics, 36 (2017), Art. 84, 15 pp. doi: 10.1145/3072959.3073669.  Google Scholar

[22]

A. J. Chorin, Numerical solution of the Navier-Stokes equations, Math. Comp., 22 (1968), 745-762.  doi: 10.1090/S0025-5718-1968-0242392-2.  Google Scholar

[23]

A. J. Chorin and J. E. Marsden, A Mathematical Introduction to Fluid Mechanics, 3rd edition, Springer-Verlag, New York, 1993. doi: 10.1007/978-1-4612-0883-9.  Google Scholar

[24]

S. Darabi, E. Shechtman, C. Barnes, D. Goldman and P. Sen, Image melding: Combining inconsistent images using patch-based synthesis, ACM Trans. Graph., 31 (2012), Art. 82, 1-82. doi: 10.1145/2185520.2185578.  Google Scholar

[25]

P. Deuflhard, Newton's Method for Nonlinear Problems, Springer-Verlag, Berlin, 2004.  Google Scholar

[26]

J. Diakonikolas and L. Orecchia, The approximate duality gap technique: A unified theory of first-order methods, SIAM J. Optim., 29 (2019), 660-689.  doi: 10.1137/18M1172314.  Google Scholar

[27]

K. van den Doel and U. Ascher, Dynamic level set regularization for large distributed parameter estimation problems, Inverse Problems, 23 (2007), 1271-1288.  doi: 10.1088/0266-5611/23/3/025.  Google Scholar

[28]

K. van den Doel and U. Ascher, The chaotic nature of faster gradient descent methods, J. Sci. Comput., 51 (2011), 560-581.  doi: 10.1007/s10915-011-9521-3.  Google Scholar

[29]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996.  Google Scholar

[30]

Z. Farbman, R. Fattal, D. Lischinski and R. Szeliski, Edge-preserving decompositions for multi-scale tone and detail manipulation, in ACM SIGGRAPH 2008 Papers, Association for Computing Machinery, New York, New York, 2008. doi: 10.1145/1399504.1360666.  Google Scholar

[31]

D. A. Gomez and J. Saúde, Mean field games models - A brief survey, Dyn. Games Appl., 4 (2014), 110-154.  doi: 10.1007/s13235-013-0099-2.  Google Scholar

[32]

D. A. GomezJ. Mohr and R. R. Souza, Continuous time finite state mean field games, Appl. Math. Optim., 68 (2013), 99-143.  doi: 10.1007/s00245-013-9202-8.  Google Scholar

[33] I. GoodfellowY. Bengio and A. Courville, Deep Learning, MIT Press, Cambridge, MA, 2016.   Google Scholar
[34]

A. Greenbaum, Iterative Methods for Solving Linear Systems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. doi: 10.1137/1.9781611970937.  Google Scholar

[35]

E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-05018-7.  Google Scholar

[36]

E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd edition, Springer-Verlag, Berlin, 1996. doi: 10.1007/978-3-642-05221-7.  Google Scholar

[37]

H. Huang and U. Ascher, Fast denoising of surface meshes with intrinsic texture, Inverse Problems, 24 (2008), 034003, 18 pp. doi: 10.1088/0266-5611/24/3/034003.  Google Scholar

[38]

H. Huang and U. Ascher, Surface mesh smoothing, regularization, and feature detection, SIAM J. Sci. Comput., 31 (2008), 74-93.  doi: 10.1137/060676684.  Google Scholar

[39]

H. HuangD. LiR. ZhangU. Ascher and D. Cohen-Or, Consolidation of unorganized point clouds for surface reconstruction, ACM Trans. Graph., 28 (2009), 1-7.  doi: 10.1109/TIP.2010.2076297.  Google Scholar

[40]

H. Huang, S. Wu, M. Gong, D. Cohen-Or, U. Ascher and H. Zhang, Edge-aware point set resampling, ACM Trans. Graph., 32 (2013), Art. 9, 12 pp. doi: 10.1145/2421636.2421645.  Google Scholar

[41]

H. Huang, K. Yin, M. Gong, D. Lischinski, D. Cohen-Or, U. M. Ascher, and B. Chen, "Mind the gap": Tele-registration for structure-driven image completion, ACM Trans. Graph., 32 (2013), Art. 174, 10 pp. doi: 10.1145/2508363.2508373.  Google Scholar

[42]

J. Kaipo and E. Somersalo, Statistical and Computational Inverse Problems, Springer-Verlag, New York, 2005.  Google Scholar

[43]

H.-O. Kreiss, Centered difference approximation to singular systems of odes, in Symposia Mathematica X, 1972. Google Scholar

[44]

J.-M. Lasry and P.-L. Lions, Mean field games, Jpn. J. Math., 2 (2007), 229-260.  doi: 10.1007/s11537-007-0657-8.  Google Scholar

[45]

R. MalhaméM. Huang and P. Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6 (2006), 221-252.  doi: 10.4310/CIS.2006.v6.n3.a5.  Google Scholar

[46]

M. Markowich, C. Ringhofer and C. Schmeiser, Semi-conductor Equations, Springer-Verlag, Vienna, 1990. doi: 10.1007/978-3-7091-6961-2.  Google Scholar

[47]

Y. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR, 269 (1983), 543-547.   Google Scholar

[48]

Y. Nesterov, Lectures on Convex Optimization, Springer, Cham, 2018. doi: 10.1007/978-3-319-91578-4.  Google Scholar

[49]

J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874.  Google Scholar

[50]

S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003. doi: 10.1007/b98879.  Google Scholar

[51]

B. T. Polyak, Some methods of speeding up the convergence of iteration methods, Z. Vycisl. Mat i Mat. Fiz., 4 (1964), 791-803.   Google Scholar

[52]

M. Raydan and B. Svaiter, Relaxed steepest descent and Cauchy-Barzilai-Borwein method, Comput. Optim. Appl., 21 (2002), 155-167.  doi: 10.1023/A:1013708715892.  Google Scholar

[53]

F. Roosta-Khorasani, K. van den Doel and U. Ascher, Stochastic algorithms for inverse problems involving PDEs and many measurements, SIAM J. Sci. Comput., 36 (2014), S3-S22. doi: 10.1137/130922756.  Google Scholar

[54]

L. Ruthotto and E. Haber, Deep neural networks motivated by partial differential equations, J. Math. Imaging Vision, 62 (2019), 352-364.  doi: 10.1007/s10851-019-00903-1.  Google Scholar

[55] G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001.  doi: 10.1017/CBO9780511626319.  Google Scholar
[56]

W. Su, S. Boyd, and E. Candes, A differential equation for modelling Nesterov's accelerated gradient method, Advances in Neural Information Processing Systems (NIPS), 27 (2014). Google Scholar

[57]

W. SuS. Boyd and E. Candes, A differential equation for modelling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), 1-43.   Google Scholar

[58]

E. TadmorS. Nezzar and L. Vese, A multiscale image representation using hierarchical (BV, ${L}^2$) decompositions, Multiscale Model. Simul., 2 (2004), 554-579.  doi: 10.1137/030600448.  Google Scholar

[59]

A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed Problems, John Wiley and Sons, Inc., New York-Toronto, Ont.-London, 1977.  Google Scholar

[60]

G. Wanner, Kepler, Newton and numerical analysis, Acta Numer., 19 (2010), 561-598.  doi: 10.1017/S0962492910000073.  Google Scholar

[61]

A. Wibisono, A. Wilson and M. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci. U. S. A., 113 (2016), E7351-E7358. doi: 10.1073/pnas.1614734113.  Google Scholar

[62]

W. I. Zangwill, Nonlinear programming: A unified approach, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1969.  Google Scholar

[63]

J. Zhang, A. Mokhtari, S. Sra and A. Jadbabai, Direct Runge-Kutta discretization achieves acceleration, preprint, 2018, arXiv: 1805.00521. Google Scholar

show all references

References:
[1]

H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Statist. Math. Tokyo, 11 (1959), 1-16.  doi: 10.1007/BF01831719.  Google Scholar

[2]

U. Ascher, On symmetric schemes and differential-algebraic equations, SIAM J. Sci. Statist. Comput., 10 (1989), 937-949.  doi: 10.1137/0910054.  Google Scholar

[3]

U. AscherJ. Christiansen and R. D. Russell, Collocation software for boundary-value ODEs, ACM Trans. Math. Software, 7 (1981), 209-222.  doi: 10.1145/355945.355950.  Google Scholar

[4]

U. Ascher and C. Greif, A First Course in Numerical Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. doi: 10.1137/1.9780898719987.  Google Scholar

[5]

U. AscherE. Haber and H. Huang, On effective methods for implicit piecewise smooth surface recovery, SIAM J. Sci. Comput., 28 (2006), 339-358.  doi: 10.1137/040617261.  Google Scholar

[6]

U. AscherH. Huang and K. van den Doel, Artificial time integration, BIT, 47 (2007), 3-25.  doi: 10.1007/s10543-006-0112-x.  Google Scholar

[7]

U. Ascher, R. Mattheij and R. Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. doi: 10.1137/1.9781611971231.  Google Scholar

[8]

U. Ascher and L. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. doi: 10.1137/1.9781611971392.  Google Scholar

[9]

U. Ascher and S. Reich, The midpoint scheme and variants for Hamiltonian systems: Advantages and pitfalls, SIAM J. Sci. Comput., 21 (1999), 1045-1065.  doi: 10.1137/S1064827597316059.  Google Scholar

[10]

U. Ascher and H. Huang, Numerical analysis in visual computing: What we can learn from each other, Vietnam J. Math, 46 (2018) 745-759. doi: 10.1007/s10013-018-0299-6.  Google Scholar

[11]

D. Baraff and A. Witkin, Large steps in cloth simulation, In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, Association for Computing Machinery, New York, New York, 1998, 43-54. doi: 10.1145/280814.280821.  Google Scholar

[12]

C. Barnes, E. Shechtman, A. Finkelstein and D. Goldman, Patchmatch: A randomized correspondence algorithm for structural image editing, ACM Trans. Graph., 27 (2009), Art. 24, 11 pp. doi: 10.1145/1576246.1531330.  Google Scholar

[13]

J. Barzilai and J. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.  doi: 10.1093/imanum/8.1.141.  Google Scholar

[14]

A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997.ch1.  Google Scholar

[15]

M. Betancourt, M. Jordan and A. Wilson, On symplectic optimization, preprint, 2018, arXiv: 1802.03653v2. Google Scholar

[16]

M. Burger, M. Di Francesco, P. A. Markowich and M. T. Wolfram, On a mean field game optimal control approach modeling fast exit scenarios in human crowds, In 52nd IEEE Conference on Decision and Control, Florence, 2013, 3128-3133. doi: 10.1109/CDC.2013.6760360.  Google Scholar

[17]

D. Calvetti and L. Reichel, Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms, 29 2002, 45-65. doi: 10.1023/A:1014899604567.  Google Scholar

[18]

D. Calvetti, L. Reichel, and Q. Zhang., Iterative exponential filtering for large discrete ill-posed problems., Numer. Math., 83: 535-556, 1999. doi: 10.1007/s002119900077.  Google Scholar

[19]

A. Chambolle and T. Pock, An introduction to continuous optimization for imaging, Acta Numer., 25 (2016), 161-319.  doi: 10.1017/S096249291600009X.  Google Scholar

[20]

T. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. doi: 10.1137/1.9780898717877.  Google Scholar

[21]

D. Chen, D. Levin, L. Matusic and D. Kaufman, Dynamics-aware numerical coarsening for fabrication design, ACM Trans. Graphics, 36 (2017), Art. 84, 15 pp. doi: 10.1145/3072959.3073669.  Google Scholar

[22]

A. J. Chorin, Numerical solution of the Navier-Stokes equations, Math. Comp., 22 (1968), 745-762.  doi: 10.1090/S0025-5718-1968-0242392-2.  Google Scholar

[23]

A. J. Chorin and J. E. Marsden, A Mathematical Introduction to Fluid Mechanics, 3rd edition, Springer-Verlag, New York, 1993. doi: 10.1007/978-1-4612-0883-9.  Google Scholar

[24]

S. Darabi, E. Shechtman, C. Barnes, D. Goldman and P. Sen, Image melding: Combining inconsistent images using patch-based synthesis, ACM Trans. Graph., 31 (2012), Art. 82, 1-82. doi: 10.1145/2185520.2185578.  Google Scholar

[25]

P. Deuflhard, Newton's Method for Nonlinear Problems, Springer-Verlag, Berlin, 2004.  Google Scholar

[26]

J. Diakonikolas and L. Orecchia, The approximate duality gap technique: A unified theory of first-order methods, SIAM J. Optim., 29 (2019), 660-689.  doi: 10.1137/18M1172314.  Google Scholar

[27]

K. van den Doel and U. Ascher, Dynamic level set regularization for large distributed parameter estimation problems, Inverse Problems, 23 (2007), 1271-1288.  doi: 10.1088/0266-5611/23/3/025.  Google Scholar

[28]

K. van den Doel and U. Ascher, The chaotic nature of faster gradient descent methods, J. Sci. Comput., 51 (2011), 560-581.  doi: 10.1007/s10915-011-9521-3.  Google Scholar

[29]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996.  Google Scholar

[30]

Z. Farbman, R. Fattal, D. Lischinski and R. Szeliski, Edge-preserving decompositions for multi-scale tone and detail manipulation, in ACM SIGGRAPH 2008 Papers, Association for Computing Machinery, New York, New York, 2008. doi: 10.1145/1399504.1360666.  Google Scholar

[31]

D. A. Gomez and J. Saúde, Mean field games models - A brief survey, Dyn. Games Appl., 4 (2014), 110-154.  doi: 10.1007/s13235-013-0099-2.  Google Scholar

[32]

D. A. GomezJ. Mohr and R. R. Souza, Continuous time finite state mean field games, Appl. Math. Optim., 68 (2013), 99-143.  doi: 10.1007/s00245-013-9202-8.  Google Scholar

[33] I. GoodfellowY. Bengio and A. Courville, Deep Learning, MIT Press, Cambridge, MA, 2016.   Google Scholar
[34]

A. Greenbaum, Iterative Methods for Solving Linear Systems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. doi: 10.1137/1.9781611970937.  Google Scholar

[35]

E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-05018-7.  Google Scholar

[36]

E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd edition, Springer-Verlag, Berlin, 1996. doi: 10.1007/978-3-642-05221-7.  Google Scholar

[37]

H. Huang and U. Ascher, Fast denoising of surface meshes with intrinsic texture, Inverse Problems, 24 (2008), 034003, 18 pp. doi: 10.1088/0266-5611/24/3/034003.  Google Scholar

[38]

H. Huang and U. Ascher, Surface mesh smoothing, regularization, and feature detection, SIAM J. Sci. Comput., 31 (2008), 74-93.  doi: 10.1137/060676684.  Google Scholar

[39]

H. HuangD. LiR. ZhangU. Ascher and D. Cohen-Or, Consolidation of unorganized point clouds for surface reconstruction, ACM Trans. Graph., 28 (2009), 1-7.  doi: 10.1109/TIP.2010.2076297.  Google Scholar

[40]

H. Huang, S. Wu, M. Gong, D. Cohen-Or, U. Ascher and H. Zhang, Edge-aware point set resampling, ACM Trans. Graph., 32 (2013), Art. 9, 12 pp. doi: 10.1145/2421636.2421645.  Google Scholar

[41]

H. Huang, K. Yin, M. Gong, D. Lischinski, D. Cohen-Or, U. M. Ascher, and B. Chen, "Mind the gap": Tele-registration for structure-driven image completion, ACM Trans. Graph., 32 (2013), Art. 174, 10 pp. doi: 10.1145/2508363.2508373.  Google Scholar

[42]

J. Kaipo and E. Somersalo, Statistical and Computational Inverse Problems, Springer-Verlag, New York, 2005.  Google Scholar

[43]

H.-O. Kreiss, Centered difference approximation to singular systems of odes, in Symposia Mathematica X, 1972. Google Scholar

[44]

J.-M. Lasry and P.-L. Lions, Mean field games, Jpn. J. Math., 2 (2007), 229-260.  doi: 10.1007/s11537-007-0657-8.  Google Scholar

[45]

R. MalhaméM. Huang and P. Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6 (2006), 221-252.  doi: 10.4310/CIS.2006.v6.n3.a5.  Google Scholar

[46]

M. Markowich, C. Ringhofer and C. Schmeiser, Semi-conductor Equations, Springer-Verlag, Vienna, 1990. doi: 10.1007/978-3-7091-6961-2.  Google Scholar

[47]

Y. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR, 269 (1983), 543-547.   Google Scholar

[48]

Y. Nesterov, Lectures on Convex Optimization, Springer, Cham, 2018. doi: 10.1007/978-3-319-91578-4.  Google Scholar

[49]

J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874.  Google Scholar

[50]

S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003. doi: 10.1007/b98879.  Google Scholar

[51]

B. T. Polyak, Some methods of speeding up the convergence of iteration methods, Z. Vycisl. Mat i Mat. Fiz., 4 (1964), 791-803.   Google Scholar

[52]

M. Raydan and B. Svaiter, Relaxed steepest descent and Cauchy-Barzilai-Borwein method, Comput. Optim. Appl., 21 (2002), 155-167.  doi: 10.1023/A:1013708715892.  Google Scholar

[53]

F. Roosta-Khorasani, K. van den Doel and U. Ascher, Stochastic algorithms for inverse problems involving PDEs and many measurements, SIAM J. Sci. Comput., 36 (2014), S3-S22. doi: 10.1137/130922756.  Google Scholar

[54]

L. Ruthotto and E. Haber, Deep neural networks motivated by partial differential equations, J. Math. Imaging Vision, 62 (2019), 352-364.  doi: 10.1007/s10851-019-00903-1.  Google Scholar

[55] G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001.  doi: 10.1017/CBO9780511626319.  Google Scholar
[56]

W. Su, S. Boyd, and E. Candes, A differential equation for modelling Nesterov's accelerated gradient method, Advances in Neural Information Processing Systems (NIPS), 27 (2014). Google Scholar

[57]

W. SuS. Boyd and E. Candes, A differential equation for modelling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), 1-43.   Google Scholar

[58]

E. TadmorS. Nezzar and L. Vese, A multiscale image representation using hierarchical (BV, ${L}^2$) decompositions, Multiscale Model. Simul., 2 (2004), 554-579.  doi: 10.1137/030600448.  Google Scholar

[59]

A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed Problems, John Wiley and Sons, Inc., New York-Toronto, Ont.-London, 1977.  Google Scholar

[60]

G. Wanner, Kepler, Newton and numerical analysis, Acta Numer., 19 (2010), 561-598.  doi: 10.1017/S0962492910000073.  Google Scholar

[61]

A. Wibisono, A. Wilson and M. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci. U. S. A., 113 (2016), E7351-E7358. doi: 10.1073/pnas.1614734113.  Google Scholar

[62]

W. I. Zangwill, Nonlinear programming: A unified approach, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1969.  Google Scholar

[63]

J. Zhang, A. Mokhtari, S. Sra and A. Jadbabai, Direct Runge-Kutta discretization achieves acceleration, preprint, 2018, arXiv: 1805.00521. Google Scholar

Figure 1.  Exponential filter $ \omega (s) = 1 - e^{-ts} $ and Tikhonov filter $ \omega_{\rm T} (s) = \frac {s}{s + \beta} $ for $ t\beta = 1/2 $
Figure 2.  Gradient descent with step sizes by (26) for the discretized heat equation with $N = 63^2 $. The Calculated Step Sizes Are Displayed Vs Iteration Counter $K $. The stability limit for a constant step size gives the straight blue line
Figure 3.  Convergence behaviour of LSD for the model Poisson problem with $ n = 63^2 $. The errors $ \| {\bf r}_k \| $ are displayed as a function of iteration counter $ k $
Figure 4.  Convergence behaviour of LSD for the model Poisson problem with $ n = 63^2 $. The errors $ f( {\bf x}_k) - f( {\bf x}^*) $ are displayed as a function of iteration counter $ k $
Figure 5.  Convergence behaviour of monotonized LSD (LSDm) as well as SD, conjugate gradient (CG) and Nesterov's (Nes) for the model Poisson problem with $ n = 63^2 $. The errors $ \| {\bf r}_k \| $ are displayed as a function of iteration counter $ k $
Figure 6.  Convergence behaviour of monotonized LSD (LSDm) as well as SD, conjugate gradient (CG) and Nesterov's (Nes) for the model Poisson problem with $ n = 63^2 $. The errors $ f( {\bf x}_k) - f( {\bf x}^*) $ are displayed as a function of iteration counter $ k $
Table 1.  Maximum time step $ h $ for the heat-to-Poisson process as a function of spatial step $ \xi $
$ \xi $ $ 2^{-5} $ $ 2^{-6} $ $ 2^{-7} $ $ 2^{-8} $
$ h $ .05 .039 .043 .035
$ \xi $ $ 2^{-5} $ $ 2^{-6} $ $ 2^{-7} $ $ 2^{-8} $
$ h $ .05 .039 .043 .035
[1]

Joseph A. Connolly, Neville J. Ford. Comparison of numerical methods for fractional differential equations. Communications on Pure & Applied Analysis, 2006, 5 (2) : 289-307. doi: 10.3934/cpaa.2006.5.289

[2]

Michael Herty, Giuseppe Visconti. Kinetic methods for inverse problems. Kinetic & Related Models, 2019, 12 (5) : 1109-1130. doi: 10.3934/krm.2019042

[3]

Iasson Karafyllis, Lars Grüne. Feedback stabilization methods for the numerical solution of ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2011, 16 (1) : 283-317. doi: 10.3934/dcdsb.2011.16.283

[4]

Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511

[5]

Philipp Hungerländer, Barbara Kaltenbacher, Franz Rendl. Regularization of inverse problems via box constrained minimization. Inverse Problems & Imaging, 2020, 14 (3) : 437-461. doi: 10.3934/ipi.2020021

[6]

Frank Pörner, Daniel Wachsmuth. Tikhonov regularization of optimal control problems governed by semi-linear partial differential equations. Mathematical Control & Related Fields, 2018, 8 (1) : 315-335. doi: 10.3934/mcrf.2018013

[7]

Zhiyuan Wen, Meirong Zhang. On the optimization problems of the principal eigenvalues of measure differential equations with indefinite measures. Discrete & Continuous Dynamical Systems - B, 2020, 25 (8) : 3257-3274. doi: 10.3934/dcdsb.2020061

[8]

Martin Hanke, William Rundell. On rational approximation methods for inverse source problems. Inverse Problems & Imaging, 2011, 5 (1) : 185-202. doi: 10.3934/ipi.2011.5.185

[9]

Daijun Jiang, Hui Feng, Jun Zou. Overlapping domain decomposition methods for linear inverse problems. Inverse Problems & Imaging, 2015, 9 (1) : 163-188. doi: 10.3934/ipi.2015.9.163

[10]

Abhishake Rastogi. Tikhonov regularization with oversmoothing penalty for nonlinear statistical inverse problems. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4111-4126. doi: 10.3934/cpaa.2020183

[11]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

[12]

G. Machado, L. Trabucho. Analytical and numerical solutions for a class of optimization problems in elasticity. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1013-1032. doi: 10.3934/dcdsb.2004.4.1013

[13]

Sergiy Zhuk. Inverse problems for linear ill-posed differential-algebraic equations with uncertain parameters. Conference Publications, 2011, 2011 (Special) : 1467-1476. doi: 10.3934/proc.2011.2011.1467

[14]

Jaan Janno, Kairi Kasemets. A positivity principle for parabolic integro-differential equations and inverse problems with final overdetermination. Inverse Problems & Imaging, 2009, 3 (1) : 17-41. doi: 10.3934/ipi.2009.3.17

[15]

Mohammed Al Horani, Angelo Favini. Inverse problems for singular differential-operator equations with higher order polar singularities. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 2159-2168. doi: 10.3934/dcdsb.2014.19.2159

[16]

Jitraj Saha, Nilima Das, Jitendra Kumar, Andreas Bück. Numerical solutions for multidimensional fragmentation problems using finite volume methods. Kinetic & Related Models, 2019, 12 (1) : 79-103. doi: 10.3934/krm.2019004

[17]

Z. Foroozandeh, Maria do rosário de Pinho, M. Shamsi. On numerical methods for singular optimal control problems: An application to an AUV problem. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2219-2235. doi: 10.3934/dcdsb.2019092

[18]

Martin Benning, Elena Celledoni, Matthias J. Ehrhardt, Brynjulf Owren, Carola-Bibiane Schönlieb. Deep learning as optimal control problems: Models and numerical methods. Journal of Computational Dynamics, 2019, 6 (2) : 171-198. doi: 10.3934/jcd.2019009

[19]

Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2020132

[20]

Bernadette N. Hahn. Dynamic linear inverse problems with moderate movements of the object: Ill-posedness and regularization. Inverse Problems & Imaging, 2015, 9 (2) : 395-413. doi: 10.3934/ipi.2015.9.395

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]