• 论文 • 上一篇    

无约束最优化的信赖域BB法

刘亚君1, 刘新为2   

  1. 1. 南开大学数学科学学院, 天津 300071;
    2. 河北工业大学理学院, 天津 300401
  • 收稿日期:2015-05-13 出版日期:2016-02-15 发布日期:2016-01-22
  • 基金资助:

    国家自然科学基金(10971047,11271107)和河北省自然科学基金(A2015202365)资助项目

刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.

Liu Yajun, Liu Xinwei. TRUST REGION BB METHODS FOR UNCONSTRAINED MINIMIZATION[J]. Mathematica Numerica Sinica, 2016, 38(1): 96-112.

TRUST REGION BB METHODS FOR UNCONSTRAINED MINIMIZATION

Liu Yajun1, Liu Xinwei2   

  1. 1. School of Mathematical Sciences, Nankai University, Tianjin 300071, China;
    2. School of Science, Hebei University of Technology, Tianjin 300401, China
  • Received:2015-05-13 Online:2016-02-15 Published:2016-01-22
梯度法是求解无约束最优化的一类重要方法.步长选取的好坏与梯度法的数值表现息息相关.注意到BB步长隐含了目标函数的二阶信息,本文将BB法与信赖域方法相结合,利用BB步长的倒数去近似目标函数的Hesse矩阵,同时利用信赖域子问题更加灵活地选取梯度法的步长,给出求解无约束最优化问题的单调和非单调信赖域BB法.在适当的假设条件下,证明了算法的全局收敛性.数值试验表明,与已有的求解无约束优化问题的BB类型的方法相比,非单调信赖域BB法中ek=‖xk-x*‖的下降呈现更明显的阶梯状和单调性,因此收敛速度更快.
It is well known that the numerical performances of the gradient methods are closely dependent on how to select the step-lengths in iterations. Notice that the BB step-length implies some second-order information of the objective function, by using the BB step in the trust region method, we propose a monotone trust region BB method and its nonmonotone version for unconstrained optimization problems. Our methods use the inverse of the BB step-lengths to approximate the Hesse matrix of objective function and select step-lengths of the gradient method by the trust region subproblems flexibly. Under suitable conditions, the new methods are proved to be globally convergent. Numerical tests show that the measure of error ek=‖xk-x*‖ obtained by the nonmonotone trust region BB method can decrease faster in comparison with some existing BB methods.

MR(2010)主题分类: 

()
[1] Barzilai J, Borwein J. Two-point step size gradient methods[J]. IMA J Numer Anal, 1988, 8: 141-148.

[2] Raydan M, Svziter B F. Relaxed steepest descent and Cauchy-Barzilai-Borwein method[J]. Com-put Optim Appl, 2002, 21:155-167.

[3] Dai Y H, Liao L Z. R-linear convergence of the Barzilai and Borwein gradient method[J]. IMA J Numer Anal, 2002, 22(1):1-10.

[4] Raydan M. On The Barzilai and Borwein choice of steplength for the gradient method[J]. IMA J Numer Anal, 1993, 13:321-326.

[5] Dai Y H, Yuan J Y, Yuan Y Y. Modified two-point stepsize gradient methods for unconstrained optimization[J]. Comput Optim and Appl, 2002, 22:103-109.

[6] Dai Y H, Alternate step gradient Method[J]. Optim, 2003, 52(4-5),395-415.

[7] Dai Y H,Yuan Y X, Alternate minimization gradient method[J]. IMA J Numer Anal, 2003, 23:377-393.

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

[9] Dai Y H, Roger F. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming[J]. Numer Math, 2005, 100(1):21-47.

[10] Friedlander A, Martinez J, Molina B, Raydan M. Gradient method with retards and generaliza-tions[J]. SIAM J Numer Anal, 1999, 36:275-289.

[11] Lamotte J L, Molina B, Raydan M. Smooth and adaptive gradient method with retards[J]. Math Comput Model, 2006, 36(9-10):1161-1168.

