×

Convergence analysis of the fast subspace descent method for convex optimization problems. (English) Zbl 1442.65426

Summary: 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.

MSC:

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

Software:

iFEM
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Atkinson, Kendall; Han, Weimin, Theoretical Numerical Analysis, 3rd ed., Texts in Applied Mathematics 39, xvi+625 pp. (2009), Springer, Dordrecht · Zbl 1181.47078 · doi:10.1007/978-1-4419-0458-4
[2] Beck, Amir; Tetruashvili, Luba, On the convergence of block coordinate descent type methods, SIAM J. Optim., 23, 4, 2037-2060 (2013) · Zbl 1297.90113 · doi:10.1137/120887679
[3] Brandt, Achi, Multi-level adaptive solutions to boundary-value problems, Math. Comp., 31, 138, 333-390 (1977) · Zbl 0373.65054 · doi:10.2307/2006422
[4] Brandt, Achi; Livne, Oren E., Multigrid techniques-1984 guide with applications to fluid dynamics, Classics in Applied Mathematics 67, xx+218 pp. (2011), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1227.65121 · doi:10.1137/1.9781611970753
[5] Chen.L2004 L. Chen, Mesh smoothing schemes based on optimal Delaunay triangulations, 13th International Meshing Roundtable, pages 109-120, Williamsburg, VA, 2004. Sandia National Laboratories.
[6] Chen.L2008c L. Chen, iFEM: An Integrated Finite Element Methods Package in MATLAB, Technical Report, University of California at Irvine, 2009.
[7] Chen, Long; Xu, J., Optimal Delaunay triangulations, J. Comput. Math., 22, 2, 299-308 (2004) · Zbl 1048.65020
[8] Ciarlet, Philippe G., Introduction to numerical linear algebra and optimisation, Cambridge Texts in Applied Mathematics, xiv+436 pp. (1989), Cambridge University Press, Cambridge
[9] Ekeland, Ivar; Temam, Roger, Convex Analysis and Variational Problems, ix+402 pp. (1976), North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York · Zbl 0939.49002
[10] Feng, Wenqiang; Salgado, Abner J.; Wang, Cheng; Wise, Steven M., Preconditioned steepest descent methods for some nonlinear elliptic equations involving p-Laplacian terms, J. Comput. Phys., 334, 45-67 (2017) · Zbl 1375.35149 · doi:10.1016/j.jcp.2016.12.046
[11] Gelman, E.; Mandel, J., On multilevel iterative methods for optimization problems, Math. Programming, 48, 1, (Ser. B), 1-17 (1990) · Zbl 0738.90059 · doi:10.1007/BF01582249
[12] Gratton, Serge; Sartenaer, Annick; Toint, Philippe L., Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim., 19, 1, 414-444 (2008) · Zbl 1163.90024 · doi:10.1137/050623012
[13] Hackbusch, Wolfgang, Multigrid Methods and Applications, Springer Series in Computational Mathematics 4, xiv+377 pp. (1985), Springer-Verlag, Berlin · Zbl 0595.65106 · doi:10.1007/978-3-662-02427-0
[14] Henson.V2005 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.
[15] Hu, Z.; Wise, S. M.; Wang, C.; Lowengrub, J. S., Stable and efficient finite-difference nonlinear-multigrid schemes for the phase field crystal equation, J. Comput. Phys., 228, 15, 5323-5339 (2009) · Zbl 1171.82015 · doi:10.1016/j.jcp.2009.04.020
[16] Huang, Jian; Chen, Long; Rui, Hongxing, Multigrid methods for a mixed finite element method of the Darcy-Forchheimer model, J. Sci. Comput., 74, 1, 396-411 (2018) · Zbl 1404.65267 · doi:10.1007/s10915-017-0466-z
[17] Lewis, Robert Michael; Nash, Stephen G., Model problems for the multigrid optimization of systems governed by differential equations, SIAM J. Sci. Comput., 26, 6, 1811-1837 (2005) · Zbl 1119.65346 · doi:10.1137/S1064827502407792
[18] Lu, Zhaosong, Randomized block proximal damped Newton method for composite self-concordant minimization, SIAM J. Optim., 27, 3, 1910-1942 (2017) · Zbl 1375.49040 · doi:10.1137/16M1082767
[19] Nash, Stephen G., A multigrid approach to discretized optimization problems, Optim. Methods Softw., 14, 1-2, 99-116 (2000) · Zbl 0988.90040 · doi:10.1080/10556780008805795
[20] Nesterov, Y., Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22, 2, 341-362 (2012) · Zbl 1257.90073 · doi:10.1137/100802001
[21] Nesterov, Yurii, Introductory Lectures on Convex Optimization, A basic course. Applied Optimization 87, xviii+236 pp. (2004), Kluwer Academic Publishers, Boston, MA · Zbl 1086.90045 · doi:10.1007/978-1-4419-8853-9
[22] Reusken, Arnold, Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems, Numer. Math., 52, 3, 251-277 (1988) · Zbl 0617.65108 · doi:10.1007/BF01398879
[23] Reusken, Arnold, Convergence of the multilevel full approximation scheme including the \(V\)-cycle, Numer. Math., 53, 6, 663-686 (1988) · Zbl 0636.65107 · doi:10.1007/BF01397135
[24] Spitaleri, R. M., Full-FAS multigrid grid generation algorithms, Appl. Numer. Math., 32, 4, 483-494 (2000) · Zbl 0973.65114 · doi:10.1016/S0168-9274(99)00064-1
[25] Tai, Xue-Cheng, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities, Numer. Math., 93, 4, 755-786 (2003) · Zbl 1057.65040 · doi:10.1007/s002110200404
[26] Tai, Xue-Cheng; Xu, Jinchao, Subspace correction methods for convex optimization problems. Eleventh International Conference on Domain Decomposition Methods, London, 1998, 130-139 (1999), DDM.org, Augsburg
[27] Tai, Xue-Cheng; Xu, Jinchao, Global and uniform convergence of subspace correction methods for some convex optimization problems, Math. Comp., 71, 237, 105-124 (2002) · Zbl 0985.65065 · doi:10.1090/S0025-5718-01-01311-4
[28] Wise, Steven; Kim, Junseok; Lowengrub, John, Solving the regularized, strongly anisotropic Cahn-Hilliard equation by an adaptive nonlinear multigrid method, J. Comput. Phys., 226, 1, 414-446 (2007) · Zbl 1310.82044 · doi:10.1016/j.jcp.2007.04.020
[29] Xu, Jinchao, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34, 4, 581-613 (1992) · Zbl 0788.65037 · doi:10.1137/1034116
[30] Yavneh, Irad; Dardyk, Gregory, A multilevel nonlinear method, SIAM J. Sci. Comput., 28, 1, 24-46 (2006) · Zbl 1109.65109 · doi:10.1137/040613809
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.