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

Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

It is well-known that conjugate gradient algorithms are widely applied in many practical fields, for instance, engineering problems and finance models, as they are straightforward and characterized by a simple structure and low storage. However, challenging problems remain, such as the convergence of the PRP algorithms for nonconvexity under an inexact line search, obtaining a sufficient descent for all conjugate gradient methods, and other theory properties regarding global convergence and the trust region feature for nonconvex functions. This paper studies family conjugate gradient formulas based on the six classic formulas, PRP, HS, CD, FR, LS, and DY, where the family conjugate gradient algorithms have better theory properties than those of the formulas by themselves. Furthermore, this technique of the presented conjugate gradient formulas can be extended to any two-term conjugate gradient formula. This paper designs family conjugate gradient algorithms for nonconvex functions, which have the following features without other conditions: (i) the sufficient descent property holds, (ii) the trust region feature is true, and (iii) the global convergence holds under normal assumptions. Numerical results show that the given conjugate gradient algorithms are competitive with those of normal methods.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10, 147–161 (2008)

    MATH  MathSciNet  Google Scholar 

  2. Dai, Y.: Analysis of Conjugate Gradient Methods, Ph.D. Thesis, Institute of Computational Mathe- matics and Scientific/Engineering Computing, Chese Academy of Sciences (1997)

  3. Dai, Y.: Convergence properties of the BFGS algoritm. SIAM J. Optim. 13, 693–701 (2003)

    Article  MATH  Google Scholar 

  4. Dai, Y., Liao, L.: New conjugacy conditions and related nonlinear conjugate gradient methods. App. Math. Optim. 43, 87–101 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Dai, Y., Yuan, Y.: A nonlinear conjugate gradient with a strong global convergence properties. SIAM J. Optim. 10, 177–182 (2000)

    Article  MATH  Google Scholar 

  6. Dai, Y., Yuan, Y.: Nonlinear conjugate gradient methods, Shanghai Scientific and Technical Publishers (1998)

  7. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fan, J., Yuan, Y.: A new trust region algorithm with trust region radius converging to zero. In: Li, D. (ed.) Proceedings of the 5th International Conference on Optimization: Techniques and Applications (December 2001, Hongkong), pp 786–794 (2001)

  9. Fletcher, R.: Practical methods of optimization, 2nd. Wiley, New York (1987)

    MATH  Google Scholar 

  10. Fletcher, R., Reeves, C.M.: Function minimization by conjugate gradients. Comput. J. 7, 149–154 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gilbert, J.C., Nocedal, J.: Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2, 21–42 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  12. Grippo, L., Lucidi, S.: A globally convergent version of the Polak-Ribière-Polyak conjugate gradient method. Math. Program. 78, 375–391 (1997)

    MATH  Google Scholar 

  13. Hager, W., Zhang, H.: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16, 170–192 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hager, W., Zhang, H.: Algorithm 851: a conjugate gradient method with guaranteed descent. ACM Trans. Math. Soft. 32, 113–137 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hestenes, M.R., Stiefel, E.: Method of conjugate gradient for solving linear equations. J. Res. Nation. Bur. Stand. 49, 409–436 (1952)

    Article  MATH  Google Scholar 

  16. Levenberg, K.: A method for the solution of certain nonlinear problem in least squares. Quart. Appl. Math. 2, 164–168 (1944)

    Article  MathSciNet  MATH  Google Scholar 

  17. Li, D.H., Tian, B.S.: N-step quadratic convergence of the MPRP method with a restart strategy. J. Comput. Appl. Math. 235, 4978–4990 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. Li, X., Wang, S., Jin, Z., Pham, H.: A conjugate gradient algorithm under Yuan-Wei-Lu line search technique for large-scale minimization optimization models, vol. 2018 (2018)

  19. Liu, Y., Storey, C.: Effcient generalized conjugate gradient algorithms part 1: theory. J. Optim. Theo. Appl. 69, 129–137 (1991)

    Article  MATH  Google Scholar 

  20. Martinet, B.: Régularisation d’inéquations variationelles par approxiamations succcessives. Rev. Fr. Inform. Rech. Oper. 4, 154–158 (1970)

    Google Scholar 

  21. Nocedal, J., Wright, S.J.: Numerical optimization. Springer, New York (1999)

    Book  MATH  Google Scholar 

  22. Polak, E.: The conjugate gradient method in extreme problems. Comput. Math. Mathem. Phy. 9, 94–112 (1969)

    Article  Google Scholar 

  23. Polak, E., Ribière, G.: Note sur la convergence de directions conjugees. Rev. Fran. Inf. Rech. Opérat. 3, 35–43 (1969)

    MATH  Google Scholar 

  24. Powell, M.J.D.: Convergence properties of a class of minimization algorithms. In: Mangasarian, Q.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear programming, vol. 2, pp 1–27. Academic Press, New York (1974)

  25. Powell, M.J.D.: Nonconvex minimization calculations and the conjugate gradient method, Lecture Notes in Mathematics, vol. 1066, pp 122–141. Springer, Berlin (1984)

    Google Scholar 

  26. Powell, M.J.D.: Convergence properties of algorithm for nonlinear optimization. SIAM Rev. 28, 487–500 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  27. Sheng, Z., Ouyang, A., Liu, L., et al.: A novel parameter estimation method for Muskingum model using new Newton-type trust region algorithm. Math. Probl. Eng. 2014, 1–7 (2014). Art. ID 634852

    MATH  MathSciNet  Google Scholar 

  28. Sheng, Z., Yuan, G.: An effective adaptive trust region algorithm for nonsmooth minimization. Comput. Optim. Appl. 71, 251–271 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  29. Sheng, Z., Yuan, G., Cui, Z.: A new adaptive trust region algorithm for optimization problems. Acta Math. Scientia. 38B(2), 479–496 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  30. Sheng, Z., Yuan, G., Cui, Z., et al.: An adaptive trust region algorithm for large-residual nonsmooth least squares problems. J. Ind. Manage. Optim. 14, 707–718 (2018)

    MATH  MathSciNet  Google Scholar 

  31. Wei, Z., Yao, S., Liu, L.: The convergence properties of some new conjugate gradient methods. Appl. Math. Comput. 183, 1341–1350 (2006)

    MATH  MathSciNet  Google Scholar 

  32. Yuan, G.: Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems. Optim. Let. 3, 11–21 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  33. Yuan, G., Lu, X.: A modified PRP conjugate gradient method. Anna. Operat. Res. 166, 73–90 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  34. Yuan, G., Lu, S., Wei, Z.: A new trust-region method with line search for solving symmetric nonlinear equations. Intern. J. Comput. Math. 88, 2109–2123 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  35. Yuan, G., Lu, X., Wei, Z.: A conjugate gradient method with descent direction for unconstrained optimization. J. Comput. Appl. Math. 233, 519–530 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  36. Yuan, G., Lu, X., Wei, Z.: BFGS trust-region method for symmetric nonlinear equations. J. Compu. Appl. Math. 230, 44–58 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  37. Yuan, G., Meng, Z., Li, Y.: A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations. J. Optim. Theory. Appl. 168, 129–152 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  38. Yuan, G., Sheng, Z., Wang, B., et al.: The global convergence of a modified BFGS method for nonconvex functions. J. Comput. Appl. Math. 327, 274–294 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  39. Yuan, G., Wei, Z., Li, G.: A modified Polak-Ribière-Polyak conjugate gradient algorithm for nonsmooth convex programs. J. Comput. Appl. Math. 255, 86–96 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  40. Yuan, G., Wei, Z., Lu, X.: Global convergence of the BFGS method and the PRP method for general functions under a modified weak Wolfe-Powell line search. Appl. Math. Model. 47, 811–825 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  41. Yuan, G., Wei, Z., Yang, Y.: The global convergence of the Polak-Ribière-Polyak conjugate gradient algorithm under inexact line search for nonconvex functions. J. Comput. Appl. Math. 362, 262–275 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  42. Yuan, G., Zhang, M.: A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations. J. Comput. Appl. Math. 286, 186–195 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  43. Yuan, Y.: Analysis on the conjugate gradient method. Optim. Meth. Soft. 2, 19–29 (1993)

    Article  Google Scholar 

  44. Zoutendijk, G.: Nonlinear programming computational methods. In: Abadie, J. (ed.) Integer and Nonlinear Programming, Northholland, Amsterdam, pp 37–86 (1970)

Download references

Acknowledgments

The authors would like to thank the editor and the referee for their valuable comments which greatly improve this manuscript.

Funding

This work was supported by the National Natural Science Fund of China (Grant No. 11661009), the Guangxi Natural Science Fund for Distinguished Young Scholars (No. 2015GXNSFGA139001), and the Guangxi Natural Science Key Fund (No. 2017GXNSFDA198046).

Author information

Authors and Affiliations

  1. College of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, 530004, China

    Gonglin Yuan

  2. School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning, 116024, China

    Xiaoliang Wang

  3. Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu, 211106, China

    Zhou Sheng

Authors
  1. Gonglin Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaoliang Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhou Sheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhou Sheng.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yuan, G., Wang, X. & Sheng, Z. Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions. Numer Algor 84, 935–956 (2020). https://doi.org/10.1007/s11075-019-00787-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-019-00787-7

Keywords

Mathematics Subject Classification (2010)

Search

Navigation