A Note on R-Linear Convergence of Nonmonotone Gradient Methods

doi:10.1007/s40305-023-00468-2

Abstract

Abstract: Nonmonotone gradient methods generally perform better than their monotone counterparts especially on unconstrained quadratic optimization. However, the known convergence rate of the monotone method is often much better than its nonmonotone variant. With the aim of shrinking the gap between theory and practice of nonmonotone gradient methods, we introduce a property for convergence analysis of a large collection of gradient methods. We prove that any gradient method using stepsizes satisfying the property will converge R-linearly at a rate of 1-λ₁/M₁, where λ₁ is the smallest eigenvalue of Hessian matrix and M₁ is the upper bound of the inverse stepsize. Our results indicate that the existing convergence rates of many nonmonotone methods can be improved to 1-1/κ with κ being the associated condition number.

Key words: Gradient methods, R-linear convergence, Nonmonotone, Quadratic optimization

CLC Number:

Xin-Rui Li, Ya-Kui Huang. A Note on R-Linear Convergence of Nonmonotone Gradient Methods[J]. Journal of the Operations Research Society of China, 2025, 13(1): 313-325.

TrendMD

References

[1] Cauchy, A.: Méthode générale pour la résolution des systemes di’équations simultanées. Comp. Rend. Sci. Paris 25, 536-538(1847)
[2] 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)
[3] Forsythe, G.E.: On the asymptotic directions of the s-dimensional optimum gradient method. Numer. Math. 11(1), 57-76(1968)
[4] Dai, Y.H., Yuan, Y.X.: Alternate minimization gradient method. IMA J. Numer. Anal. 23(3), 377-393(2003)
[5] Huang, Y.K., Dai, Y.H., Liu, X.W., et al.: On the asymptotic convergence and acceleration of gradient methods. J. Sci. Comput. 90, 7(2022)
[6] Dai, Y.H., Yang, X.: A new gradient method with an optimal stepsize property. Comp. Optim. Appl. 33(1), 73-88(2006)
[7] Elman, H.C., Golub, G.H.: Inexact and preconditioned Uzawa algorithms for saddle point problems. SIAM J. Numer. Anal. 31(6), 1645-1661(1994)
[8] Dai, Y.H., Yuan, Y.X.: Analysis of monotone gradient methods. J. Ind. Mang. Optim. 1(2), 181(2005)
[9] Yuan, Y.X.: A new stepsize for the steepest descent method. J. Comput. Math. 24(2), 149-156(2006)
[10] Yuan, Y.X.: Step-sizes for the gradient method. AMS/IP Stud. Adv. Math. 42(2), 785-796(2008)
[11] Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141-148(1988)
[12] Dai, Y.H.: A new analysis on the Barzilai-Borwein gradient method. J. Oper. Res. Soc. China 2(1), 187-198(2013)
[13] Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Math. Program. 103(3), 541-559(2005)
[14] Raydan, M.: On the Barzilai-Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13(3), 321-326(1993)
[15] Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai-Borwein gradient method. IMA J. Numer. Anal. 22(1), 1-10(2002)
[16] Li, D.W., Sun, R.Y.: On a faster R-Linear convergence rate of the Barzilai-Borwein method (2021). arXiv:2101.00205v2
[17] Dai, Y.H., Al-Baali, M., Yang, X.: A positive Barzilai-Borwein-like stepsize and an extension for symmetric linear systems. In: Numerical Analysis and Optimization, pp. 59-75. (2015)
[18] Burdakov, O., Dai, Y.H., Huang, N.: Stabilized Barzilai-Borwein method. J. Comput. Math. 37(6), 916-936(2019)
[19] Dai, Y.H., Huang, Y.K., Liu, X.W.: A family of spectral gradient methods for optimization. Comput. Optim. Appl. 74(1), 43-65(2019)
[20] 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)
[21] Fletcher, R.: On the Barzilai-Borwein method. In: Optimization and Control with Applications, pp. 235-256. Springer, New York (2005)
[22] Huang, Y.K., Dai, Y.H., Liu, X.W.: Equipping the Barzilai-Borwein method with the two dimensional quadratic termination property. SIAM J. Optim. 31(4), 3068-3096(2021)
[23] Raydan, M.: The Barzilai-Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7(1), 26-33(1997)
[24] Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10(4), 1196-1211(2000)
[25] Crisci, S., Porta, F., Ruggiero, V., Zanni, L.: Spectral properties of Barzilai-Borwein rules in solving singly linearly constrained optimization problems subject to lower and upper bounds. SIAM J. Optim. 30(2), 1300-1326(2020)
[26] Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100(1), 21-47(2005)
[27] Huang, Y.K., Liu, H.: Smoothing projected Barzilai-Borwein method for constrained non-lipschitz optimization. Comp. Optim. Appl. 65(3), 671-698(2016)
[28] Huang,Y.K.,Dai,Y.H., Liu,X.W., Zhang,H.:Gradientmethods exploiting spectral properties.Optimi. Method Softw. 35(4), 681-705(2020)
[29] Huang, Y.K., Liu, H., Zhou, S.: Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization. Data Min. Knowl. Disc. 29(6), 1665-1684(2015)
[30] Jiang, B., Dai, Y.H.: Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems. Optim. Method Softw. 28(4), 756-784(2013)
[31] Tan, C., Ma, S., Dai, Y.H., Qian, Y.: Barzilai-Borwein step size for stochastic gradient descent. In: Advances in Neural Information Processing Systems, pp. 685-693(2016)
[32] Wang, Y., Ma, S.: Projected Barzilai-Borwein method for large-scale nonnegative image restoration. Inverse Probl. Sci. En. 15(6), 559-583(2007)
[33] De Asmundis, R., Di Serafino, D., Hager, W.W., Toraldo, G., Zhang, H.: An efficient gradient method using the Yuan steplength. Comput. Optim. Appl. 59(3), 541-563(2014)
[34] Frassoldati, G., Zanni, L., Zanghirati, G.: New adaptive stepsize selections in gradient methods. J. Ind. Mang. Optim. 4(2), 299-312(2008)
[35] Sun, C., Liu, J.P.: New stepsizes for the gradient method. Optim. Lett. 14(7), 1943-1955(2020)
[36] Zhou, B., Gao, L., Dai, Y.H.: Gradient methods with adaptive step-sizes. Comput. Optim. Appl. 35(1), 69-86(2006)
[37] Dai, Y.H.: Alternate step gradient method. Optimization 52(4-5), 395-415(2003)
[38] Huang, N.: On R-linear convergence analysis for a class of gradient methods. Comput. Optim. Appl. 81(1), 161-177(2022)
[39] Friedlander, A., Martínez, J.M., Molina, B., Raydan, M.: Gradient method with retards and generalizations. SIAM J. Numer. Anal. 36(1), 275-289(1998)
[40] Huang, Y.K., Dai, Y.H., Liu, X.W., Zhang, H.: On the acceleration of the Barzilai-Borwein method. Comput. Optim. Appl. 81(3), 717-740(2022)
[41] Zou, Q., Magoulès, F.: Fast gradient methods with alignment for symmetric linear systems without using Cauchy step. J. Comput. Math. 381, 113033(2021)
[42] Dai, Y.H., Hager, W.W., Schittkowski, K., Zhang, H.: The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26(3), 604-627(2006)