Contractivity of Runge-Kutta methods for convex gradient systems

DOI10.1137/19M1299256MaRDI QIDQ5115704zbMATH OpenOpenAlexFDO

Authors Jesús María Sanz-Serna, Konstantinos C. Zygalakis

Publication date 18 August 2020

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.09971

zbMATH Keywords

convex optimizationnumerical stabilityRunge-Kutta methods

Mathematics Subject Classification ID

Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations (65L06) Stability and convergence of numerical methods for ordinary differential equations (65L20) Convex programming (90C25)

Abstract: We consider the application of Runge-Kutta (RK) methods to gradient systems $(d/dt)x=-ablaV(x)$, where, as in many optimization problems, $V$ is convex and $ablaV$ (globally) Lipschitz-continuous with Lipschitz constant $L$. Solutions of this system behave contractively, i.e. the Euclidean distance between two solutions $x(t)$ and $widetildex(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. Dahlquist and Jeltsch results' imply that (1) there are explicit RK schemes that behave contractively whenever $Lh$ is below a scheme-dependent constant and (2) Euler's rule is optimal in this regard. We prove however, by explicit construction of a convex potential using ideas from robust control theory, that there exists RK schemes that fail to behave contractively for any choice of the time-step $h$.

Recommendations

• Contractivity of Runge-Kutta methods
• Runge–Kutta Methods for Dissipative and Gradient Dynamical Systems
• An energy stable Runge-Kutta method for convex gradient problems
• scientific article; zbMATH DE number 176981
• Runge-Kutta discretizations of singularly perturbed gradient equations

Cites work

• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• A special stability problem for linear multistep methods
• A stability property of implicit Runge-Kutta methods
• A variational perspective on accelerated methods in optimization
• Analysis and design of optimization algorithms via integral quadratic constraints
• Analysis of optimization algorithms via integral quadratic constraints: nonstrongly convex problems
• Contractivity of Runge-Kutta methods
• Energy-diminishing integration of gradient systems
• scientific article; zbMATH DE number 3911612 (Why is no real title available?)
• scientific article; zbMATH DE number 3548346 (Why is no real title available?)
• scientific article; zbMATH DE number 940566 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Monotonicity for Runge-Kutta methods: inner product norms
• Multivariate convexity preserving interpolation by smooth functions
• Numerical Methods for Ordinary Differential Equations
• Piecewise linear interpolants to Lagrange and Hermite convex scattered data
• Reducibility and contractivity of Runge-Kutta methods revisited
• Runge–Kutta Methods for Dissipative and Gradient Dynamical Systems
• Stability Criteria for Implicit Runge–Kutta Methods
• Symplectic Runge-Kutta schemes for adjoint equations, automatic differentiation, optimal control, and more

Cited in

(11)

• Contractivity of Runge-Kutta methods
• SRKCD: a stabilized Runge-Kutta method for stochastic optimization
• Asymptotic error in Euler's method with a constant step size
• Runge-Kutta-like scaling techniques for first-order methods in convex optimization
• scientific article; zbMATH DE number 176981 (Why is no real title available?)
• A Note on Unconditional Maximum Norm Contractivity of Diagonally Split Runge–Kutta Methods
• The connections between Lyapunov functions for some optimization algorithms and differential equations
• scientific article; zbMATH DE number 7626757 (Why is no real title available?)
• Designing stable neural networks using convex analysis and ODEs
• Contraction rate estimates of stochastic gradient kinetic Langevin integrators
• Exponential contractivity and error estimates of IMEX Euler method for nonlinear perturbed dissipative systems in seminormed space

This page was built for publication: Contractivity of Runge-Kutta methods for convex gradient systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115704)