×

zbMATH — the first resource for mathematics

On the nonmonotone line search. (English) Zbl 1049.90087
Summary. 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.

MSC:
90C30 Nonlinear programming
65K10 Numerical optimization and variational techniques
Software:
minpack
PDF BibTeX Cite
Full Text: DOI
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. · Zbl 0616.65067
[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. · Zbl 0763.65042
[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. · Zbl 0797.90088
[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. · Zbl 0632.90059
[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. · Zbl 0724.90060
[6] KE, X., and HAN, J., A Nonmonotone Trust Region Algorithm for Equality Constrained Optimization, Science in China, Vol. 38A, pp. 683-695, 1995. · Zbl 0835.90089
[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. · Zbl 0846.90099
[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. · Zbl 0912.90259
[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. · Zbl 0732.65055
[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. · Zbl 0898.90119
[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. · Zbl 0849.90113
[12] TOINT, P. L., A Nonmonotone Trust-Region Algorithm for Nonlinear Optimization Subject to Convex Constraints, Mathematical Programming, Vol. 77, pp. 69-94, 1997. · Zbl 0891.90153
[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. · Zbl 0792.90079
[14] ARMIJO, L., Minimization of Functions Having Lipschitz Continuous First Partial Derivatives, Pacific Journal of Mathematics, Vol. 16, pp. 1-3, 1966. · Zbl 0202.46105
[15] WOLFE, P., Convergence Conditions for Ascent Methods, SIAM Review, Vol. 11, pp. 226-235, 1969. · Zbl 0177.20603
[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. · Zbl 0638.65055
[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). · Zbl 1002.65069
[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. · Zbl 0454.65049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.