Convergence Analysis of the Fast Subspace Descent Methods for Convex Optimization Problems

2018/10/09 by Long Chen, Chen, Long, Xiaozhe Hu +3
Computer Science · Engineering · Physics and Astronomy · #65J15 #65K10 #65N22 #65N55 #Advanced Numerical Methods in Computational Mathematics #FOS: Mathematics #Matrix Theory and Algorithms #Model Reduction and Neural Networks #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1810.04116

openalex publication_date 2018/10/09 · openalex created_date 2019/10/25 · openalex updated_date 2026/07/28

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.

Citations

• Solving the regularized, strongly anisotropic Cahn–Hilliard equation by an adaptive nonlinear multigrid method

Related

• Randomized subspace correction methods for convex optimization
• Randomized Fast Subspace Descent Methods
• A simple uniformly optimal method without line search for convex optimization
• Connections between convex optimization algorithms and subspace correction methods
• Numerical Design of Optimized First-Order Algorithms