Nonmonotone adaptive trust region method based on simple conic model for unconstrained optimization

Abstract

We propose a nonmonotone adaptive trust region method based on simple conic model for unconstrained optimization. Unlike traditional trust region methods, the subproblem in our method is a simple conic model, where the Hessian of the objective function is approximated by a scalar matrix. The trust region radius is adjusted with a new self-adaptive adjustment strategy which makes use of the information of the previous iteration and current iteration. The new method needs less memory and computational efforts. The global convergence and Q-superlinear convergence of the algorithm are established under the mild conditions. Numerical results on a series of standard test problems are reported to show that the new method is effective and attractive for large scale unconstrained optimization problems.

Keywords

Nonmonotone technique / conic model / trust region method / large scale optimization / global convergence

References

[1] Andrei N. Scaled conjugate gradient algorithms for unconstrained optimization. Comput Optim Appl, 2007, 38: 401-416

[2] Andrei N. An unconstrained optimization test functions collection. Adv Model Optim, 2008, 10: 147-161

[3] Ariyawansa K A. Deriving collinear scaling algorithms as extensions of quasi-Newton methods and the local convergence of DFP and BFGS related collinear scaling algorithm. Math Program, 1990, 49: 23-48

[4] Ariyawansa K A, Lau D T M. Local and Q-superlinear convergence of a class of collinear scaling algorithms that extends quasi-Newton methods with Broyden’s bounded-ϕ class of updates. Optimization, 1992, 23: 323-339

[5] Conn A R, Gould N I M, Toint Ph L. Trust-Region Methods. Philadelphia: SIAM, 2000

[6] Cui Z C, Wu B Y, Qu S J. Combining nonmonotone conic trust region and line search techniques for unconstrained optimization. J Comput Appl Math, 2011, 235: 2432-2441

[7] Dai Y H. A nonmonotone conjugate gradient algorithm for unconstrained optimization. J Syst Sci Complex, 2002, 15: 139-145

[8] Dai Y H. On the nonmonotone line search. J Optim Theory Appl, 2002, 112: 315-330

[9] Davidon W C. Conic approximations and collinear scalings for optimizers. SIAM J Numer Anal, 1980, 17: 268-281

[10] Deng N Y, Li Z F. Some global convergence properties of a conic variable metric algorithm for minimization with inexact line search. Optim Methods Softw, 1995, 5: 105-122

[11] Di S, Sun W. A trust region method for conic model to solve unconstrained optimizations. Optim Methods Softw, 1996, 6: 237-263

[12] Dolan E D, Moré J J. Benchmarking optimization software performance profiles. Math Program, 2002, 91: 201-213

[13] Fu J H, Sun W, de Sampaio R J B. An adaptive approach of conic trust region method for unconstrained optimization problems. J Appl Math Comput, 2005, 19: 165-177

[14] Gourgeon H, Nocedal J. A conic algorithm for optimization. SIAM J Sci Stat Comput, 1985, 6: 253-267

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

[16] Grippo L, Sciandrone M. Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput Optim Appl, 2002, 23: 143-169

[17] Han Q, Sun W, Han J, Sampaio R J B. An adaptive trust-region method for unconstrained optimization. Optim Methods Softw, 2005, 20: 665-677

[18] Ji Y, Li Y J, Zhang K C, Zhang X L. A new nonmonotone trust-region method of conic model for solving unconstrained optimization. J Comput Appl Math, 2010, 233: 1746-1754

[19] Moré J J. Recent developments in algorithms and software for trust region methods. In: Bachem A, Grötschel M, Korte B, eds. Mathematical Programming: The State of the Art. Berlin: Springer, 1983, 258-287

[20] Ni Q. Optimality conditions for trust region subproblems involving a conic model. SIAM J Optim, 2005, 15: 828-837

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

[22] Powell M J D. A new algorithm for unconstrained optimization. In: Rosen J B, Mangasarian O L, Ritter K, eds. Nonlinear Programming. New York: Academic Press, 1970, 31-65

[23] Powell M J D, Toint Ph L. On the estimation of sparse Hessian matrices. SIAM J Numer Anal, 1979, 16: 1060-1074

[24] Powell M J D, Yuan Y. A trust region algorithm for equality constrained optimization. Math Program, 1991, 49: 189-211

[25] Sang Z Y, Sun Q Y. A self-adaptive trust region method with line search based on a simple subproblem model. J Comput Appl Math, 2009, 232: 514-522

[26] Schubert L K. Modification of a quasi-Newton method for nonlinear equations with sparse Jacobian. Math Comp, 1970, 24: 27-30

[27] Sorensen D C. The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization. SIAM J Numer Anal, 1980, 17: 84-114

[28] Sun Q Y, Duan L N, Cui B. A nonmonotone trust region algorithm with simple quadratic models. J Systems Sci Math Sci, 2009, 29: 470-483

[29] Sun W. Optimization methods for non-quadratic model. Asia-Pac J Oper Res, 1996, 13: 43-63

[30] Sun W. Nonmonotone trust region method for solving optimization problems. Appl Math Comput, 2004, 156: 159-174

[31] Sun W, Han J, Sun J. Global convergence of nonmonotone descent methods for unconstrained optimization problems. J Comput Appl Math, 2002, 146: 89-98

[32] Sun W, Xu D. A filter-trust-region method based on conic model for unconstrained optimization. Sci China Math, 2012, 42: 527-543 (in Chinese)

[33] Sun W, Yuan Y. Optimization Theory and Methods: Nonlinear Programming. New York: Springer, 2006

[34] Toint Ph L. Towards an efficient sparsity exploiting Newton method for minimization. In: Duff I S, ed. Sparse Matrices and Their Uses. New York: Academic Press, 1981, 57-88

[35] Toint Ph L. An assessment of non-monotone line search techniques for unconstrained optimization. SIAM J Sci Comput, 1996, 17: 725-739

[36] Xu C X, Yang X Y. Convergence of conic-quasi-Newton trust-region methods for unconstrained optimization. Math Appl (Wuhan), 1998, (2): 71-76 (in Chinese)

[37] Zhang H C, Hager W W. A nonmonotone line search technique and its application to unconstrained optimization. SIAM J Optim, 2004, 14: 1043-1056

[38] Zhou Q Y, Zhang C. A new nonmonotone adaptive trust region method based on simple quadratic models. J Appl Math Comput, 2012, 40: 111-123

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg