• 论文 •

基于混合非单调下降条件的直接搜索方法

1. 东莞理工学院, 计算机学院, 广东东莞 523808
• 收稿日期:2014-12-14 出版日期:2015-05-15 发布日期:2015-05-13
• 基金资助:

国家自然科学基金(#11271069)和教育部人文社会科学基金(#13YJC630095)资助.

Liu Qunfeng, Zeng Jinping, Zhang Zhongzhi, Cheng Wanyou. A DIRECT SEARCH METHOD BASED ON THE MIXED NONMONOTONE DECREASE CONDITION[J]. Mathematica Numerica Sinica, 2015, 37(2): 213-224.

A DIRECT SEARCH METHOD BASED ON THE MIXED NONMONOTONE DECREASE CONDITION

Liu Qunfeng, Zeng Jinping, Zhang Zhongzhi, Cheng Wanyou

1. College of Computer Science, Dongguan University of Technology, Dongguan 523808, Guangdong, China
• Received:2014-12-14 Online:2015-05-15 Published:2015-05-13

In this paper, a new strategy for updating the grid size is proposed based on the mixed nonmonotone decrease condition. Such strategy let the grid size decrease rapidly when a strongly minimal frame is found but decrease slowly when other quasi-minimal frame is found. It is shown in this paper that such strategy can avoid the grid size decreasing too fast, and moreover, it needs weaker convergence conditions than the pure nonmonotone decrease strategy. A direct search method is then proposed based on such strategy, and its global convergence is proved. Numerical results show that the proposed method is competitive.

MR(2010)主题分类:

()
 [1] Audet C, Dennis J J E. Analysis of generalized pattern searches[J]. SIAMJournal on Optimization, 2003, 13: 889-903.[2] Audet C, Dennis J J E. Mesh adaptive direct search algorithms for constrained optimization[J]. SIAM Journal on Optimization, 2006, 17: 188-217.[3] Conn A R, Scheinberg K, Vicent L N. Introduction to derivative-free optimization. Philadelphia: SIAM-MPS, 2009.[4] Coope I D, Price C J. Frame based methods for unconstrained optimization[J]. Journal of Opti- mization Theory and Application, 2000, 107: 261-274.[5] Coope I D, Price C J. On the convergence of grid-based methods for unconstrained optimization[J]. SIAM Journal on Optimizatioin, 2001, 11: 859-869.[6] Coope I D, Price C J. Positive bases in numerical optimization[J]. Computational Optimization and Applications, 2002, 21 (2): 169-176.[7] Hooke R, Jeeves T A. Direct search solution of numerical and statistical problems[J]. Journal of the ACM, 1961, 8: 212-229.[8] Kolda T G, Lewis R M, Torczon V. Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods. SIAM Review, 2003, 45: 385-482.[9] Lewis R M, Torczon V, Trosset M W. Why pattern search works. Optima, 1998, 59: 1-7.[10] Lewis R M, Torczon V, Trosset M W. Direct search methods: Then and now[J]. Journal of Computational and Applied Mathematics, 2000, 124: 191-207.[11] Price C J, Coope I D. Frames and grids in unconstrained and linearly constrained optimization: a nonsmooth approach[J]. SIAM Journal on Optimization, 2003, 14 (2): 415-438.[12] Torczon V. On the convergence of pattern search algorithms[J]. SIAM Journal on Optimization, 1997, 7: 1-25.[13] Trosset M W. I know it when I see it: Toward a definition of direct search methods[J]. SIAG/OPT Views-and-News: A Forum for the SIAM Activity Group on Optimization, 1997, 9: 7-10.[14] Liu Q F. Linear scaling and the DIRECT algorithm[J]. Journal of Global Optimization, 2013, 56 (3): 1233-1245.[15] Liu Q F, Zeng J P. Global optimization by multilevel partition[J]. Journal of Global Optimization, 2015, 61 (1): 47-69.[16] Liu Q F, Zeng J P, Yang G. MrDIRECT: A multilevel robust DIRECT algorithm for global optimization problems. Journal of Global Optimization, DOI: 10.1007/s10898-014-0241-8, online, 2014.[17] Davidon W C. Variable metric method for minimization[J]. SIAM Journal on Optimization, 1992, 1: 1-17.[18] Rosenbrock H H. An automatic method for finding the greatest or least value of a function[J]. Computer Journal, 1960, 3: 175-184.[19] Torczon V. On the convergence of the multidirectional search algorithm[J]. SIAM Journal on Optimization, 1991, 1: 123-145.[20] Lewis R M, Torczon V. Rank ordering and positive bases in pattern search algorithms. Tech. Report 96-71, Institute for Computer Applications in Science and Engineering, NASA Langley Rearch Center, Hampson, VA, 1996.[21] Audet C. Convergence results for pattern search algorithms are tight[J]. Optimization and Engi- neering, 2004, 5(2): 101-122.[22] Coope I D, Price C J. A direct search frame-based conjugate gradients method[J]. Journal of Computational Mathematics, 2004, 22: 489-500.[23] Custódio A L, Vicente L N. Using sampling and simplex derivatives in pattern search methods[J]. SIAM Journal on Optimization, 2007, 18: 537-555.[24] Custódio A L, Dennis J E, Vicente L N. Using simplex gradients of nonsmooth functions in direct search methods[J]. IMA Journal of Numerical Analysis, 2008, 28 (4): 770-784.[25] Custódio A L, Rocha H, Vicente L N. Incorporating minimum Frobenius norm models in direct search[J]. Computational Optimization and Applications, 2010, 46: 265-278.[26] Sandia National Laboratories. APPSPACK: Asynchronous Pattern Search, 5.0.1 edition, February 2007. https://software.sandia.gov/appspack/.[27] 刘群锋. 非单调Frame型直接搜索共轭梯度法[J]. 计算数学, 2011, 3: 249-256.[28] Davis C. Theory of positive linear dependence[J]. American Journal of Mathematics, 1954, 76: 733-746.[29] Regis R G. On the properties of positive spanning sets and positive bases. Optimization and Engineering, 2015.[30] Zhang L, Zou W J, Li D H. A descent modified Polad-Ribiere-Polyak conjugate gradient method and its global convergence[J]. IMA Journal of Numerical Analysis, 2006, 26: 629-640.[31] Liu Q F. Two minimal positive bases based direct search conjugate gradient methods for compu- tationally expensive functions[J]. Numerical Algorithms, 2011, 58(4): 461-474.[32] Moré J J, Garbow B S, Hillstrom K E. Testing unconstrained optimization software[J]. ACM Transactions on Mathematical Software, 1981, 7(1): 17-41.[33] CUTEr: A constrained and unconstrained testing enviroment, Revisited. Website. http://cuter.rl.ac.uk/cuter-www/[34] Moré J J, Wild S M. Benchmarking derivative-free optimization algorithms[J]. SIAM Journal on Optimization, 2009, 20: 172-191.[35] Dolan E D, Moré J J. Benchmarking optimization software with performance profiles[J]. Mathe- matical Programming, 2002, 91: 201-213.
 [1] 尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471. [2] 冯艳昭, 张澜. 子空间约束下矩阵方程ATXB+BTXTA=D的解及最佳逼近[J]. 计算数学, 2020, 42(2): 246-256. [3] 吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236. [4] 张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50. [5] 姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386. [6] 王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62. [7] 周海林. 线性子空间上求解矩阵方程组A1XB1=C1,A2XB2=C2的迭代算法[J]. 计算数学, 2017, 39(2): 213-228. [8] 刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124. [9] 刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112. [10] 简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424. [11] 周海林. 矩阵方程AXB+CYD=E的M对称解的迭代算法[J]. 计算数学, 2015, 37(2): 186-198. [12] 袁敏, 万中. 求解非线性P0互补问题的非单调磨光算法[J]. 计算数学, 2014, 36(1): 35-50. [13] 张凯院, 牛婷婷, 聂玉峰. 一类非线性矩阵方程对称解的双迭代算法[J]. 计算数学, 2014, 36(1): 75-84. [14] 简金宝, 唐菲, 黎健玲, 唐春明. 无约束极大极小问题的广义梯度投影算法[J]. 计算数学, 2013, 35(4): 385-392. [15] 毕亚倩, 刘新为. 求解界约束优化的一种新的非单调谱投影梯度法[J]. 计算数学, 2013, 35(4): 419-430.