A family of spectral gradient methods for optimization. (English) Zbl 1427.90260
Summary: We propose a family of spectral gradient methods, whose stepsize is determined by a convex combination of the long Barzilai-Borwein (BB) stepsize and the short BB stepsize. Each member of the family is shown to share certain quasi-Newton property in the sense of least squares. The family also includes some other gradient methods as its special cases. We prove that the family of methods is \(R\)-superlinearly convergent for two-dimensional strictly convex quadratics. Moreover, the family is \(R\)-linearly convergent in the any-dimensional case. Numerical results of the family with different settings are presented, which demonstrate that the proposed family is promising.
Keywords:
unconstrained optimization; steepest descent method; spectral gradient method; \(R\)-linear convergence; \(R\)-superlinear convergenceReferences:
| [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 |
| [2] | Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141-148 (1988) · Zbl 0638.65055 |
| [3] | 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) · Zbl 1047.90077 |
| [4] | Birgin, E.G., Martínez, J.M., Raydan, M., et al.: Spectral projected gradient methods: review and perspectives. J. Stat. Softw. 60(3), 539-559 (2014) · Zbl 1047.65042 |
| [5] | Broyden, C.G.: A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19(92), 577-593 (1965) · Zbl 0131.13905 |
| [6] | 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) |
| [7] | Dai, Y.H.: Alternate step gradient method. Optimization 52(4-5), 395-415 (2003) · Zbl 1056.65055 |
| [8] | Dai, Y.H.: A new analysis on the Barzilai-Borwein gradient method. J. Oper. Res. Soc. China 2(1), 187-198 (2013) · Zbl 1334.90162 |
| [9] | 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. Springer (2015) · Zbl 1330.65084 |
| [10] | Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Math. Program. 103(3), 541-559 (2005) · Zbl 1099.90038 |
| [11] | Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100(1), 21-47 (2005) · Zbl 1068.65073 |
| [12] | 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) · Zbl 1147.65315 |
| [13] | Dai, Y.H., Kou, C.: A Barzilai-Borwein conjugate gradient method. Sci. China Math. 59, 1511-1524 (2016) · Zbl 1352.49031 |
| [14] | Dai, Y.H., Liao, L.Z.: \[R\] R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22(1), 1-10 (2002) · Zbl 1002.65069 |
| [15] | Dai, Y.H., Yuan, Y.X.: Alternate minimization gradient method. IMA J. Numer. Anal. 23(3), 377-393 (2003) · Zbl 1055.65073 |
| [16] | Dai, Y.H., Yuan, Y.X.: Analysis of monotone gradient methods. J. Ind. Manag. Optim. 1(2), 181 (2005) · Zbl 1071.65084 |
| [17] | 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) · Zbl 1310.90082 |
| [18] | 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 |
| [19] | Dennis Jr., J.E., Moré, J.J.: Quasi-Newton methods, motivation and theory. SIAM Rev. 19(1), 46-89 (1977) · Zbl 0356.65041 |
| [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) · Zbl 1426.65082 |
| [21] | Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213 (2002) · Zbl 1049.90004 |
| [22] | Fletcher, R.: On the Barzilai-Borwein method. In: Optimization and Control with Applications, pp. 235-256 (2005) · Zbl 1118.90318 |
| [23] | Frassoldati, G., Zanni, L., Zanghirati, G.: New adaptive stepsize selections in gradient methods. J. Ind. Manag. Optim. 4(2), 299 (2008) · Zbl 1161.90524 |
| [24] | 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) · Zbl 0940.65032 |
| [25] | Gonzaga, C.C., Schneider, R.M.: On the steepest descent algorithm for quadratic functions. Comput. Optim. Appl. 63(2), 523-542 (2016) · Zbl 1360.90183 |
| [26] | Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23(4), 707-716 (1986) · Zbl 0616.65067 |
| [27] | 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 |
| [28] | Huang, Y., Liu, H., Zhou, S.: Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization. Data Min. Knowl. Discov. 29(6), 1665-1684 (2015) · Zbl 1405.65060 |
| [29] | Jiang, B., Dai, Y.H.: Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems. Optim. Methods Softw. 28(4), 756-784 (2013) · Zbl 1302.90209 |
| [30] | Kalousek, Z.: Steepest descent method with random step lengths. Found. Comput. Math. 17(2), 359-422 (2017) · Zbl 1376.49042 |
| [31] | Liu, Y.F., Dai, Y.H., Luo, Z.Q.: Coordinated beamforming for MISO interference channel: complexity analysis and efficient algorithms. IEEE Trans. Signal Process. 59(3), 1142-1157 (2011) · Zbl 1392.94315 |
| [32] | Nocedal, J., Sartenaer, A., Zhu, C.: On the behavior of the gradient norm in the steepest descent method. Comput. Optim. Appl. 22(1), 5-35 (2002) · Zbl 1008.90057 |
| [33] | 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 |
| [34] | 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 |
| [35] | Raydan, M., Svaiter, B.F.: Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21(2), 155-167 (2002) · Zbl 0988.90049 |
| [36] | 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) |
| [37] | Wang, Y., Ma, S.: Projected Barzilai-Borwein method for large-scale nonnegative image restoration. Inverse Probl. Sci. Eng. 15(6), 559-583 (2007) · Zbl 1202.94077 |
| [38] | Wright, S.J., Nowak, R.D., Figueiredo, M.A.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57(7), 2479-2493 (2009) · Zbl 1391.94442 |
| [39] | Yuan, Y.X.: Step-sizes for the gradient method. AMS IP Stud. Adv. Math. 42(2), 785-796 (2008) · Zbl 1172.90509 |
| [40] | Zhou, B., Gao, L., Dai, Y.H.: Gradient methods with adaptive step-sizes. Comput. Optim. Appl. 35(1), 69-86 (2006) · Zbl 1121.90099 |
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.
