PDE acceleration: a convergence rate analysis and applications to obstacle problems

DOI10.1007/S40687-019-0197-XMaRDI QIDQ2336046zbMATH OpenOpenAlexFDO

Authors Jeff Calder, Anthony Yezzi

Publication date 18 November 2019

Published in Research in the Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

accelerated gradient descentminimal surfacesNesterov accelerationnonlinear wave equationsprimal-dual methodsstochastic homogenization

Mathematics Subject Classification ID

Variational methods applied to PDEs (35A15) PDEs in connection with control and optimization (35Q93) PDEs on infinite-dimensional (e.g., function) spaces (= PDEs in infinitely many variables) (35R15) Optimality conditions for problems involving partial differential equations (49K20) Acceleration of convergence in numerical analysis (65B99) Numerical optimization and variational techniques (65K10) Finite difference methods for initial value and initial-boundary value problems involving PDEs (65M06) Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs (65M12)

Abstract: This paper provides a rigorous convergence rate and complexity analysis for a recently introduced framework, called PDE acceleration, for solving problems in the calculus of variations, and explores applications to obstacle problems. PDE acceleration grew out of a variational interpretation of momentum methods, such as Nesterov's accelerated gradient method and Polyak's heavy ball method, that views acceleration methods as equations of motion for a generalized Lagrangian action. Its application to convex variational problems yields equations of motion in the form of a damped nonlinear wave equation rather than nonlinear diffusion arising from gradient descent. These accelerated PDE's can be efficiently solved with simple explicit finite difference schemes where acceleration is realized by an improvement in the CFL condition from $dtsimd{x}^2$ for diffusion equations to $dtsimdx$ for wave equations. In this paper, we prove a linear convergence rate for PDE acceleration for strongly convex problems, provide a complexity analysis of the discrete scheme, and show how to optimally select the damping parameter for linear problems. We then apply PDE acceleration to solve minimal surface obstacle problems, including double obstacles with forcing, and stochastic homogenization problems with obstacles, obtaining state of the art computational results.

Recommendations

• Accelerated variational PDEs for efficient solution of regularized inversion problems
• Accelerated Optimization in the PDE Framework Formulations for the Active Contour Case
• Primal-dual extragradient methods for nonlinear nonsmooth PDE-constrained optimization
• Acceleration and global convergence of a first-order primal-dual method for nonconvex problems
• Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order o(1/k^2)

Cites work

• A fast algorithm for Euler's elastica model using augmented Lagrangian method
• A minimal surface criterion for graph partitioning
• A variational perspective on accelerated methods in optimization
• Accelerated Optimization in the PDE Framework Formulations for the Active Contour Case
• Accelerated Optimization in the PDE Framework: Formulations for the Manifold of Diffeomorphisms
• Accelerated variational PDEs for efficient solution of regularized inversion problems
• Active contours without edges
• ADAPTIVE FINITE ELEMENT METHODS FOR THE OBSTACLE PROBLEM
• An \(L^1\) penalty method for general obstacle problems
• An accelerated method for nonlinear elliptic PDE
• An algorithm for solving the double obstacle problems
• An efficient primal-dual method for the obstacle problem
• An iterative method for elliptic problems with rapidly oscillating coefficients
• Convergence analysis of a conforming adaptive finite element method for an obstacle problem
• Convergence Rate Analysis of a Multiplicative Schwarz Method for Variational Inequalities
• Cyclic schemes for PDE-based image analysis
• Fourth-order partial differential equations for noise removal
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 2163369 (Why is no real title available?)
• scientific article; zbMATH DE number 5180707 (Why is no real title available?)
• Image denoising using mean curvature of image surface
• Large-scale machine learning with stochastic gradient descent
• Méthodes d'approximation et d'itération pour les opérateurs monotones
• Multigrid Algorithms for Variational Inequalities
• Multilevel projection algorithm for solving obstacle problems
• Nonlinear total variation based noise removal algorithms
• Numerical solution of the obstacle problem by the penalty method
• Obstacle problems with cohesion: a hemivariational inequality approach and its efficient numerical solution
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• Quantitative stochastic homogenization and large-scale regularity
• Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities
• Some methods of speeding up the convergence of iteration methods
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• The calculus of variations and materials science
• The gradient and heavy ball with friction dynamical systems: The quasiconvex case
• THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
• The obstacle problem revisited
• The Primal-Dual Active Set Strategy as a Semismooth Newton Method
• User’s guide to viscosity solutions of second order partial differential equations

Cited in

(5)

• Preconditioned accelerated gradient descent methods for locally Lipschitz smooth objectives with applications to the solution of nonlinear PDEs
• Accelerated Optimization in the PDE Framework: Formulations for the Manifold of Diffeomorphisms
• Convergence Acceleration for Time-Dependent Parametric Multifidelity Models
• A primal-dual level set method for computing geodesic distances
• Accelerated gradient flows for large bending deformations of nonlinear plates

This page was built for publication: PDE acceleration: a convergence rate analysis and applications to obstacle problems

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