An efficient gradient method using the Yuan steplength. (English) Zbl 1310.90082
Summary: We propose a new gradient method for quadratic programming, named SDC, which alternates some steepest descent (SD) iterates with some gradient iterates that use a constant steplength computed through the Yuan formula. The SDC method exploits the asymptotic spectral behaviour of the Yuan steplength to foster a selective elimination of the components of the gradient along the eigenvectors of the Hessian matrix, i.e., to push the search in subspaces of smaller and smaller dimensions. The new method has global and \(R\)-linear convergence. Furthermore, numerical experiments show that it tends to outperform the Dai-Yuan method, which is one of the fastest methods among the gradient ones. In particular, SDC appears superior as the Hessian condition number and the accuracy requirement increase. Finally, if the number of consecutive SD iterates is not too small, the SDC method shows a monotonic behaviour.
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. Tokyo 11, 1-16 (1959) · Zbl 0100.14002 · doi:10.1007/BF01831719 |
| [2] | Barzilai, J., Borwein, J.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [3] | Birgin, E., Martínez, J., Raydan, M.: Spectral projected gradient methods: review and perspectives. J. Stat. Softw. (2012, to appear) · Zbl 1008.90057 |
| [4] | Bonettini, S., Landi, G., Loli Piccolomini, E., Zanni, L.: Scaling techniques for gradient projection-type methods in astronomical image deblurring. Int. J. Comput. Math. 90(1), 9-29 (2013) · Zbl 1278.68326 · doi:10.1080/00207160.2012.716513 |
| [5] | Cauchy, A.: Méthodes générales pour la résolution des systèmes d’équations simultanées. CR. Acad. Sci. Par. 25, 536-538 (1847) |
| [6] | Dai, Y.H.: Alternate step gradient method. Optimization 52(4-5), 395-415 (2003) · Zbl 1056.65055 · doi:10.1080/02331930310001611547 |
| [7] | 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 · doi:10.1007/s00211-004-0569-y |
| [8] | Dai, Y.H., Hager, 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 · doi:10.1093/imanum/drl006 |
| [9] | 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 · doi:10.1093/imanum/22.1.1 |
| [10] | Dai, Y.H., Yuan, Y.: Alternate minimization gradient method. IMA J. Numer. Anal. 23, 377-393 (2003) · Zbl 1055.65073 · doi:10.1093/imanum/23.3.377 |
| [11] | Dai, Y.H., Yuan, Y.: Analysis of monotone gradient methods. J. Ind. Manag. Optim. 1, 181-192 (2005) · Zbl 1071.65084 · doi:10.3934/jimo.2005.1.181 |
| [12] | De Angelis, P., Toraldo, G.: On the identification property of a projected gradient method. SIAM J. Numer. Anal. 30(5), 1483-1497 (1993) · Zbl 0802.65080 · doi:10.1137/0730077 |
| [13] | De Asmundis, R., di Serafino, D., Landi, G.: On the regularizing behavior of recent gradient methods in the solution of linear ill-posed problems (2014). http://www.optimization-online.org/DB_HTML/2014/06/4393.html · Zbl 1382.65114 |
| [14] | De Asmundis, R., di Serafino, D., Riccio, F., Toraldo, G.: On spectral properties of steepest descent methods. IMA J. Numer. Anal. 33, 1416-1435 (2013) · Zbl 1321.65095 · doi:10.1093/imanum/drs056 |
| [15] | van den Doel, K., Ascher, U.: The chaotic nature of faster gradient descent methods. J. Sci. Comput. 51(3), 560-581 (2012) · Zbl 1252.65073 · doi:10.1007/s10915-011-9521-3 |
| [16] | Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1, 586-598 (2007) · doi:10.1109/JSTSP.2007.910281 |
| [17] | Fletcher, R.: Low storage method for uncostrained optimization. In: Allgower, E.L., Georg, K. (eds.) Computational Solution of Nonlinear Systems of Equations. Lectures in Applied Mathematics, vol. 26, pp. 165-179. AMS Publications, Providence, RI (1990) · Zbl 1254.90113 |
| [18] | Fletcher, R.: On the Barzilai-Borwein method. In: Qi, L., Teo, K., Yang, X. (eds.) Optimization and Control with Applications. Applied Optimization Series, vol. 96, pp. 235-256. Springer, New York, NY (2005) · Zbl 1118.90318 |
| [19] | Fletcher, R.: A limited memory steepest descent method. Math. Program. Ser. A 135, 413-436 (2012) · Zbl 1254.90113 · doi:10.1007/s10107-011-0479-6 |
| [20] | Frassoldati, G., Zanni, L., Zanghirati, G.: New adaptive stepsize selections in gradient methods. J. Ind. Manag. Optim. 4(2), 299-312 (2008) · Zbl 1161.90524 · doi:10.3934/jimo.2008.4.299 |
| [21] | Friedlander, A., Martínez, J., Molina, B., Raydan, M.: Gradient method with retards and generalizations. SIAM J. Numer. Anal. 36, 275-289 (1999) · Zbl 0940.65032 · doi:10.1137/S003614299427315X |
| [22] | Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Num. Anal. 23, 707-716 (1986) · Zbl 0616.65067 · doi:10.1137/0723046 |
| [23] | Huang, H.: Efficient reconstruction of 2D images and 3D surfaces. Ph.D. Thesis, University of BC, Vancouver (2008) · Zbl 0988.90049 |
| [24] | Lamotte, J.L., Molina, B., Raydan, M.: Smooth and adaptive gradient method with retards. Math. Comput. Model. 36(9-10), 1161-1168 (2002) · Zbl 1029.65029 · doi:10.1016/S0895-7177(02)00266-2 |
| [25] | Loosli, G., Canu, S.: Quadratic programming and machine learning large scale problems and sparsity. In: Siarry, P. (ed.) Optimization in Signal and Image Processing, pp. 111-135. Wiley ISTE, Hoboken, NJ (2009) |
| [26] | Moré, J., Toraldo, G.: Algorithms for bound constrained quadratic programming problems. Numer. Math. 55, 377-400 (1989) · Zbl 0675.65061 · doi:10.1007/BF01396045 |
| [27] | Nocedal, J., Sartenaer, A., Zhu, C.: On the behavior of the gradient norm in the steepest descent method. Comput. Optim. Appl. 22, 5-35 (2002) · Zbl 1008.90057 · doi:10.1023/A:1014897230089 |
| [28] | Raydan, M.: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13, 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, 26-33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365 |
| [30] | Raydan, M., Svaiter, B.: Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21, 155-167 (2002) · Zbl 0988.90049 · doi:10.1023/A:1013708715892 |
| [31] | Yuan, Y.: A new stepsize for the steepest descent method. J. Comp. Math. 24, 149-156 (2006) · Zbl 1101.65067 |
| [32] | Yuan, Y.: 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, Y.H.: 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.
