Adaptive nonmonotone line search method for unconstrained optimization

Abstract

In this paper, an adaptive nonmonotone line search method for unconstrained minimization problems is proposed. At every iteration, the new algorithm selects only one of the two directions: a Newton-type direction and a negative curvature direction, to perform the line search. The nonmonotone technique is included in the backtracking line search when the Newton-type direction is the search direction. Furthermore, if the negative curvature direction is the search direction, we increase the steplength under certain conditions. The global convergence to a stationary point with second-order optimality conditions is established. Some numerical results which show the efficiency of the new algorithm are reported.

Keywords

Nonmonotone method / Newton-type direction / direction of negative curvature / adaptive line search / unconstrained optimization

References

[1] Bunch J. R., Parlett B. N. Direct methods for solving symmetric indefinite systems of linear equations. SIAM J Nume Anal, 1971, 8: 639-655.

[2] Deng N. Y., Xiao Y., Zhou F. Y. A nonmonotonic trust region algorithm. Journal of Optimization Theory and Applications, 1993, 76: 259-285.

[3] Ferris M. C., Lucidi S., Roma M. Nonmonotone curvilinear line search methods for unconstrained optimization. Computational Optimization and Applications, 1996, 6: 117-136.

[4] Fu J., Sun W. Nonmonotone adaptive trust-region method for unconstrained optimization problems. Applied Mathematics and Computation, 2005, 163: 489-504.

[5] Grippo L., Lamparillo F., Lucidi S. A nonmonotone line search technique for Newton’s method. SIAM J Numer Anal, 1986, 23: 707-716.

[6] Gould N. I. M., Lucidi S., Roma M. Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optimization Methods and Software, 2000, 14: 75-98.

[7] Lucidi S., Rochetich F., Roma M. Curvilinear stabilization techniques for truncate Newton methods in large scale unconstrained optimization. SIAM J Optimization, 1998, 3: 916-939.

[8] Lampariello F., Sciandrone M. Use of the minimum-norm search direction in a nonmonotone version of the Gauss-Newton method. Journal of Optimization Theory and Applications, 2003, 119: 65-82.

[9] McCormick G. P. A modification of Armijo’s step-size rule for negative curvature. Mathematical Programming, 1977, 13: 111-115.

[10] Moré J. J., Garbow B. S., Hillstrom K. E. Testing unconstrained optimization software. ACM Trans Math Software, 1981, 7: 17-41.

[11] Moré J. J., Sorensen D. C. On the use of directions of negative curvature in a modified Newton method. Mathematical Programming, 1979, 16: 1-20.

[12] Nocedal J., Wright S. J. Numerical Optimization, 1999, New York: Springer.

[13] Sun W. Nonmonotone optimization methods: motivation and development. In: International Conference on Numerical Linear Algebra and Optimization, Guilin, China, October 7–10, 2003 (Invited talk)

[14] Sun W. Nonmonotone trust-region method for solving optimization problems. Applied Mathematics and Computation, 2004, 156: 159-174.

[15] Sun W., Han J., Sun J. On global convergence of nonmonotone decent method. J Comput Appl Math, 2002, 146: 89-98.

[16] Yuan Y., Sun W. Optimization Theory and Methods, 1997, Beijing: Science Press.

[17] Zhou H., Sun W. Nonmonotone descent algorithm for nonsmooth unconstrained optimization problems. International Journal of Pure and Applied Mathematics, 2003, 9: 153-163.

[18] Zhou Q., Sun W. A nonmonotone second order steplength method for unconstrained optimization. Journal of Computational Mathematics, 2007, 23: 104-112.