Abstract
Nonmonotone line search approach is a new technique for solving optimization problems. It relaxes the line search range and finds a larger step-size at each iteration, so as to possibly avoid local minimizer and run away from narrow curved valley. It is helpful to find the global minimizer of optimization problems. In this paper we develop a new modification of matrix-free nonmonotone Armijo line search and analyze the global convergence and convergence rate of the resulting method. We also address several approaches to estimate the Lipschitz constant of the gradient of objective functions that would be used in line search algorithms. Numerical results show that this new modification of Armijo line search is efficient for solving large scale unconstrained optimization problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Armijo, L.: Minimization of functions having Lipschitz continuous first partial derivatives. Pac. J. Math. 16, 1–3 (1966)
Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)
Cohen, A.I.: Stepsize analysis for descent methods. J. Optim. Theory Appl. 33(2), 187–205 (1981)
Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002)
Dai, Y.H.: On the nonmonotone line search. J. Optim. Theory Appl. 112(2), 315–330 (2002)
Deng, N., Xiao, Y., Zhou, F.: Nonmonotone trust region algorithms. J. Optim. Theory Appl. 76, 259–285 (1993)
Dennis J.E. Jr., Schnable, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs (1983)
Dolan, E., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Gould, N.I.M., Orban, D., Toint, Ph.L.: GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Softw. 29, 353–372 (2003)
Bongartz, I., Conn, A.R., Gould, N., Toint, Ph.L.: CUTE: constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 123–160 (1995)
Grippo, L., Lampariello, F., Lucidi, S.: A class of nonmonotone stability methods in unconstrained optimization. Numer. Math. 62, 779–805 (1991)
Grippo, L., Lampariello, F., Lucidi, S.: A truncated Newton method with nonmonotone line search for unconstrained optimization. J. Optim. Theory Appl. 60, 401–419 (1989)
Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)
Goldstein, A.A.: On steepest descent. SIAM J. Control 3, 147–151 (1965)
Ke, X., Han, J.: A nonmonotone trust region algorithm for equality constrained optimization. Sci. China 38A, 683–695 (1995)
Ke, X., Liu, G., Xu, D.: A nonmonotone trust region algorithm for unconstrained optimization. Chin. Sci. Bull. 41, 197–201 (1996)
Liu, G., Han, J., Sun, D.: Global convergence of BFGS algorithm with nonmonotone line search. Optimization 34, 147–159 (1995)
Moré, J.J., Garbow, B.S., Hillstron, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981)
Nocedal, J., Wright, J.S.: Numerical Optimization. Springer, New York (1999)
Nocedal, J.: Theory of algorithms for unconstrained optimization. Acta Numer. 1, 199–242 (1992)
Powell, M.J.D.: Direct search algorithms for optimization calculations. Acta Numer. 7, 287–336 (1998)
Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer, New York (1997)
Panier, E., Tits, A.: Avoiding the Maratos effect by means of a nonmonotone line search, I: general constrained problems. SIAM J. Numer. Anal. 28, 1183–1195 (1991)
Raydan, M., Svaiter, B.E.: Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21, 155–167 (2002)
Raydan, M.: The Barzilai and Borwein method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)
Raydan, M.: On the Barzilai Borwein gradient choice of steplength for the gradient method. IMA J. Numer. Anal. 13, 321–326 (1993)
Sun, W.Y., Han, J.Y., Sun, J.: Global convergence of nonmonotone descent methods for unconstrained optimization problems. J. Comput. Appl. Math. 146, 89–98 (2002)
Shi, Z.J., Shen, J.: Convergence of nonmonotone line search method. J. Comput. Appl. Math. 193, 397–412 (2006)
Shi, Z.J., Shen, J.: New inexact line search method for unconstrained optimization. J. Optim. Theory Appl. 127, 425–446 (2005)
Shi, Z.J., Shen, J.: Convergence of descent method without line search. Appl. Math. Comput. 167, 94–107 (2005)
Shi, Z.J.: Convergence of line search methods for unconstrained optimiztaion. Appl. Math. Comput. 157, 393–405 (2004)
Toint, P.L.: An assessment of nonmonotone line search techniques for unconstrained optimization. SIAM J. Sci. Comput. 17, 725–739 (1996)
Toint, P.L.: A nonmonotone trust-region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77, 69–94 (1997)
Todd, M.J.: On convergence properties of algorithms for unconstrained minimization. IMA J. Numer. Anal. 9, 435–441 (1989)
Vrahatis, M.N., Androulakis, G.S., Lambrinos, J.N., Magoulas, G.D.: A class of gradient unconstrained minimization algorithms with adaptive stepsize. J. Comput. Appl. Math. 114, 367–386 (2000)
Vrahatis, M.N., Androulakis, G.S., Manoussakis, G.E.: A new unconstrained optimization method for imprecise function and gradient values. J. Math. Anal. Appl. 197, 586–607 (1996)
Wei, Z., Qi, L., Jiang, H.: Some convergence properties of descent methods. J. Optim. Theory Appl. 95(1), 177–188 (1997)
Wolfe, P.: Convergence condition for ascent methods II: some corrections. SIAM Rev. 13, 185–188 (1971)
Wolfe, P.: Convergence condition for ascent methods. SIAM Rev. 11, 226–235 (1969)
Xiao, Y., Zhou, F.J.: Nonmonotone trust region methods with curvilinear path in unconstrained minimization. Computing 48, 303–317 (1992)
Zhang, J.L., Zhang, X.S.: A nonmonotone adaptive trust region method and its convergence. Comput. Math. Appl. 45, 1469–1477 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work was supported in part by Rackham Faculty Research Grant of University of Michigan, USA.
Rights and permissions
About this article
Cite this article
Shi, Z., Wang, S. Modified nonmonotone Armijo line search for descent method. Numer Algor 57, 1–25 (2011). https://doi.org/10.1007/s11075-010-9408-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-010-9408-7