Previous Articles    

TWO NOVEL GRADIENT METHODS WITH OPTIMAL STEP SIZES

Harry Oviedo, Oscar Dalmau, Rafael Herrera   

  1. Centro de Investigación en Matemáticas, CIMAT A. C. Guanajuato, Gto. Mexico
  • Received:2018-09-29 Revised:2019-02-18 Published:2021-04-12
  • Contact: Oscar Dalmau,Email:dalmau@cimat.mx
  • Supported by:
    This work was supported in part by CONACYT (Mexico), Grants 258033 and 256126.

Harry Oviedo, Oscar Dalmau, Rafael Herrera. TWO NOVEL GRADIENT METHODS WITH OPTIMAL STEP SIZES[J]. Journal of Computational Mathematics, 2021, 39(3): 375-391.

In this work we introduce two new Barzilai and Borwein-like steps sizes for the classical gradient method for strictly convex quadratic optimization problems. The proposed step sizes employ second-order information in order to obtain faster gradient-type methods. Both step sizes are derived from two unconstrained optimization models that involve approximate information of the Hessian of the objective function. A convergence analysis of the proposed algorithm is provided. Some numerical experiments are performed in order to compare the efficiency and effectiveness of the proposed methods with similar methods in the literature. Experimentally, it is observed that our proposals accelerate the gradient method at nearly no extra computational cost, which makes our proposal a good alternative to solve large-scale problems.

CLC Number: 

[1] Cauchy Augustin, Méthode générale pour la résolution des systemes déquations simultanées, Comp. Rend. Sci. Paris, 25(1847), 536-538.
[2] D. Iudin and A. Nemirovskii, Informational complexity and efficient methods for solving complex extremal problems, Matekon, 13(1983), 25-45.
[3] Y. Nesterov, One class of methods of unconditional minimization of a convex function having a high rate of convergence, USSR Computational Mathematics and Mathematical Physics, 24(1984), 80-82.
[4] J. Barzilai and J. Borwein, Two-point step size gradient methods, IMA journal of numerical analysis, 8(1988), 141-148.
[5] M. Raydan, On the Barzilai and Borwein choice of steplength for the gradient method, IMA Journal of Numerical Analysis, 13(1993), 321-326.
[6] Y. Dai, and L. Liao, R-linear convergence of the Barzilai and Borwein gradient method, IMA Journal of Numerical Analysis, 22(2002), 1-10.
[7] M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7(1997), 26-33.
[8] B. Molina and M. Raydan, Preconditioned Barzilai-Borwein method for the numerical solution of partial differential equations, Numerical Algorithms, 13(1996), 45-60.
[9] Y. Dai and R. Fletcher, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numerische Mathematik, 100(2005), 21-47.
[10] Y. Dai and Y. Yuan, Alternate minimization gradient method, IMA Journal of Numerical Analysis, 23(2003), 377-393.
[11] Y. Dai, Alternate step gradient method, Optimization, 52(2003), 395-415.
[12] Z. Liu, H. Liu and X. Dong, An efficient gradient method with approximate optimal stepsize for the strictly convex quadratic minimization problem, Optimization, 67(2018), 427-440.
[13] R. De Asmundis, D. Di Serafino, W. Hager, G. Toraldo, and H. Zhang, An efficient gradient method using the Yuan steplength, Computational Optimization and Applications, 59(2014), 541-563.
[14] A. Friedlander, J. Martínez, B. Molina and M. Raydan, Gradient method with retards and generalizations, SIAM Journal on Numerical Analysis, 36(1998), 275-289.
[15] D. Luenberger and Y. Ye, Linear and nonlinear programming, Springer, 1984.
[16] Y. Yuan, A new stepsize for the steepest descent method, Journal of Computational Mathematics, 24(2006), 149-156.
[17] B. Zhou, L. Gao and Y. Dai, Gradient methods with adaptive step-sizes, Computational Optimization and Applications, 35(2006), 69-86.
[18] G. Frassoldati, L. Zanni and G. Zanghirati, New adaptive stepsize selections in gradient methods, Journal of industrial and management optimization, 4(2008), 299-312.
[19] M. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of research of the National Bureau of Standards, 49(1952), 409-436.
[20] D. Di Serafino, V. Ruggiero, G. Toraldo and L. Zanni, On the steplength selection in gradient methods for unconstrained optimization, Applied Mathematics and Computation, 318(2018), 176-195.
[1] El-Sayed M.E. Mostafa. A CONJUGATE GRADIENT METHOD FOR DISCRETE-TIME OUTPUT FEEDBACK CONTROL DESIGN [J]. Journal of Computational Mathematics, 2012, 30(3): 279-297.
[2] N.H.Sweilam,L.F.Abd-Elal. A COMPUTATIONAL APPROACH FOR OPTIMAL CONTROL SYSTEMS GOVERNED BY PARABOLIC VARIATIONAL INEQUALITIES$^*$ [J]. Journal of Computational Mathematics, 2003, 21(6): 815-824.
[3] Yu Hong DAI,Qin NI. TESTING DIFFERENT CONJUGATE GRADIENT METHODS FOR LARGE-SCALE UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2003, 21(3): 311-320.
Viewed
Full text


Abstract