Gradient descent and fast artificial time integration
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 43 (2009) no. 4, p. 689-708

The integration to steady state of many initial value ODEs and PDEs using the forward Euler method can alternatively be considered as gradient descent for an associated minimization problem. Greedy algorithms such as steepest descent for determining the step size are as slow to reach steady state as is forward Euler integration with the best uniform step size. But other, much faster methods using bolder step size selection exist. Various alternatives are investigated from both theoretical and practical points of view. The steepest descent method is also known for the regularizing or smoothing effect that the first few steps have for certain inverse problems, amounting to a finite time regularization. We further investigate the retention of this property using the faster gradient descent variants in the context of two applications. When the combination of regularization and accuracy demands more than a dozen or so steepest descent steps, the alternatives offer an advantage, even though (indeed because) the absolute stability limit of forward Euler is carefully yet severely violated.

DOI : https://doi.org/10.1051/m2an/2009025
Classification:  65F10,  65F50
Keywords: steady state, artificial time, gradient descent, forward Euler, lagged steepest descent, regularization
@article{M2AN_2009__43_4_689_0,
author = {Ascher, Uri M. and Kees van den Doel and Huang, Hui and Svaiter, Benar F.},
title = {Gradient descent and fast artificial time integration},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
publisher = {EDP-Sciences},
volume = {43},
number = {4},
year = {2009},
pages = {689-708},
doi = {10.1051/m2an/2009025},
zbl = {1169.65329},
mrnumber = {2542872},
language = {en},
url = {http://www.numdam.org/item/M2AN_2009__43_4_689_0}
}
Ascher, Uri M.; Kees van den Doel; Huang, Hui; Svaiter, Benar F. Gradient descent and fast artificial time integration. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 43 (2009) no. 4, pp. 689-708. doi : 10.1051/m2an/2009025. http://www.numdam.org/item/M2AN_2009__43_4_689_0/

[1] H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Stat. Math. Tokyo 11 (1959) 1-16. | MR 107973 | Zbl 0100.14002

[2] U. Ascher, Numerical Methods for Evolutionary Differential Equations. SIAM, Philadelphia, USA (2008). | MR 2420042 | Zbl 1157.65048

[3] U. Ascher, E. Haber and H. Huang, On effective methods for implicit piecewise smooth surface recovery. SIAM J. Sci. Comput. 28 (2006) 339-358. | MR 2219300 | Zbl 1104.65320

[4] U. Ascher, H. Huang and K. Van Den Doel, Artificial time integration. BIT 47 (2007) 3-25. | MR 2312495 | Zbl 1113.65068

[5] J. Barzilai and J. Borwein, Two point step size gradient methods. IMA J. Num. Anal. 8 (1988) 141-148. | MR 967848 | Zbl 0638.65055

[6] M. Cheney, D. Isaacson and J.C. Newell, Electrical impedance tomography. SIAM Review 41 (1999) 85-101. | MR 1669729 | Zbl 0927.35130

[7] E. Chung, T. Chan and X. Tai, Electrical impedance tomography using level set representations and total variation regularization. J. Comp. Phys. 205 (2005) 357-372. | MR 2132313 | Zbl 1072.65143

[8] Y. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100 (2005) 21-47. | MR 2129700 | Zbl 1068.65073

[9] Y. Dai, W. Hager, K. Schittkowsky and H. Zhang, A cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Num. Anal. 26 (2006) 604-627. | MR 2241317 | Zbl 1147.65315

[10] H.W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems. Kluwer (1996). | MR 1408680 | Zbl 0859.65054

[11] M. Figueiredo, R. Nowak and S. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1 (2007) 586-598.

[12] G.E. Forsythe, On the asymptotic directions of the s-dimensional optimum gradient method. Numer. Math. 11 (1968) 57-76. | MR 223071 | Zbl 0153.46004

[13] A. Friedlander, J. Martinez, B. Molina and M. Raydan, Gradient method with retard and generalizations. SIAM J. Num. Anal. 36 (1999) 275-289. | MR 1664812 | Zbl 0940.65032

[14] G. Golub and Q. Ye, Inexact preconditioned conjugate gradient method with inner-outer iteration. SIAM J. Sci. Comp. 21 (2000) 1305-1320. | MR 1740397 | Zbl 0955.65022

[15] A. Greenbaum, Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, USA (1997). | MR 1474725 | Zbl 0883.65022

[16] E. Haber and U. Ascher, Preconditioned all-at-one methods for large, sparse parameter estimation problems. Inverse Problems 17 (2001) 1847-1864. | MR 1872925 | Zbl 0995.65110

[17] E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Second Edition, Springer (1996). | MR 1439506 | Zbl 0859.65067

[18] H. Huang, Efficient Reconstruction of 2D Images and 3D Surfaces. Ph.D. Thesis, University of BC, Vancouver, Canada (2008).

[19] W. Hundsdorfer and J.G. Verwer, Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations. Springer (2003). | MR 2002152 | Zbl 1030.65100

[20] Y. Li and D.W. Oldenburg, Inversion of 3-D DC resistivity data using an approximate inverse mapping. Geophys. J. Int. 116 (1994) 557-569.

[21] J. Nagy and K. Palmer, Steepest descent, CG and iterative regularization of ill-posed problems. BIT 43 (2003) 1003-1017. | MR 2058881 | Zbl 1045.65034

[22] J. Nocedal and S. Wright, Numerical Optimization. Springer, New York (1999). | MR 1713114 | Zbl 0930.65067

[23] J. Nocedal, A. Sartenar and C. Zhu, On the behavior of the gradient norm in the steepest descent method. Comput. Optim. Appl. 22 (2002) 5-35. | MR 1901251 | Zbl 1008.90057

[24] S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces. Springer (2003). | MR 1939127 | Zbl 1026.76001

[25] P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12 (1990) 629-639.

[26] L. Pronzato, H. Wynn and A. Zhigljavsky, Dynamical Search: Applications of Dynamical Systems in Search and Optimization. Chapman & Hall/CRC, Boca Raton (2000). | MR 1707340 | Zbl 1053.90102

[27] M. Raydan and B. Svaiter, Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21 (2002) 155-167. | MR 1883751 | Zbl 0988.90049

[28] R. Sincovec and N. Madsen, Software for nonlinear partial differential equations. ACM Trans. Math. Software 1 (1975) 232-260. | Zbl 0311.65057

[29] N.C. Smith and K. Vozoff, Two dimensional DC resistivity inversion for dipole dipole data. IEEE Trans. Geosci. Remote Sens. 22 (1984) 21-28.

[30] G. Strang and G. Fix, An Analysis of the Finite Element Method. Prentice-Hall, Engelwood Cliffs, NJ (1973). | MR 443377 | Zbl 0356.65096

[31] E. Tadmor, S. Nezzar and L. Vese, A multiscale image representation using hierarchical (BV, ${L}^{2}$) decompositions. SIAM J. Multiscale Model. Simul. 2 (2004) 554-579. | MR 2113170 | Zbl 1146.68472

[32] E. Van Den Berg and M. Friedlander, Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31 (2008) 840-912. | MR 2466141

[33] K. Van Den Doel and U. Ascher, On level set regularization for highly ill-posed distributed parameter estimation problems. J. Comp. Phys. 216 (2006) 707-723. | MR 2235390 | Zbl 1097.65112

[34] K. Van Den Doel and U. Ascher, Dynamic level set regularization for large distributed parameter estimation problems. Inverse Problems 23 (2007) 1271-1288. | MR 2329944 | Zbl 1117.65147

[35] C. Vogel, Computational methods for inverse problem. SIAM, Philadelphia, USA (2002). | MR 1928831 | Zbl 1008.65103

[36] J. Weickert, Anisotropic Diffusion in Image Processing. B.G. Teubner, Stuttgart (1998). | MR 1666943 | Zbl 0886.68131