Contractivity of Runge-Kutta methods for convex gradient systems
share
We consider the application of Runge-Kutta (RK) methods to gradient systems (d/dt)x = -∇ V(x), where, as in many optimization problems, V is convex and ∇ V (globally) Lipschitz-continuous with Lipschitz constant L. Solutions of this system behave contractively, i.e. the distance between two solutions x(t) and x(t) is a nonincreasing function of t. It is then of interest to investigate whether a similar contraction takes place, at least for suitably small step sizes h, for the discrete solution. We prove that there are RK schemes that for arbitrarily small h do not behave contractively. We derive a sufficient condition that guarantees the contractivity of a given RK method for a given h. It turns out that there are explicit RK schemes that behave contractively whenever Lh is below a scheme-dependent constant, which is some cases coincides with the one given by linear stability analysis. We show that, among all consistent, explicit RK methods, Euler's rule is optimal in this regard.
READ FULL TEXT