×

On the asymptotic convergence and acceleration of gradient methods. (English) Zbl 1481.90309

Summary: We consider the asymptotic behavior of a family of gradient methods, which include the steepest descent and minimal gradient methods as special instances. It is proved that each method in the family will asymptotically zigzag between two directions. Asymptotic convergence results of the objective value, gradient norm, and stepsize are presented as well. To accelerate the family of gradient methods, we further exploit spectral properties of stepsizes to break the zigzagging pattern. In particular, a new stepsize is derived by imposing finite termination on minimizing two-dimensional strictly convex quadratic function. It is shown that, for the general quadratic function, the proposed stepsize asymptotically converges to the reciprocal of the largest eigenvalue of the Hessian. Furthermore, based on this spectral property, we propose a periodic gradient method by incorporating the Barzilai-Borwein method. Numerical comparisons with some recent successful gradient methods show that our new method is very promising.

MSC:

90C52 Methods of reduced gradient type
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Akaike, H., On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Stat. Math., 11, 1, 1-16 (1959) · Zbl 0100.14002 · doi:10.1007/BF01831719
[2] Barzilai, J.; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 1, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[3] Birgin, EG; Martínez, JM; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 4, 1196-1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[4] Cauchy, A., Méthode générale pour la résolution des systemes déquations simultanées, Comp. Rend. Sci. Paris, 25, 536-538 (1847)
[5] Dai, YH, Alternate step gradient method, Optimization, 52, 4-5, 395-415 (2003) · Zbl 1056.65055 · doi:10.1080/02331930310001611547
[6] Dai, YH; Fletcher, R., On the asymptotic behaviour of some new gradient methods, Math. Program., 103, 3, 541-559 (2005) · Zbl 1099.90038 · doi:10.1007/s10107-004-0516-9
[7] Dai, YH; Huang, Y.; Liu, XW, A family of spectral gradient methods for optimization, Comput. Optim. Appl., 74, 1, 43-65 (2019) · Zbl 1427.90260 · doi:10.1007/s10589-019-00107-8
[8] Dai, YH; Liao, LZ, \(R\)-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal., 22, 1, 1-10 (2002) · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[9] Dai, YH; Yang, X., A new gradient method with an optimal stepsize property, Comput. Optim. Appl., 33, 1, 73-88 (2006) · Zbl 1103.90099 · doi:10.1007/s10589-005-5959-2
[10] Dai, YH; Yuan, YX, Alternate minimization gradient method, IMA J. Numer. Anal., 23, 3, 377-393 (2003) · Zbl 1055.65073 · doi:10.1093/imanum/23.3.377
[11] Dai, YH; Yuan, YX, Analysis of monotone gradient methods, J. Ind. Mang. Optim., 1, 2, 181 (2005) · Zbl 1071.65084
[12] De Asmundis, R.; Di Serafino, D.; Hager, WW; Toraldo, G.; Zhang, H., An efficient gradient method using the Yuan steplength, Comput. Optim. Appl., 59, 3, 541-563 (2014) · Zbl 1310.90082 · doi:10.1007/s10589-014-9669-5
[13] De Asmundis, R.; di Serafino, D.; Riccio, F.; Toraldo, G., On spectral properties of steepest descent methods, IMA J. Numer. Anal., 33, 4, 1416-1435 (2013) · Zbl 1321.65095 · doi:10.1093/imanum/drs056
[14] Di Serafino, D.; Ruggiero, V.; Toraldo, G.; Zanni, L., On the steplength selection in gradient methods for unconstrained optimization, Appl. Math. Comput., 318, 176-195 (2018) · Zbl 1426.65082
[15] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[16] Elman, HC; Golub, GH, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31, 6, 1645-1661 (1994) · Zbl 0815.65041 · doi:10.1137/0731085
[17] Fletcher, R., On the Barzilai-Borwein method, Optimization and Control with Applications, 235-256 (2005), Boston: Springer, Boston · Zbl 1118.90318 · doi:10.1007/0-387-24255-4_10
[18] Forsythe, GE, On the asymptotic directions of the s-dimensional optimum gradient method, Numer. Math., 11, 1, 57-76 (1968) · Zbl 0153.46004 · doi:10.1007/BF02165472
[19] Frassoldati, G.; Zanni, L.; Zanghirati, G., New adaptive stepsize selections in gradient methods, J. Ind. Mang. Optim., 4, 2, 299 (2008) · Zbl 1161.90524
[20] Gonzaga, CC; Schneider, RM, On the steepest descent algorithm for quadratic functions, Comput. Optim. Appl., 63, 2, 523-542 (2016) · Zbl 1360.90183 · doi:10.1007/s10589-015-9775-z
[21] Huang, Y.; Dai, YH; Liu, XW; Zhang, H., Gradient methods exploiting spectral properties, Optim. Method Softw., 35, 4, 681-705 (2020) · Zbl 1454.90042 · doi:10.1080/10556788.2020.1727476
[22] Huang, Y.; Liu, H., Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization, Comput. Optim. Appl., 65, 3, 671-698 (2016) · Zbl 1357.90117 · doi:10.1007/s10589-016-9854-9
[23] Huang, Y.; Liu, H.; Zhou, S., Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization, Data Min. Knowl. Disc., 29, 6, 1665-1684 (2015) · Zbl 1405.65060 · doi:10.1007/s10618-014-0390-x
[24] Jiang, B.; Dai, YH, Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems, Optim. Method Softw., 28, 4, 756-784 (2013) · Zbl 1302.90209 · doi:10.1080/10556788.2012.656115
[25] Liu, YF; Dai, YH; Luo, ZQ, Coordinated beamforming for miso interference channel: Complexity analysis and efficient algorithms, IEEE Trans. Signal Process., 59, 3, 1142-1157 (2011) · Zbl 1392.94315 · doi:10.1109/TSP.2010.2092772
[26] Nocedal, J.; Sartenaer, A.; Zhu, C., On the behavior of the gradient norm in the steepest descent method, Comp. Optim. Appl., 22, 1, 5-35 (2002) · Zbl 1008.90057 · doi:10.1023/A:1014897230089
[27] Pronzato, L.; Wynn, HP; Zhigljavsky, AA, Asymptotic behaviour of a family of gradient algorithms in \(R^d\) and Hilbert spaces, Math. program., 107, 3, 409-438 (2006) · Zbl 1111.90085 · doi:10.1007/s10107-005-0602-7
[28] Raydan, M., On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal., 13, 3, 321-326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[29] Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 1, 26-33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[30] Sun, C.; Liu, JP, New stepsizes for the gradient method, Optim. Lett., 14, 1943-1955 (2020) · Zbl 1459.90224 · doi:10.1007/s11590-019-01512-y
[31] Yuan, YX, A new stepsize for the steepest descent method, J. Comput. Math., 24, 2, 149-156 (2006) · Zbl 1101.65067
[32] Yuan, YX, Step-sizes for the gradient method, AMS IP Stud. Adv. Math., 42, 2, 785-796 (2008) · Zbl 1172.90509
[33] Zhou, B.; Gao, L.; Dai, YH, Gradient methods with adaptive step-sizes, Comput. Optim. Appl., 35, 1, 69-86 (2006) · Zbl 1121.90099 · doi:10.1007/s10589-006-6446-0
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.