[12] Dai Y H, Yuan Y. Analyses of monotone gradient methods[J]. Ind Manag Optim, 2005, 1:181-192.

[13] Yuan Y. A new stepsize for the steepest descent method[J]. Comp Math, 2006, 24:149-156.

[14] Yuan Y. Step-sizes for the gradient method[G]. in:K S Liu, Z P Xin and S T Yau, eds, Third International Congress of Chinese Mathematicians(AMS/IP Studies in Advanced Mathematics), 42(2):785-796.

[15] Fletcher R. A limited memory steepest descent method[J]. Math Program, 2012, 135:413-436.

[16] Roberta D A, Daniela d S, Filippo R, Gerardo T. On spectral properties of steepest descent methods[J]. IMA J Numer Anal, 2013, 33:1416-1435.

[17] 袁亚湘. 信赖域方法的收敛性[J]. 计算数学, 1994, 08(3):333-346.

[18] 孙文瑜, 徐贤成, 朱德通. 最优化方法[M]. 北京:高等教育出版社, 2011.

[19] Yuan Y. On the truncated conjugate gradient method[J]. Math Program, 2000, 87:561-571.

[20] 李正锋, 邓乃扬. 一类新的非单调信赖域算法及其收敛性[J]. 应用数学学报, 1999, 22(3):457-465.

[21] Chen J, Sun W Y. Nonmonotone Adaptivee Trust Region Algorithms with Indefinite Dogleg Path for Unconstrained Minimization[J]. Northeast Math, 2008, 24(1):19-30.

[22] Bastin F, Malmedy V, Mouffe M, Toint Ph L, et al. A Retrospective Trust-Region Method for Unconstrained Optimization[J]. Math Program, 2010, 123(2):395-418.

[23] Cartis C, Gould N I M, Toint Ph L. Adaptive cubic overestimation methods for unconstrained optimization[J]. Math Program, 2011, 130(2):295-319.

[24] 戴彧虹, 刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1):69-92.

[25] Raydan M. Convergence properties of the Barzilai and Borwein gradient method[D]. USA:Rice University, 1991.

[26] Roberta D A, Daniela d S, Gerardo T. An efficient gradient method using the Yuan steplength[J]. Comput Optim Appl, 2014, 59:541-563.
[1] 尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[2] 张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[3] 王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.
[4] 刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[5] 简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424.
[6] 袁敏, 万中. 求解非线性P0互补问题的非单调磨光算法[J]. 计算数学, 2014, 36(1): 35-50.
[7] 简金宝, 唐菲, 黎健玲, 唐春明. 无约束极大极小问题的广义梯度投影算法[J]. 计算数学, 2013, 35(4): 385-392.
[8] 刘金魁. 两种有效的非线性共轭梯度算法[J]. 计算数学, 2013, 35(3): 286-296.
[9] 范斌, 马昌凤, 谢亚君. 求解非线性互补问题的一类光滑Broyden-like方法[J]. 计算数学, 2013, 35(2): 181-194.
[10] 简金宝, 马鹏飞, 徐庆娟. 不等式约束优化一个基于滤子思想的广义梯度投影算法[J]. 计算数学, 2013, 35(2): 205-214.
[11] 刘景辉, 马昌凤, 陈争. 解无约束优化问题的一个新的带线搜索的信赖域算法[J]. 计算数学, 2012, 34(3): 275-284.
[12] 王开荣, 刘奔. 建立在修正BFGS公式基础上的新的共轭梯度法[J]. 计算数学, 2012, 34(1): 81-92.
[13] 江羡珍, 韩麟, 简金宝. Wolfe线搜索下一个全局收敛的混合共轭梯度法[J]. 计算数学, 2012, 34(1): 103-112.
[14] 万中, 冯冬冬. 一类非单调保守BFGS算法研究[J]. 计算数学, 2011, 33(4): 387-396.
[15] 庞善民, 陈兰平. 一类带非单调线搜索的信赖域算法[J]. 计算数学, 2011, 33(1): 48-56.
阅读次数
全文


摘要