Gradient Descent and Fast Artificial Time Integration

Gradient Descent and Fast Atificial Time Integration

Uri Ascher1             Kees van den Doel1             Hui Huang1             Benar F. Svaiter2   

   1 University of British Columbia            2 Institute of Pure and Applied Mathematics    

 


Figure 1: Step size dynamics for A = diag(20, 10, 2, 1). (a) The greedy strategies produce orderly dynamical systems which have a steady state or are two-periodic. Forward Euler absolute stability limit, depicted here as ‘Estab’, therefore decrees slow convergence. (b) When this pattern is broken a faster convergence to steady state results.

 

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. 


BibTex
@ARTICLE{Huang2009,
title = {Gradient Descent and Fast Atificial Time Integration},
author = { Uri Ascher and Kees van den Doel and Hui Huang and Benar F. Svaiter},
journal = {Mathematical Modelling and Numerical Analysis},

month = {07},

volume = {43},
pages = {689 - 708},
year = {2009},
}

Downloads (faster for people in China)

Downloads (faster for people in other places)