• 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 and 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.

[2]

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

[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.

[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.

[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.

[6]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[14]

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

[15]

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

[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.

[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.

[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.

[19]

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

[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.

[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.

[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.

[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.

[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.

[25]

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

[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.

[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.

[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.

[29]

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

[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.

[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.

[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.

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

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

[35]

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

[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.

[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.

[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.

[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.

[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.

[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.

[42]

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

[43]

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

[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.

[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.

[46]

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

[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. 

[48]

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

[49]

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

[50]

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

[51]

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

[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.

[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.

[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.

[55] G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001.  doi: 10.1017/CBO9780511626319.
[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).

[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. 

[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.

[59]

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

[60]

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

[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.

[62]

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

[63]

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

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.

[2]

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

[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.

[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.

[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.

[6]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[14]

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

[15]

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

[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.

[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.

[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.

[19]

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

[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.

[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.

[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.

[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.

[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.

[25]

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

[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.

[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.

[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.

[29]

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

[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.

[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.

[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.

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

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

[35]

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

[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.

[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.

[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.

[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.

[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.

[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.

[42]

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

[43]

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

[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.

[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.

[46]

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

[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. 

[48]

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

[49]

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

[50]

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

[51]

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

[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.

[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.

[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.

[55] G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, Cambridge, 2001.  doi: 10.1017/CBO9780511626319.
[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).

[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. 

[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.

[59]

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

[60]

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

[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.

[62]

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

[63]

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

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 and Applied Analysis, 2006, 5 (2) : 289-307. doi: 10.3934/cpaa.2006.5.289

[2]

Ye Zhang, Bernd Hofmann. Two new non-negativity preserving iterative regularization methods for ill-posed inverse problems. Inverse Problems and Imaging, 2021, 15 (2) : 229-256. doi: 10.3934/ipi.2020062

[3]

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

[4]

Mohammed Al Horani, Angelo Favini, Hiroki Tanabe. Inverse problems on degenerate integro-differential equations. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022025

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Dang Van Hieu, Le Dung Muu, Pham Kim Quy. New iterative regularization methods for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021185

[13]

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

[14]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems and Imaging, 2021, 15 (3) : 415-443. doi: 10.3934/ipi.2020074

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete and Continuous Dynamical Systems, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

 Impact Factor: 

Metrics

  • PDF downloads (430)
  • HTML views (206)
  • Cited by (2)

Other articles
by authors

[Back to Top]