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

Chen, Long; Hu, Xiaozhe; Wise, Steven

doi:10.1090/mcom/3526

Convergence analysis of the Fast Subspace Descent method for convex optimization problems
HTML articles powered by AMS MathViewer

by Long Chen, Xiaozhe Hu and Steven M. Wise;

Math. Comp. 89 (2020), 2249-2282

DOI: https://doi.org/10.1090/mcom/3526

Published electronically: April 7, 2020

HTML | PDF | Request permission

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

Kendall Atkinson and Weimin Han, Theoretical numerical analysis, 3rd ed., Texts in Applied Mathematics, vol. 39, Springer, Dordrecht, 2009. A functional analysis framework. MR 2511061, DOI 10.1007/978-1-4419-0458-4
Amir Beck and Luba Tetruashvili, On the convergence of block coordinate descent type methods, SIAM J. Optim. 23 (2013), no. 4, 2037–2060. MR 3116649, DOI 10.1137/120887679
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
Achi Brandt and Oren E. Livne, Multigrid techniques—1984 guide with applications to fluid dynamics, Classics in Applied Mathematics, vol. 67, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. Revised edition of the 1984 original [ MR0772748]. MR 3396211, DOI 10.1137/1.9781611970753
L. Chen, Mesh smoothing schemes based on optimal Delaunay triangulations, 13th International Meshing Roundtable, pages 109–120, Williamsburg, VA, 2004. Sandia National Laboratories.
L. Chen, iFEM: An Integrated Finite Element Methods Package in MATLAB, Technical Report, University of California at Irvine, 2009.
Long Chen and Jin-chao Xu, Optimal Delaunay triangulations, J. Comput. Math. 22 (2004), no. 2, 299–308. Special issue dedicated to the 70th birthday of Professor Zhong-Ci Shi. MR 2058939
Philippe G. Ciarlet, Introduction to numerical linear algebra and optimisation, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 1989. With the assistance of Bernadette Miara and Jean-Marie Thomas; Translated from the French by A. Buttigieg. MR 1015713
Ivar Ekeland and Roger Temam, Convex analysis and variational problems, Studies in Mathematics and its Applications, Vol. 1, North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1976. Translated from the French. MR 463994
Wenqiang Feng, Abner J. Salgado, Cheng Wang, and Steven M. Wise, Preconditioned steepest descent methods for some nonlinear elliptic equations involving p-Laplacian terms, J. Comput. Phys. 334 (2017), 45–67. MR 3606217, DOI 10.1016/j.jcp.2016.12.046
E. Gelman and J. Mandel, On multilevel iterative methods for optimization problems, Math. Programming 48 (1990), no. 1, (Ser. B), 1–17. MR 1049769, DOI 10.1007/BF01582249
Serge Gratton, Annick Sartenaer, and Philippe L. Toint, Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim. 19 (2008), no. 1, 414–444. MR 2403039, DOI 10.1137/050623012
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
V. E. Henson, Multigrid methods for nonlinear problems: an overview, submitted to the conference proceedings of the SPIE 15th Annual Symposium on Electronic Imaging, 2005.
Z. Hu, S. M. Wise, C. Wang, and J. S. Lowengrub, Stable and efficient finite-difference nonlinear-multigrid schemes for the phase field crystal equation, J. Comput. Phys. 228 (2009), no. 15, 5323–5339. MR 2541456, DOI 10.1016/j.jcp.2009.04.020
Jian Huang, Long Chen, and Hongxing Rui, Multigrid methods for a mixed finite element method of the Darcy-Forchheimer model, J. Sci. Comput. 74 (2018), no. 1, 396–411. MR 3742884, DOI 10.1007/s10915-017-0466-z
Robert Michael Lewis and Stephen G. Nash, Model problems for the multigrid optimization of systems governed by differential equations, SIAM J. Sci. Comput. 26 (2005), no. 6, 1811–1837. MR 2196577, DOI 10.1137/S1064827502407792
Zhaosong Lu, Randomized block proximal damped Newton method for composite self-concordant minimization, SIAM J. Optim. 27 (2017), no. 3, 1910–1942. MR 3693609, DOI 10.1137/16M1082767
Stephen G. Nash, A multigrid approach to discretized optimization problems, Optim. Methods Softw. 14 (2000), no. 1-2, 99–116. International Conference on Nonlinear Programming and Variational Inequalities (Hong Kong, 1998). MR 1809605, DOI 10.1080/10556780008805795
Yu. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim. 22 (2012), no. 2, 341–362. MR 2968857, DOI 10.1137/100802001
Yurii Nesterov, Introductory lectures on convex optimization, Applied Optimization, vol. 87, Kluwer Academic Publishers, Boston, MA, 2004. A basic course. MR 2142598, DOI 10.1007/978-1-4419-8853-9
Arnold Reusken, Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems, Numer. Math. 52 (1988), no. 3, 251–277. MR 929572, DOI 10.1007/BF01398879
Arnold Reusken, Convergence of the multilevel full approximation scheme including the $V$-cycle, Numer. Math. 53 (1988), no. 6, 663–686. MR 955979, DOI 10.1007/BF01397135
R. M. Spitaleri, Full-FAS multigrid grid generation algorithms, Appl. Numer. Math. 32 (2000), no. 4, 483–494. Numerical grid generation-technologies for advanced simulations (Berlin, 1997). MR 1759311, DOI 10.1016/S0168-9274(99)00064-1
Xue-Cheng Tai, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities, Numer. Math. 93 (2003), no. 4, 755–786. MR 1961887, DOI 10.1007/s002110200404
Xue-Cheng Tai and Jinchao Xu, Subspace correction methods for convex optimization problems, Eleventh International Conference on Domain Decomposition Methods (London, 1998) DDM.org, Augsburg, 1999, pp. 130–139. MR 1827418
Xue-Cheng Tai and Jinchao Xu, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp. 71 (2002), no. 237, 105–124. MR 1862990, DOI 10.1090/S0025-5718-01-01311-4
Steven Wise, Junseok Kim, and John Lowengrub, Solving the regularized, strongly anisotropic Cahn-Hilliard equation by an adaptive nonlinear multigrid method, J. Comput. Phys. 226 (2007), no. 1, 414–446. MR 2356365, DOI 10.1016/j.jcp.2007.04.020
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
Irad Yavneh and Gregory Dardyk, A multilevel nonlinear method, SIAM J. Sci. Comput. 28 (2006), no. 1, 24–46. MR 2219286, DOI 10.1137/040613809