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.

References

1. Bunch J R Parlett B N Direct methods for solvingsymmetric indefinite systems of linear equationsSIAM J Nume Anal 1971 8639655. doi:10.1137/0708060
2. Deng N Y Xiao Y Zhou F Y A nonmonotonic trust region algorithmJournal of Optimization Theory and Applications 1993 76259285. doi:10.1007/BF00939608
3. Ferris M C Lucidi S Roma M Nonmonotone curvilinear line search methods for unconstrainedoptimizationComputational Optimizationand Applications 1996 6117136
4. Fu J Sun W Nonmonotone adaptive trust-regionmethod for unconstrained optimization problemsApplied Mathematics and Computation 2005 163489504. doi:10.1016/j.amc.2004.02.011
5. Grippo L Lamparillo F Lucidi S A nonmonotone line search technique for New-ton's methodSIAM J Numer Anal 1986 23707716. doi:10.1137/0723046
6. Gould N I M Lucidi S Roma M et al.Exploiting negative curvature directions in linesearchmethods for unconstrained optimizationOptimizationMethods and Software 2000 147598. doi:10.1080/10556780008805794
7. Lucidi S Rochetich F Roma M Curvilinear stabilization techniques for truncate Newtonmethods in large scale unconstrained optimizationSIAM J Optimization 1998 3916939. doi:10.1137/S1052623495295250
8. Lampariello F Sciandrone M Use of the minimum-norm searchdirection in a non-monotone version of the Gauss-Newton methodJournal of Optimization Theory and Applications 2003 1196582. doi:10.1023/B:JOTA.0000005041.99777.af
9. McCormick G P Amodification of Armijo's step-size rule for negative curvatureMathematical Programming 1977 13111115. doi:10.1007/BF01584328
10. Moré J J Garbow B S Hillstrom K E Testing unconstrained optimization softwareACM Trans Math Software 1981 71741. doi:10.1145/355934.355936
11. Moré J J Sorensen D C On the use of directions ofnegative curvature in a modified Newton methodMathematical Programming 1979 16120. doi:10.1007/BF01582091
12. Nocedal J Wright S J Numerical OptimizationNew YorkSpringer 1999
13. Sun W Nonmonotoneoptimization methods: motivation and developmentIn: International Conference on Numerical Linear Algebra and Optimization,Guilin, China October 7–10, 2003 (Invited talk)
14. Sun W Nonmonotonetrust-region method for solving optimization problemsApplied Mathematics and Computation 2004 156159174. doi:10.1016/j.amc.2003.07.008
15. Sun W Han J Sun J On global convergence of nonmonotone decent methodJ Comput Appl Math 2002 1468998. doi:10.1016/S0377‐0427(02)00420‐X
16. Yuan Y Sun W Optimization Theory and MethodsBeijingSciencePress 1997
17. Zhou H Sun W Nonmonotone descent algorithmfor nonsmooth unconstrained optimization problemsInternational Journal of Pure and Applied Mathematics 2003 9153163
18. Zhou Q Sun W A nonmonotone second ordersteplength method for unconstrained optimizationJournal of Computational Mathematics 2007 23104112
19. Zhang J Xu C A class of indefinite doglegpath methods for unconstrained minimizationSIAM J Optimization 1999 3646667. doi:10.1137/S105262349627523X
20. Zhang J L Zhang X S A nonmonotone adaptive trustregion method and its convergenceComputersand Mathematics with Applications 2003 4514691477. doi:10.1016/S0898‐1221(03)00130‐5