Gradient descent and fast artificial time integration

Uri M. Ascher; Kees van den Doel; Hui Huang; Benar F. Svaiter

ESAIM: Mathematical Modelling and Numerical Analysis (2009)

  • Volume: 43, Issue: 4, page 689-708
  • ISSN: 0764-583X

Abstract

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

How to cite

top

Ascher, Uri M., et al. "Gradient descent and fast artificial time integration." ESAIM: Mathematical Modelling and Numerical Analysis 43.4 (2009): 689-708. <http://eudml.org/doc/250599>.

@article{Ascher2009,
abstract = { 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. },
author = {Ascher, Uri M., van den Doel, Kees, Huang, Hui, Svaiter, Benar F.},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Steady state; artificial time; gradient descent; forward Euler; lagged steepest descent; regularization.; steady state; lagged steepest descent; regularization; numerical examples; finite volume method; initial value problems; Greedy algorithms; absolute stability},
language = {eng},
month = {7},
number = {4},
pages = {689-708},
publisher = {EDP Sciences},
title = {Gradient descent and fast artificial time integration},
url = {http://eudml.org/doc/250599},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Ascher, Uri M.
AU - van den Doel, Kees
AU - Huang, Hui
AU - Svaiter, Benar F.
TI - Gradient descent and fast artificial time integration
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2009/7//
PB - EDP Sciences
VL - 43
IS - 4
SP - 689
EP - 708
AB - 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.
LA - eng
KW - Steady state; artificial time; gradient descent; forward Euler; lagged steepest descent; regularization.; steady state; lagged steepest descent; regularization; numerical examples; finite volume method; initial value problems; Greedy algorithms; absolute stability
UR - http://eudml.org/doc/250599
ER -

References

top
  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. Tokyo11 (1959) 1–16.  Zbl0100.14002
  2. U. Ascher, Numerical Methods for Evolutionary Differential Equations. SIAM, Philadelphia, USA (2008).  Zbl1157.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.  Zbl1104.65320
  4. U. Ascher, H. Huang and K. van den Doel, Artificial time integration. BIT47 (2007) 3–25.  Zbl1113.65068
  5. J. Barzilai and J. Borwein, Two point step size gradient methods. IMA J. Num. Anal.8 (1988) 141–148.  Zbl0638.65055
  6. M. Cheney, D. Isaacson and J.C. Newell, Electrical impedance tomography. SIAM Review41 (1999) 85–101.  Zbl0927.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.  Zbl1072.65143
  8. Y. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math.100 (2005) 21–47.  Zbl1068.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.  Zbl1147.65315
  10. H.W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems. Kluwer (1996).  Zbl0859.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.  Zbl0153.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.  Zbl0940.65032
  14. G. Golub and Q. Ye, Inexact preconditioned conjugate gradient method with inner-outer iteration. SIAM J. Sci. Comp.21 (2000) 1305–1320.  Zbl0955.65022
  15. A. Greenbaum, Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, USA (1997).  Zbl0883.65022
  16. E. Haber and U. Ascher, Preconditioned all-at-one methods for large, sparse parameter estimation problems. Inverse Problems17 (2001) 1847–1864.  Zbl0995.65110
  17. E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Second Edition, Springer (1996).  Zbl0859.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).  Zbl1030.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. BIT43 (2003) 1003–1017.  Zbl1045.65034
  22. J. Nocedal and S. Wright, Numerical Optimization. Springer, New York (1999).  Zbl0930.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.  Zbl1008.90057
  24. S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces. Springer (2003).  Zbl1026.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).  Zbl1053.90102
  27. M. Raydan and B. Svaiter, Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl.21 (2002) 155–167.  Zbl0988.90049
  28. R. Sincovec and N. Madsen, Software for nonlinear partial differential equations. ACM Trans. Math. Software1 (1975) 232–260.  Zbl0311.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).  Zbl0356.65096
  31. E. Tadmor, S. Nezzar and L. Vese, A multiscale image representation using hierarchical (BV, L2) decompositions. SIAM J. Multiscale Model. Simul.2 (2004) 554–579.  Zbl1146.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.  Zbl1193.49033
  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.  Zbl1097.65112
  34. K. van den Doel and U. Ascher, Dynamic level set regularization for large distributed parameter estimation problems. Inverse Problems23 (2007) 1271–1288.  Zbl1117.65147
  35. C. Vogel, Computational methods for inverse problem. SIAM, Philadelphia, USA (2002).  Zbl1008.65103
  36. J. Weickert, Anisotropic Diffusion in Image Processing. B.G. Teubner, Stuttgart (1998).  Zbl0886.68131

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.