×

A nonmonotone line search method for noisy minimization. (English) Zbl 1327.90396

Summary: A nonmonotone line search method for optimization in noisy environment is proposed. The method is defined for arbitrary search directions and uses only the noisy function values. Convergence of the proposed method is established under a set of standard assumptions. The computational issues are considered and the presented numerical results affirm that nonmonotone strategies are worth considering. Four different line search rules with three different directions are compared numerically. The influence of nonmonotonicity is discussed.

MSC:

90C56 Derivative-free methods and methods using generalized derivatives
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andradottir, S.: A scaled stochastic approximation algorithm. Manag. Sci. 42(4), 475-498 (1996) · Zbl 0885.93058 · doi:10.1287/mnsc.42.4.475
[2] Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[3] Billups, S.C., Larson, J., Graf, P.: Derivative-free optimization of expensive functions with computational error using weighted regression. SIAM J. Optim. 23(1), 27-53 (2013) · Zbl 1295.90106 · doi:10.1137/100814688
[4] Birgin, E.G., Krejić, N., Martínez, J.M.: Globally convergent inexact quasi-Newton methods for solving nonlinear systems. Numer. Algorithms 32(2-4), 249-260 (2003) · Zbl 1034.65032 · doi:10.1023/A:1024013824524
[5] Cheng, W., Li, D.H.: A derivative-free nonmonotone line searh and its application to the spectral residual method. IMA J. Numer. Anal. 29, 814-825 (2009) · Zbl 1169.65043 · doi:10.1093/imanum/drn019
[6] Cruz, W.L., Martinez, J.M., Raydan, M.: Spectral residual method without gradient information for solving large-scale nonlinear systems of equations. Math. Comput. 75(255), 1429-1448 (2006) · Zbl 1122.65049 · doi:10.1090/S0025-5718-06-01840-0
[7] Dennis, J.E. Jr., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, Philadelphia (1996) · Zbl 0847.65038
[8] Diniz-Ehrhardt, M.A., Martínez, J.M., Raydan, M.: A derivative free nonmonotone line-search technique for unconstrained optimization. J. Comput. Appl. Math. 219(2), 383-397 (2008) · Zbl 1149.65041 · doi:10.1016/j.cam.2007.07.017
[9] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Progr. Ser. A 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[10] Fu, M.C.: Gradient estimation. In: Henderson, S.G., Nelson, B.L. (eds.) Handbook in OR & MS, vol. 13, pp. 575-616. Elsevier, North Holland (2006) · Zbl 1149.65045
[11] 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 · doi:10.1137/0723046
[12] Kelley, C.T.: Iterative Methods for Optimization. SIAM, Philadelphia (1999) · Zbl 0934.90082 · doi:10.1137/1.9781611970920
[13] Krejić, N., Krklec Jerinkić, N.: Nonmonotone line search methods with variable sample size. Numer. Algorithms (2014). doi:10.1007/s11075-014-9869-1 · Zbl 1316.65062
[14] Krejić, N., Luz̆anin, J., Stojkovska, I.: A gradient method for unconstrained optimization in noisy environment. Appl. Numer. Math. 70, 1-21 (2013) · Zbl 1283.65059 · doi:10.1016/j.apnum.2013.02.006
[15] Krejić, N., Rapajić, S.: Gllobaly convergent Jacobian smoothing inexact Newton methods for NCP. Comput. Optim. Appl. 41(2), 243-261 (2008) · Zbl 1182.90091 · doi:10.1007/s10589-007-9104-2
[16] Li, D.H., Fukushima, M.: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations. Optim. Methods Softw. 13, 181-201 (2000) · Zbl 0960.65076 · doi:10.1080/10556780008805782
[17] Lucidi, S., Sciandrone, M.: A derivative-free algorithm for bound constrained optimization. Comput. Optim. Appl. 21, 119-142 (2002) · Zbl 0988.90033 · doi:10.1023/A:1013735414984
[18] Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7(1), 17-41 (1981) · Zbl 0454.65049 · doi:10.1145/355934.355936
[19] Nikolovski, F., Stojkovska, I.: New derivative-free nonmonotone line search methods for unconstrained minimization. In: Proceedings of the Fifth International Scientific Conference—FMNS2013, Mathematics and Informatics, vol. 1, pp. 47-53. South-West University “Neofit Rilski”, Blagoevgrad, Bulgaria (2013) · Zbl 0454.65049
[20] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[21] Powell, M.J.D.: The NEWUOA software for unconstrained optimization without derivatives. In: Large Scale Nonlinear Optimization, Nonconvex Optimization and Its Applications, pp. 255-297. Springer, US (2006) · Zbl 1108.90005
[22] Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26-33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[23] Spall, J.C.: Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Wiley, Hoboken (2003) · Zbl 1088.90002 · doi:10.1002/0471722138
[24] Xu, Z., Dai, Y.-H.: New stochastic approximation algorithms with adaptive step size. Optim. Lett. 6(8), 1831-1846 (2012) · Zbl 1261.90057 · doi:10.1007/s11590-011-0380-5
[25] Yu, Z., Pu, D.: A new nonmonotone line search technique for unconstrained optimization. J. Comput. Appl. Math. 219, 134-144 (2008) · Zbl 1149.65045 · doi:10.1016/j.cam.2007.07.008
[26] Zhang, B., Zhu, Z., Li, S.: A modified spectral conjugate gradient projection algorithm for total variation image restoration. Appl. Math. Lett. 27, 26-35 (2014) · Zbl 1313.65310 · doi:10.1016/j.aml.2013.08.006
[27] Zhang, H., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14(4), 1043-1056 (2004) · Zbl 1073.90024 · doi:10.1137/S1052623403428208
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.