Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Note on R-Linear Convergence of Nonmonotone Gradient Methods

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

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-\lambda _1/M_1\), where \(\lambda _1\) is the smallest eigenvalue of Hessian matrix and \(M_1\) 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/\kappa \) with \(\kappa \) being the associated condition number.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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)

    Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  3. Forsythe, G.E.: On the asymptotic directions of the \(s\)-dimensional optimum gradient method. Numer. Math. 11(1), 57–76 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dai, Y.H., Yuan, Y.X.: Alternate minimization gradient method. IMA J. Numer. Anal. 23(3), 377–393 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dai, Y.H., Yang, X.: A new gradient method with an optimal stepsize property. Comp. Optim. Appl. 33(1), 73–88 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dai, Y.H., Yuan, Y.X.: Analysis of monotone gradient methods. J. Ind. Mang. Optim. 1(2), 181 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Yuan, Y.X.: A new stepsize for the steepest descent method. J. Comput. Math. 24(2), 149–156 (2006)

    MathSciNet  MATH  Google Scholar 

  10. Yuan, Y.X.: Step-sizes for the gradient method. AMS/IP Stud. Adv. Math. 42(2), 785–796 (2008)

    MathSciNet  MATH  Google Scholar 

  11. Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141–148 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  12. Dai, Y.H.: A new analysis on the Barzilai-Borwein gradient method. J. Oper. Res. Soc. China 2(1), 187–198 (2013)

    Article  MATH  Google Scholar 

  13. Dai, Y.H., Fletcher, R.: On the asymptotic behaviour of some new gradient methods. Math. Program. 103(3), 541–559 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Raydan, M.: On the Barzilai-Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13(3), 321–326 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  23. Raydan, M.: The Barzilai-Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7(1), 26–33 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  26. Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100(1), 21–47 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  27. Huang, Y.K., Liu, H.: Smoothing projected Barzilai-Borwein method for constrained non-lipschitz optimization. Comp. Optim. Appl. 65(3), 671–698 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  28. Huang, Y.K., Dai, Y.H., Liu, X.W., Zhang, H.: Gradient methods exploiting spectral properties. Optimi. Method Softw. 35(4), 681–705 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  30. Jiang, B., Dai, Y.H.: Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems. Optim. Method Softw. 28(4), 756–784 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  34. Frassoldati, G., Zanni, L., Zanghirati, G.: New adaptive stepsize selections in gradient methods. J. Ind. Mang. Optim. 4(2), 299–312 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  35. Sun, C., Liu, J.P.: New stepsizes for the gradient method. Optim. Lett. 14(7), 1943–1955 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  36. Zhou, B., Gao, L., Dai, Y.H.: Gradient methods with adaptive step-sizes. Comput. Optim. Appl. 35(1), 69–86 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  37. Dai, Y.H.: Alternate step gradient method. Optimization 52(4–5), 395–415 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  38. Huang, N.: On \(R\)-linear convergence analysis for a class of gradient methods. Comput. Optim. Appl. 81(1), 161–177 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Hebei University of Technology, Tianjin, 300401, China

    Xin-Rui Li & Ya-Kui Huang

Authors
  1. Xin-Rui Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ya-Kui Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

X.-R. Li performed theoretical analysis and wrote the manuscript. Y.-K. Huang developed the idea and contributed to theoretical analysis and writing.

Corresponding author

Correspondence to Ya-Kui Huang.

Ethics declarations

Conflicts of interest

The authors declare that they have no conflict of interest. Not applicable, because this article does not contain any studies with human or animal subjects.

Additional information

This work was supported by the National Natural Science Foundation of China (No. 11701137) and the Natural Science Foundation of Hebei Province (No. A2021202010).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, XR., Huang, YK. A Note on R-Linear Convergence of Nonmonotone Gradient Methods. J. Oper. Res. Soc. China (2023). https://doi.org/10.1007/s40305-023-00468-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s40305-023-00468-2

Keywords

Mathematics Subject Classification

Search

Navigation