Skip to main content
SpringerLink
Log in

On the Nonmonotone Line Search

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The technique of nonmonotone line search has received many successful applications and extensions in nonlinear optimization. This paper provides some basic analyses of the nonmonotone line search. Specifically, we analyze the nonmonotone line search methods for general nonconvex functions along different lines. The analyses are helpful in establishing the global convergence of a nonmonotone line search method under weaker conditions on the search direction. We explore also the relations between nonmonotone line search and R-linear convergence assuming that the objective function is uniformly convex. In addition, by taking the inexact Newton method as an example, we observe a numerical drawback of the original nonmonotone line search and suggest a standard Armijo line search when the nonmonotone line search condition is not satisfied by the prior trial steplength. The numerical results show the usefulness of such suggestion for the inexact Newton method.

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. GRIPPO, L., LAMPARIELLO, F., and LUCIDI, S., A Nonmonotone Line Search Technique for Newton's Method, SIAM Journal on Numerical Analysis, Vol. 23, pp. 707-716, 1986.

    Google Scholar 

  2. BONNANS, J. F., PANIER, E., TITS, A., and ZHOU, J. L., Avoiding the Maratos Effect by Means of a Nonmonotone Line Search, II: Inequality Constrained Problems-Feasible Iterates, SIAM Journal on Numerical Analysis, Vol. 29, pp. 1187-1202, 1992.

    Google Scholar 

  3. DENG, N. Y., XIAO, Y., and ZHOU, F. J., Nonmonotonic Trust-Region Algorithm, Journal of Optimization Theory and Applications, Vol. 26, pp. 259-285, 1993.

    Google Scholar 

  4. GRIPPO, L., LAMPARIELLO, F., and LUCIDI, S., A Truncated Newton Method with Nonmonotone Line Search for Unconstrained Optimization, Journal of Optimization Theory and Applications, Vol. 60, pp. 401-419, 1989.

    Google Scholar 

  5. GRIPPO, L., LAMPARIELLO, F., and LUCIDI, S., A Class of Nonmonotone Stabilization Methods in Unconstrained Optimization, Numerische Mathematik, Vol. 59, pp. 779-805, 1991.

    Google Scholar 

  6. KE, X., and HAN, J., A Nonmonotone Trust Region Algorithm for Equality Constrained Optimization, Science in China, Vol. 38A, pp. 683-695, 1995.

    Google Scholar 

  7. KE, X., LIU, G., and XU, D., A Nonmonotone Trust-Region Algorithm for Unconstrained Optimization, Chinese Science Bulletin, Vol. 41, pp. 197-201, 1996.

    Google Scholar 

  8. LUCIDI, S., ROCHETICH, F., and ROMA, M., Curvilinear Stabilization Techniques for Truncated Newton Methods in Large-Scale Unconstrained Optimization, SIAM Journal on Optimization, Vol. 8, pp. 916-939, 1998.

    Google Scholar 

  9. PANIER, E., and TITS, A., Avoiding the Maratos Effect by Means of a Nonmonotone Line Search, I: General Constrained Problems, SIAM Journal on Numerical Analysis, Vol. 28, pp. 1183-1195, 1991.

    Google Scholar 

  10. RAYDAN, M., The Barzilai and Borwein Gradient Method for the Large-Scale Unconstrained Minimization Problem, SIAM Journal on Optimization, Vol. 7, pp. 26-33, 1997.

    Google Scholar 

  11. TOINT, P. L., An Assessment of Nonmonotone Line Search Techniques for Unconstrained Optimization, SIAM Journal on Scientific Computing, Vol. 17, pp. 725-739, 1996.

    Google Scholar 

  12. TOINT, P. L., A Nonmonotone Trust-Region Algorithm for Nonlinear Optimization Subject to Convex Constraints, Mathematical Programming, Vol. 77, pp. 69-94, 1997.

    Google Scholar 

  13. ZHOU, J. L., and TITS, A., Nonmonotone Line Search for Minimax Problems, Journal of Optimization Theory and Applications, Vol. 76, pp. 455-476, 1993.

    Google Scholar 

  14. ARMIJO, L., Minimization of Functions Having Lipschitz Continuous First Partial Derivatives, Pacific Journal of Mathematics, Vol. 16, pp. 1-3, 1966.

    Google Scholar 

  15. WOLFE, P., Convergence Conditions for Ascent Methods, SIAM Review, Vol. 11, pp. 226-235, 1969.

    Google Scholar 

  16. DAI, Y. H., A Nonmonotone Conjugate Gradient Algorithm for Unconstrained Optimization, Research Report, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 2000 (accepted by Journal of Systems Science and Complexity).

  17. BARZILAI, J., and BORWEIN, J. M., Two-Point Stepsize Gradient Methods, IMA Journal of Numerical Analysis, Vol. 8, pp. 141-148, 1988.

    Google Scholar 

  18. DAI, Y. H., and LIAO, L. Z., R-Linear Convergence of the Barzilai and Borwein Gradient Method, Research Report 99-039, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1999 (accepted by IMA Journal of Numerical Analysis).

  19. Moré, J. J., GARBOW, B. S., and HILLSTROM, K. E., Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software, Vol. 7, pp. 17-41, 1981.

    Google Scholar 

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 System Sciences, Chinese Academy of Sciences, Beijing, China

    Y. H. Dai (Associate Professor)

Authors
  1. Y. H. Dai
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dai, Y.H. On the Nonmonotone Line Search. Journal of Optimization Theory and Applications 112, 315–330 (2002). https://doi.org/10.1023/A:1013653923062

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1013653923062

Search

Navigation