Convergence analysis of the fast subspace descent method for convex optimization problems

DOI10.1090/MCOM/3526zbMATH Open1442.65426arXiv1810.04116OpenAlexW3005875771MaRDI QIDQ5113667FDOQ5113667

Long Chen, X. Hu, Steven Wise

Publication date: 15 June 2020

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: The full approximation storage (FAS) scheme is a widely used multigrid method for nonlinear problems. In this paper, a new framework to design and analyze FAS-like schemes for convex optimization problems is developed. The new method, the Fast Subspace Descent (FASD) scheme, which generalizes classical FAS, can be recast as an inexact version of nonlinear multigrid methods based on space decomposition and subspace correction. The local problem in each subspace can be simplified to be linear and one gradient descent iteration (with an appropriate step size) is enough to ensure a global linear (geometric) convergence of FASD.

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

Recommendations

• A new subspace correction method for nonlinear unconstrained convex optimization problems
• Global and uniform convergence of subspace correction methods for some convex optimization problems
• Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
• Additive Schwarz methods for convex optimization as gradient methods
• scientific article; zbMATH DE number 1981901

zbMATH Keywords

convergence analysisnonlinear PDEconvex optimization problemsfast subspace descent methodfull approximation storage (FAS) schemenonlineare multigrid method

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Numerical solutions to equations with nonlinear operators (65J15) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22)

Cites Work

• Introductory lectures on convex optimization. A basic course.
• Title not available (Why is that?)
• Theoretical Numerical Analysis
• Title not available (Why is that?)
• Stable and efficient finite-difference nonlinear-multigrid schemes for the phase field crystal equation
• Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
• Iterative Methods by Space Decomposition and Subspace Correction
• Multi-Level Adaptive Solutions to Boundary-Value Problems
• A multigrid approach to discretized optimization problems
• Model Problems for the Multigrid Optimization of Systems Governed by Differential Equations
• On the Convergence of Block Coordinate Descent Type Methods
• On multilevel iterative methods for optimization problems
• Multigrid Techniques
• Solving the regularized, strongly anisotropic Cahn-Hilliard equation by an adaptive nonlinear multigrid method
• Title not available (Why is that?)
• Global and uniform convergence of subspace correction methods for some convex optimization problems
• Full-FAS multigrid grid generation algorithms
• Preconditioned steepest descent methods for some nonlinear elliptic equations involving p-Laplacian terms
• Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems
• A Multilevel Nonlinear Method
• Convergence of the multilevel full approximation scheme including the V- cycle
• Multigrid methods for a mixed finite element method of the Darcy-Forchheimer model
• Randomized Block Proximal Damped Newton Method for Composite Self-Concordant Minimization

Cited In (9)

• Preconditioned accelerated gradient descent methods for locally Lipschitz smooth objectives with applications to the solution of nonlinear PDEs
• Additive Schwarz methods for convex optimization with backtracking
• Title not available (Why is that?)
• Numerical comparison of modified-energy stable SAV-type schemes and classical BDF methods on benchmark problems for the functionalized Cahn-Hilliard equation
• Asymptotic behaviour of time stepping methods for phase field models
• A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
• A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians
• Transformed primal-dual methods for nonlinear saddle point systems
• Convergence rate of a rectangular subdivision-based optimization algorithm for smooth multivariate functions

Uses Software

• iFEM

This page was built for publication: Convergence analysis of the fast subspace descent method for convex optimization problems

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