Skip to main content
SpringerLink
Log in

A perfect example for the BFGS method

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function; namely, (b) we are able to construct a relatively simple polynomial example.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Byrd R.H., Nocedal J., Yuan Y.X.: Global convergence of a class of quasi-Newton methods on convex problems. SIAM J. Numer. Anal. 24, 1171–1190 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  2. Broyden, C.G.: The convergence of a class of double rank minimization algorithms: 2. The new algorithm. J. Inst. Math. Appl. 6, 222–231 (1970)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  4. Davidon W.C.: Variable metric methods for minimization. SIAM J. Optim. 1, 1–17 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  5. Dennis J.E., Moré J.J.: Quasi-Newton method, motivation and theory. SIAM Rev. 19, 46–89 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fletcher R.: A new approach to variable metric algorithms. Comput. J. 13, 317–322 (1970)

    Article  MATH  Google Scholar 

  7. Fletcher R.: An Overview of Unconstrained Optimization. In: Spedicato, E. (ed.) Algorithms for Continuous Optimization: The State of Art, pp. 109–143. Kluwer, Dordrecht (1994)

    Chapter  Google Scholar 

  8. Fletcher R., Powell M.J.D.: A rapidly convergent descent method for minimization. Comput. J. 6, 163–168 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  9. Goldfarb D.: A family of variable metric methods derived by variational means. Math. Comp. 24, 23–26 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  10. Lasserre J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Li D.H., Fukushima M.: On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM J. Optim. 11, 1054–1064 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  12. Mascarenhas W.F.: The BFGS algorithm with exact line searches fails for nonconvex functions. Math. Program. 99(1), 49–61 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  13. Nocedal J.: Theory of algorithms for unconstrained optimization. Acta Numer. 1, 199–242 (1992)

    Article  MathSciNet  Google Scholar 

  14. Powell M.J.D.: On the convergence of the variable metric algorithm. J. Inst. Math. Appl. 7, 21–36 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  15. Powell M.J.D.: Some global convergence properties of a variable metric algorithm for minimization without exact line searches. In: Cottle, R.W., Lemke, C.E. (eds.) Nonlinear Programming, SIAM-AMS Proceedings Vol. IX, pp. 53–72. SIAM, Philadelphia (1976)

    Google Scholar 

  16. Powell M.J.D.: Nonconvex minimization calculations and the conjugate gradient method. In: Griffiths, D.F. (Ed.) Numerical Analysis, Lecture Notes in Math. 1066., pp. 122–141. Springer, Berlin (1984)

    Google Scholar 

  17. Powell M.J.D.: On the convergence of the DFP algorithm for unconstrained optimization when there are only two variables. Math. Program. Ser. B 87, 281–301 (2000)

    Article  MATH  Google Scholar 

  18. Shanno D.F.: Conditioning of quasi-Newton methods for function minimization. Math. Comp. 24, 647–650 (1970)

    Article  MathSciNet  Google Scholar 

  19. Shor N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1–11 (1987)

    MathSciNet  MATH  Google Scholar 

  20. Sun W.Y., Yuan Y.X.: Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006)

    MATH  Google Scholar 

  21. Yuan, Y.X.: Numerical Methods for Nonlinear Programming. Shanghai Scientific and Technical Publishers, Shanghai (1993); (in Chinese)

Download references

Author information

Authors and Affiliations

  1. State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, P.O. Box 2719, Beijing, 100190, People’s Republic of China

    Yu-Hong Dai

Authors
  1. Yu-Hong Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yu-Hong Dai.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dai, YH. A perfect example for the BFGS method. Math. Program. 138, 501–530 (2013). https://doi.org/10.1007/s10107-012-0522-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0522-2

Keywords

Mathematics Subject Classification

Search

Navigation