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

doi:10.1007/s11464-014-0356-8

Front. Math. China

2014, Vol. 9

Issue (5) : 1211-1238 https://doi.org/10.1007/s11464-014-0356-8

RESEARCH ARTICLE

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

Lijuan ZHAO^1,²,Wenyu SUN¹,Raimundo J. B. de SAMPAIO^3,^*(

)

1. School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China
2. Department of Social Science Teaching, Nanjing Institute of Railway Technology, Nanjing 210031, China
3. PPGEPS, Pontifical Catholic University of Parana (PUCPR), Curitiba, Parana, Brazil

Download: PDF(303 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Raimundo J. B. de SAMPAIO

Issue Date: 26 August 2014

Cite this article:

Lijuan ZHAO,Wenyu SUN,Raimundo J. B. de SAMPAIO. Nonmonotone adaptive trust region method based on simple conic model for unconstrained optimization[J]. Front. Math. China, 2014, 9(5): 1211-1238.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-014-0356-8
https://academic.hep.com.cn/fmc/EN/Y2014/V9/I5/1211

1	Andrei N. Scaled conjugate gradient algorithms for unconstrained optimization. Comput Optim Appl, 2007, 38: 401-416 doi: 10.1007/s10589-007-9055-7
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 doi: 10.1007/BF01588777
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 doi: 10.1080/02331939208843768
5	Conn A R, Gould N I M, Toint Ph L. Trust-Region Methods. Philadelphia: SIAM, 2000 doi: 10.1137/1.9780898719857
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 doi: 10.1016/j.cam.2010.10.044
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 doi: 10.1023/A:1013653923062
9	Davidon W C. Conic approximations and collinear scalings for optimizers. SIAM J Numer Anal, 1980, 17: 268-281 doi: 10.1137/0717023
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 doi: 10.1080/10556789508805604
11	Di S, Sun W. A trust region method for conic model to solve unconstrained optimizations. Optim Methods Softw, 1996, 6: 237-263 doi: 10.1080/10556789608805637
12	Dolan E D, Moré J J. Benchmarking optimization software performance profiles. Math Program, 2002, 91: 201-213 doi: 10.1007/s101070100263
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 doi: 10.1007/BF02935796
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 doi: 10.1137/0723046
16	Grippo L, Sciandrone M. Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput Optim Appl, 2002, 23: 143-169 doi: 10.1023/A:1020587701058
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 doi: 10.1080/10556780410001697677
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 doi: 10.1016/j.cam.2009.09.011
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 doi: 10.1137/S1052623402418991
21	Nocedal J, Wright S J. Numerical Optimization. New York: Springer, 1999 doi: 10.1007/b98874
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 doi: 10.1016/B978-0-12-597050-1.50006-3
23	Powell M J D, Toint Ph L. On the estimation of sparse Hessian matrices. SIAM J Numer Anal, 1979, 16: 1060-1074 doi: 10.1137/0716078
24	Powell M J D, Yuan Y. A trust region algorithm for equality constrained optimization. Math Program, 1991, 49: 189-211 doi: 10.1007/BF01588787
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 doi: 10.1016/j.cam.2009.06.027
26	Schubert L K. Modification of a quasi-Newton method for nonlinear equations with sparse Jacobian. Math Comp, 1970, 24: 27-30 doi: 10.1090/S0025-5718-1970-0258276-9
27	Sorensen D C. The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization. SIAM J Numer Anal, 1980, 17: 84-114 doi: 10.1137/0717011
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 doi: 10.1016/j.amc.2003.07.008
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 doi: 10.1016/S0377-0427(02)00420-X
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 doi: 10.1137/S106482759427021X
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 doi: 10.1137/S1052623403428208
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 doi: 10.1007/s12190-012-0572-x

[1]	Yongguang HE, Huiyun LI, Xinwei LIU. Relaxed inertial proximal Peaceman-Rachford splitting method for separable convex programming[J]. Front. Math. China, 2018, 13(3): 555-578.

Viewed

Full text

Abstract

Cited

Shared

Discussed