Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Convergence analysis of the Fast Subspace Descent method for convex optimization problems


Authors: Long Chen, Xiaozhe Hu and Steven M. Wise
Journal: Math. Comp. 89 (2020), 2249-2282
MSC (2010): Primary 65N55, 65N22, 65K10, 65J15
DOI: https://doi.org/10.1090/mcom/3526
Published electronically: April 7, 2020
MathSciNet review: 4109566
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

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 for convex optimization problems.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65N55, 65N22, 65K10, 65J15

Retrieve articles in all journals with MSC (2010): 65N55, 65N22, 65K10, 65J15


Additional Information

Long Chen
Affiliation: Department of Mathematics, University of California at Irvine, Irvine, California 92697
Email: chenlong@math.uci.edu

Xiaozhe Hu
Affiliation: Department of Mathematics, Tuffs University, Medford, Massachussetts 02155
Email: Xiaozhe.Hu@tufts.edu

Steven M. Wise
Affiliation: Department of Mathematics, The University of Tennessee, Knoxville, Tennessee 37996
Email: swise1@utk.edu

DOI: https://doi.org/10.1090/mcom/3526
Received by editor(s): October 2, 2018
Received by editor(s) in revised form: July 1, 2019, October 19, 2019, and January 10, 2020
Published electronically: April 7, 2020
Additional Notes: The second author was supported by NSF Grant DMS-1620063.
The third author was supported by the NSF Grant DMS-1719854.
Article copyright: © Copyright 2020 American Mathematical Society