A non-monotone retrospective trust-region method for unconstrained optimization

Jun Chen; Wenyu Sun; Zhenghao Yang

doi:10.3934/jimo.2013.9.919

Article Contents

2013, Volume 9, Issue 4: 919-944. Doi: 10.3934/jimo.2013.9.919

This issue Previous Article Equilibrium joining probabilities in observable queues with general service and setup times Next Article Integrated imperfect production inventory model under permissible delay in payments depending on the order quantity

A non-monotone retrospective trust-region method for unconstrained optimization

1.
School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046
2.
Department of Applied Mathematics, Nanjing Agricultural University, Nanjing 210095

Received: December 31, 2011

Revised: March 31, 2013

Published: September 2013

Abstract Related Papers Cited by

Abstract

In this paper, a new non-monotone trust-region algorithm is proposed for solving unconstrained nonlinear optimization problems. We modify the retrospective ratio which is introduced by Bastin et al. [Math. Program., Ser. A (2010) 123: 395-418] to form a convex combination ratio for updating the trust-region radius. Then we combine the non-monotone technique with this new framework of trust-region algorithm. The new algorithm is shown to be globally convergent to a first-order critical point. Numerical experiments on CUTEr problems indicate that it is competitive with both the original retrospective trust-region algorithm and the classical trust-region algorithms.

Keywords:

Mathematics Subject Classification: 90C30, 90C26, 65K05.

Citation:

Related Papers

Cited by

References

[1]	F. Bastin, V. Malmedy, M. Mouffe, Ph. L. Toint and D. Tomanos, A retrospective trust-region method for unconstrained optimization, Mathematical Programming, 123 (2010), 395-418.doi: 10.1007/s10107-008-0258-1.
[2]	I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Transactions on Mathematical Software, 21 (1995), 123-160.doi: 10.1145/200979.201043.
[3]	R. M. Chamberlain, M. J. D. Powell, C. Lemaréchal and H. C. Pedersen, The watchdog technique for forcing convergence in algorithms for constrained optimization, Mathematical Programming Studies, 16 (1982), 1-17.
[4]	J. Chen, W. Y. Sun and R. J. B. de Sampaio, Numerical research on the sensitivity of nonmonotone trust region algorithms to their parameters, Computers and Mathematics with Applications, 56 (2008), 2932-2940.doi: 10.1016/j.camwa.2008.05.010.
[5]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,'' MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2000.doi: 10.1137/1.9780898719857.
[6]	N. Y. Deng, Y. Xiao and F. J. Zhou, Nonmonotonic trust region algorithm, Journal of Optimization Theory and Applications, 76 (1993), 259-285.doi: 10.1007/BF00939608.
[7]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, Series A, 91 (2002), 201-213.doi: 10.1007/s101070100263.
[8]	J. H. Fu and W. Y. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems, Applied Mathematics and Computation, 163 (2005), 489-504.doi: 10.1016/j.amc.2004.02.011.
[9]	N. I. M. Gould, D. Orban and Ph. L. Toint, CUTEr and SifDec: A Constrained and Unconstrained Testing Environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 373-394.doi: 10.1145/962437.962438.
[10]	L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for newton's method, SIAM Journal on Numerical Analysis, 23 (1986), 707-716.doi: 10.1137/0723046.
[11]	J. T. Mo, C. Y. Liu and S. C. Yan, A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values, Journal of Computational and Applied Mathematics, 209 (2007), 97-108.doi: 10.1016/j.cam.2006.10.070.
[12]	J. J. Moré, Recent developments in algorithms and software for trust region methods, in "Mathematical Programming: The State of the Art" (eds. A. Bachem, M. Grötschel and B. Korte), Springer, Berlin, (1983), 258-287.
[13]	J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 553-572.doi: 10.1137/0904038.
[14]	J. Nocedal and S. J. Wright, "Numerical Optimization,'' $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006.
[15]	M. J. D. Powell, A hybrid method for nonlinear equations, in "Numerical Methods for Nonlinear Algebraic Equations" (ed. P. Rabinowitz), Gordon and Breach, London, (1970), 87-114.
[16]	M. J. D. Powell, Convergence properties of a class of minimization algorithms, in "Nonlinear Programming, 2" (eds. O. L. Mangasarian, R. R. Meyer and S. M. Robinson), Academic Press, London, (1974), 1-27.
[17]	G. A. Shultz, R. B. Schnabel and R. H. Byrd, A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties, SIAM Journal on Numerical Analysis, 22 (1985), 47-67.doi: 10.1137/0722003.
[18]	W. Y. Sun, Nonmonotone trust region method for solving optimization problems, Applied Mathematics and Computation, 156 (2004), 159-174.doi: 10.1016/j.amc.2003.07.008.
[19]	W. Y. Sun, J. Y. Han and J. Sun, Global convergence of nonmonotone descent methods for unconstrained optimization problems, Journal of Computational and Applied Mathematics, 146 (2002), 89-98.doi: 10.1016/S0377-0427(02)00420-X.
[20]	W. Y. Sun and Y. X. Yuan, "Optimization Theory and Methods. Nonlinear Programming,'' Springer Optimization and Its Applications, Vol. 1, Springer, New York, 2006.
[21]	W. Y. Sun and Q. Y. Zhou, An unconstrained optimization method using nonmonotone second order Goldstein's line search, Science in China Series A: Mathematics, 50 (2007), 1389-1400.doi: 10.1007/s11425-007-0072-x.
[22]	Ph. L. Toint, An assessment of nonmonotone linesearch techniques for unconstrained optimization, SIAM Journal on Scientific Computing, 17 (1996), 725-739.doi: 10.1137/S106482759427021X.
[23]	Ph. L. Toint, A non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Mathematical Programming, 77 (1997), 69-94.doi: 10.1007/BF02614518.
[24]	Y. X. Yuan, On the convergence of trust region algorithms, (in Chinese) Mathematica Numerica Sinica, 16 (1994), 333-346.
[25]	Y. X. Yuan and W. Y. Sun, "Optimization Theory and Methods,'' (in Chinese) Science Press, Beijing, 1997.
[26]	H. C. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM Journal on Optimization, 14 (2004), 1043-1056.doi: 10.1137/S1052623403428208.
[27]	D. T. Zhu, A nonmonotone trust region technique for unconstrained optimization problems, Systems Science and Mathematical Sciences, 11 (1998), 375-382.