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.
Mots-clés : 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: Mod\'elisation math\'ematique et analyse num\'erique},
pages = {689--708},
publisher = {EDP-Sciences},
volume = {43},
number = {4},
year = {2009},
doi = {10.1051/m2an/2009025},
mrnumber = {2542872},
zbl = {1169.65329},
language = {en},
url = {http://www.numdam.org/articles/10.1051/m2an/2009025/}
}
TY - JOUR AU - Ascher, Uri M. AU - Kees van den Doel AU - Huang, Hui AU - Svaiter, Benar F. TI - Gradient descent and fast artificial time integration JO - ESAIM: Modélisation mathématique et analyse numérique PY - 2009 SP - 689 EP - 708 VL - 43 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an/2009025/ DO - 10.1051/m2an/2009025 LA - en ID - M2AN_2009__43_4_689_0 ER -
%0 Journal Article %A Ascher, Uri M. %A Kees van den Doel %A Huang, Hui %A Svaiter, Benar F. %T Gradient descent and fast artificial time integration %J ESAIM: Modélisation mathématique et analyse numérique %D 2009 %P 689-708 %V 43 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an/2009025/ %R 10.1051/m2an/2009025 %G en %F 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: Modélisation mathématique et analyse numérique, Special issue on Numerical ODEs today, Tome 43 (2009) no. 4, pp. 689-708. doi : 10.1051/m2an/2009025. http://www.numdam.org/articles/10.1051/m2an/2009025/
[1] , 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 | Zbl
[2] , Numerical Methods for Evolutionary Differential Equations. SIAM, Philadelphia, USA (2008). | MR | Zbl
[3] , and , On effective methods for implicit piecewise smooth surface recovery. SIAM J. Sci. Comput. 28 (2006) 339-358. | MR | Zbl
[4] , and , Artificial time integration. BIT 47 (2007) 3-25. | MR | Zbl
[5] and , Two point step size gradient methods. IMA J. Num. Anal. 8 (1988) 141-148. | MR | Zbl
[6] , and , Electrical impedance tomography. SIAM Review 41 (1999) 85-101. | MR | Zbl
[7] , and , Electrical impedance tomography using level set representations and total variation regularization. J. Comp. Phys. 205 (2005) 357-372. | MR | Zbl
[8] and , Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100 (2005) 21-47. | MR | Zbl
[9] , , and , A cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Num. Anal. 26 (2006) 604-627. | MR | Zbl
[10] , and , Regularization of Inverse Problems. Kluwer (1996). | MR | Zbl
[11] , and , Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1 (2007) 586-598.
[12] , On the asymptotic directions of the s-dimensional optimum gradient method. Numer. Math. 11 (1968) 57-76. | MR | Zbl
[13] , , and , Gradient method with retard and generalizations. SIAM J. Num. Anal. 36 (1999) 275-289. | MR | Zbl
[14] and , Inexact preconditioned conjugate gradient method with inner-outer iteration. SIAM J. Sci. Comp. 21 (2000) 1305-1320. | MR | Zbl
[15] , Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, USA (1997). | MR | Zbl
[16] and , Preconditioned all-at-one methods for large, sparse parameter estimation problems. Inverse Problems 17 (2001) 1847-1864. | MR | Zbl
[17] and , Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Second Edition, Springer (1996). | MR | Zbl
[18] , Efficient Reconstruction of 2D Images and 3D Surfaces. Ph.D. Thesis, University of BC, Vancouver, Canada (2008).
[19] and , Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations. Springer (2003). | MR | Zbl
[20] and , Inversion of 3-D DC resistivity data using an approximate inverse mapping. Geophys. J. Int. 116 (1994) 557-569.
[21] and , Steepest descent, CG and iterative regularization of ill-posed problems. BIT 43 (2003) 1003-1017. | MR | Zbl
[22] and , Numerical Optimization. Springer, New York (1999). | MR | Zbl
[23] , and , On the behavior of the gradient norm in the steepest descent method. Comput. Optim. Appl. 22 (2002) 5-35. | MR | Zbl
[24] and , Level Set Methods and Dynamic Implicit Surfaces. Springer (2003). | MR | Zbl
[25] and , Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12 (1990) 629-639.
[26] , and , Dynamical Search: Applications of Dynamical Systems in Search and Optimization. Chapman & Hall/CRC, Boca Raton (2000). | MR | Zbl
[27] and , Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21 (2002) 155-167. | MR | Zbl
[28] and , Software for nonlinear partial differential equations. ACM Trans. Math. Software 1 (1975) 232-260. | Zbl
[29] and , Two dimensional DC resistivity inversion for dipole dipole data. IEEE Trans. Geosci. Remote Sens. 22 (1984) 21-28.
[30] and , An Analysis of the Finite Element Method. Prentice-Hall, Engelwood Cliffs, NJ (1973). | MR | Zbl
[31] , and , A multiscale image representation using hierarchical (BV, ) decompositions. SIAM J. Multiscale Model. Simul. 2 (2004) 554-579. | MR | Zbl
[32] and , Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31 (2008) 840-912. | MR
[33] and , On level set regularization for highly ill-posed distributed parameter estimation problems. J. Comp. Phys. 216 (2006) 707-723. | MR | Zbl
[34] and , Dynamic level set regularization for large distributed parameter estimation problems. Inverse Problems 23 (2007) 1271-1288. | MR | Zbl
[35] , Computational methods for inverse problem. SIAM, Philadelphia, USA (2002). | MR | Zbl
[36] , Anisotropic Diffusion in Image Processing. B.G. Teubner, Stuttgart (1998). | MR | Zbl
Cité par Sources :
