×

zbMATH — the first resource for mathematics

A non-monotone line search algorithm for unconstrained optimization. (English) Zbl 1203.90146
Summary: The monotone line search schemes have been extensively used in the iterative methods for solving various optimization problems. It is well known that the non-monotone line search technique can improve the likelihood of finding a global optimal solution and the numerical performance of the methods, especially for some difficult nonlinear problems. The traditional non-monotone line search approach requires that a maximum of recent function values decreases. In this paper, we propose a new line search scheme which requires that a convex combination of recent function values decreases. We apply the new line search technique to solve unconstrained optimization problems, and show the proposed algorithm possesses global convergence and \(R\)-linear convergence under suitable assumptions. We also report the numerical results of the proposed algorithm for solving almost all the unconstrained testing problems given in CUTEr, and give numerical comparisons of the proposed algorithm with two famous non-monotone methods.

MSC:
90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization
Software:
SifDec; SCALCG; L-BFGS; CUTEr
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrei, N.: Scaled conjugate gradient algorithms for unconstrained optimization. Comput. Optim. Appl. 38, 401–416 (2007) · Zbl 1168.90608
[2] Dai, Y.H.: On the nonmonotone line search. J. Optim. Theory Appl. 112, 315–330 (2002) · Zbl 1049.90087
[3] Dai, Y.H.: A nonmonotone conjugate gradient algorithm for unconstrained optimization. J. Syst. Sci. Complex. 15, 139–145 (2002) · Zbl 1019.90039
[4] Dolan, E.D., MorĂ©, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004
[5] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEr and SifDec: A constrained and unconstrained environment, revisited. ACM Trans. Math. Softw. 29, 373–394 (2003) · Zbl 1068.90526
[6] Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM. J. Numer. Anal. 23, 707–716 (1986) · Zbl 0616.65067
[7] 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) · Zbl 0632.90059
[8] Grippo, L., Lampariello, F., Lucidi, S.: A class of nonmonotone stabilization method in unconstrained optimization. Numer. Math. 59, 779–805 (1991) · Zbl 0739.90062
[9] Huang, Z.H., Sun, J.: A smoothing Newton algorithm for mathematical programs with complementarity constraints. J. Ind. Manag. Optim. 1, 153–170 (2005) · Zbl 1177.90374
[10] Huang, Z.H., Zhang, Y., Wu, W.: A smoothing-type algorithm for solving system of inequalities. J. Comput. Appl. Math. 220, 355–363 (2008) · Zbl 1148.65039
[11] Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503–528 (1989) · Zbl 0696.90048
[12] Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35, 773–782 (1980) · Zbl 0464.65037
[13] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (1999) · Zbl 0930.65067
[14] Panier, E.R., Tits, A.L.: Avoiding the Maratas effect by means of a nonmonotone line search. SIAM. J. Numer. Anal. 28, 1183–1195 (1991) · Zbl 0732.65055
[15] Pytlak, R., Tarnawski, T.: On the method of shortest residuals for unconstrained optimization. J. Optim. Theory. Appl. 133, 99–110 (2007) · Zbl 1145.90105
[16] Yuan, Y.X., Sun, W.Y.: Optimization Theories and Methods. Science Press, Beijing (1997)
[17] Zhang, H.C., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043–1056 (2004) · Zbl 1073.90024
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.