基于非单调技术的ODE型混合方法

摘要/Abstract

摘要： 基于非单调线搜索技术和IMPBOT算法，提出了一个求解无约束优化问题的ODE型混合方法.该方法的主要特点是：为了求得试验步，该方法在每次迭代时不必求解带信赖域界的子问题，仅需要求解一线性方程组系统；当试验步不被接受时，该方法就执行改进的Wolfe-型非单调线搜索来获得下一个新的迭代点，从而避免了反复求解线性方程组系统. 在一定条件下，所提算法还是整体收敛和超线性收敛的. 数值试验结果表明该方法是有效的.

关键词: 无约束优化, 非单调线搜索, 信赖域技术, IMPBOT算法, 收敛性

Abstract: In this paper, a new ODE-based hybrid method is proposed for solving unconstrained optimization problems, which combines the idea of IMPBOT algorithm with the nonmonotone line search technique. A main feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step. If the trial step cannot be accepted, a modified Wolfe-type nonmonotone line search is performed to generate a new iterative point, thus avoiding resolving the linear equation system. Under some assumptions, the algorithm is proven to be globally and locally convergent. Numerical results are also reported that show the efficiency of this proposed method.

Key words: unconstrained optimization, nonmonotone line search, trust region technique, IMPBOT algorithm, convergence

中图分类号:

O221.2

刘媛媛, 欧宜贵. 基于非单调技术的ODE型混合方法[J]. 运筹学学报, 2013, 17(3): 11-22.

LIU Yuanyuan, OU Yigui. An ODE-based hybrid method based on the nonmonotone technique[J]. Operations Research Transactions, 2013, 17(3): 11-22.

参考文献

Nocedal J, Wright S J. Numerical Optimization [M]. New York: Springer, 1999.
袁亚湘, 孙文瑜. 最优化理论与方法 [M]. 北京：科学出版社, 1997.
Nocedal J, Wright S J. Numerical Optimization [M]. New York: Springer, 1999.
Brown A A, Biggs M C. Some effective methods for unconstrained optimization based on the solution of system of ordinary differentiable equations [J]. Journal of Optimization Theorem and Applications, 1989, 62: 211-224.
Nocedal J, Wright S J. Numerical Optimization [M]. New York: Springer, 1999.
韩立兴. 关于无约束规划的一个ODE算法的收敛性质 [J]. 计算数学, 1993, 15: 449-455.
Higham D J. Trust region algorithms and timestep selection [J]. SIAM Journal on Numerical Analysis, 1999, 37: 194-210.
Luo X L, Kelley C T, Liao L Z, et al. Combining trust-region techniques and rosenbrock methods to compute stationary points [J]. Journal of Optimization Theorem and Applications, 2009, 140: 265-286.
Ou Y G. An ODE-based trust region filter algorithm for unconstrained optimization [J]. Numerical Functional Analysis and Optimization, 2011, 32: 524-540.
Luo X L. A second-order pseudo-transient method for steady-state problems [J]. Applied Mathematics and Computation, 2010, 216: 1752-1762.
Zhang L H, Kelley C T, Liao L Z. A continuous Newton-type method for unconstrained optimization [J]. Pacific Journal of Optimization, 2008, 4: 259-277.
Nocedal J, Yuan Y X. Combing trust region and line search techniques [M]//Advances in Nonlinear programming, [S.l.]: Kluwer, 1998, 153-175.
Ou Y G. A hybrid trust region algorithm for unconstrained optimization [J]. Applied Numerical Mathematics, 2011, 61: 900-909.
Deng N Y, Xiao Y, Zhou F J. Nonmonotone trust region algorithm [J]. Journal of Optimization Theorem and Applications, 1993, 76: 259-285.
Sun W. Y. Nonmonotone trust region method for solving optimization problems [J]. Applied Mathematics and Computation, 2004, 156: 159-174.
Grippo L, Lamparillo F, Lucidi S. A nonmonotone line search technique for Newton's method [J]. SIAM Journal on Numerical Analysis, 1986, 23: 707-716.
Sun W Y, Zhou Q Y. An unconstrained optimization method using nonmonotone second order Goldstein's line search [J]. Science in China (Series A): Mathematics, 2007, 50: 1389-1400.
Ahookhosh M, Amini K. A nonmonotone trust-region line search method for unconstrained optimization [J]. Applied Mathematical Modelling, 2012, 36: 478-487.
Shi Z J, Wang S Q. Nonmonotone adaptive trust region method [J]. European Journal of Operational Research, 2011, 208: 28-36.
Yu Z S, Pu D G. A new nonmonotone line search technique for unconstrained optimization [J]. Journal of Computational and Applied Mathematics, 2008, 219: 134-144.
Dai Y H. On the nonmonotone line search [J]. Journal of Optimization Theory and Applications, 2002, 112: 315-330.
Hu P, Liu X Q. A nonmonotone line search slackness technique for unconstrained optimization [J]. Journal of Optimization Theorem and Applications, 2012, Doi: 10.1007/s10957-012-0247-7.
Toint Ph L. An assessment of nonmonotone line search techniques for unconstrained optimization [J]. SIAM Journal on Scientic and Statistical Computing, 1996, 17: 725-739.
Zhang H C, Hager W W. A nonmonotone line search technique and its application to unconstrained optimization [J]. SIAM Journal on Optimization, 2004, 14: 1043-1056.
Hu S L, Huang Z H, Lu N. A nonmonotone line search algorithm for unconstrained optimization [J]. Journal of Scientific Computing, 2010, 42: 38-53.
Cui Z C, Wu B Y. A new modified nonmonotone adaptive trust region method for unconstrained optimization [J]. Computational Optimization and Applications, 2012, 53: 795-806.
Gu N Z, Mo J T. Incorporating nonmonotone strategies into the trust region method for unconstrained optimization [J]. Computers and Mathematics with Applications, 2008, 55: 2158-2172.
Liu J H, Ma C F. A nonmonotone trust region method with new inexact line search for unconstrained optimization [J]. Numerical Algorithms, 2012, Doi: 10.1007/s11075-012-9652-0.
More J, Garbow B, Hillstrom K. Testing unconstrained optimization software [J]. ACM Transactions on Mathematical Software, 1981, 7: 17-41.
Dolan E D, More J. Benchmarking optimization software with performance profiles [J]. Mathematical Programming (Serial A), 2002, 91: 201-213.

[1]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[2]	田明雨, 杨永建. 求解多项式规划的一个全局最优化算法[J]. 运筹学学报, 2018, 22(4): 79-88.
[3]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[4]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[5]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[6]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[7]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[8]	霍永亮. 极大极小随机规划逼近问题最优解集和最优值的稳定性[J]. 运筹学学报, 2016, 20(1): 75-83.
[9]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[10]	濮定国, 尚有林, 王关琳. 无罚函数和滤子的一个新的QP-free方法[J]. 运筹学学报, 2015, 19(3): 48-56.
[11]	陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.
[12]	党亚峥, 薛中会. 凸可行问题的平行近似次梯度投影算法[J]. 运筹学学报, 2015, 19(1): 117-124.
[13]	程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.
[14]	戴彧虹，刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1): 69-92.
[15]	濮定国，刘爱兰，尚有林，冯爱芬，孙振洋. 无罚函数和滤子的QP-free非可行域方法[J]. 运筹学学报, 2013, 17(1): 106-116.