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

DOI10.1007/S40687-019-0197-XzbMATH Open1427.65145arXiv1810.01066OpenAlexW2982582408MaRDI QIDQ2336046FDOQ2336046

Authors: Jeff Calder, Anthony Yezzi 

Publication date: 18 November 2019

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

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.

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

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)\)

zbMATH Keywords

accelerated gradient descentminimal surfacesstochastic homogenizationnonlinear wave equationsprimal-dual methodsNesterov acceleration

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Variational methods applied to PDEs (35A15) PDEs in connection with control and optimization (35Q93) Optimality conditions for problems involving partial differential equations (49K20) 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) PDEs on infinite-dimensional (e.g., function) spaces (= PDEs in infinitely many variables) (35R15) Acceleration of convergence in numerical analysis (65B99)

Cites Work

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

Cited In (3)

• 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

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)