解无约束优化的非单调信赖域法和Perry-Shanno无记忆拟牛顿法
|
摘要
本文对求解无约束优化问题(?)f(x)给出三个算法：(1)不重解子问题的非单调自适应信赖域算法。(2)非单调Perry-Shanno无记忆拟牛顿方法，(3)非单调带参数的Perry-Shanno无记忆拟牛顿法。本文主要工作如下：
(1)文[2]给出了一种自适应信赖域算法，其调整信赖域半径的公式是△_(k+1)=R_(c_2)(r_k)‖d_k‖。其中R_η(t)称为R-函数。我们给出一个比文[2]简单的新的R-函数R_η(t)并采用公式△_(k+1)=R_(c_2)(r_k)△_k调整信赖域半径。在数值试验中我们发现当试探步d_k被接受时，有时d_k可能是f(x)的一个极好的下降方向。取x_(k+1)=x_k+d_k可能并没有充分利用这个好的下降方向d_k，对这种情形，我们采用一种不精确线搜索来确定x_(k+1)。另外当试探步d_k不被接受时，我们没有重解子问题或向后线搜索，而是采用了一个固定的公式给出新的迭代点x_(k+1)。对采用上述技巧的信赖域算法，在适当条件下，我们证明了它的全局收敛性。数值试验表明该算法是有效的。
(2)对非单调线搜索的Perry-Shanno无记忆拟牛顿法，我们不仅证明了f(x)是凸函数时的全局收敛性，同时在f(x)是非凸函数时的收敛性也作了深入的探讨，并给出了几个收敛的充分条件。初步的数值试验表明了算法的有效性。
(3)在第二个工作的基础上给出了非单调带参数的Perry-Shanno无记忆拟牛顿算法，我们不仅证明了f(x)是凸函数时的全局收敛性，同时在f(x)是非凸函数时的收敛性也作了深入的探讨，并给出了几个收敛的充分条件。并且可以通过参数的选取来控制解的误差，最后给出了几个演示性的算例。
In this paper, we propose three methods for unconstrained optimiza-tion.(1).a new nonmonotonic self-adaptive trust region algorithm without resolv-ing the subproblem.(2). nonmonotonic Perry-Shanno Memoryless Quasi-Newtonmethod.(3).nonmonotonic Perry-Shanno Memoryless Quasi-Newton method with pa-rameter, the dissertation can be summarized as follows:
1. Paper [2] proposes a self-adaptive trust region algorithm, and the formula oftrust region radius is△_(k+i)= R_(c_2)(r_k)‖d_k‖.Where R_η(t) names R-function.wepropose a new R-function which is simpler than Paper [2],and define a formula△_(k+1)= R_(c_2)(r_k)△_k as trust region radius, when a trial step is accepted,sometimesd_k is a good descend direction,we take a inexact line search to obtain x_(k+1).When atrial step is not accepted,the method does not reslove the subproblem but generatesa iterative point whose steplength is defined by a formula.Under mild conditions,weprove that the algorithm is global convergence.Numerical results are presented whichshow that the method is effective. Numerical results are also presented.
2. This chapter will try to discuss nonmonotonic Memoryless Quasi-Newtonmethod.The convergence of this method is proved for convex function and non-convex function. Primary numerical results demonstrate that the algorithm is efficient.
3. The chapter takes nonmonotonic Perry-Shanno Memoryless Quasi-Newtonmethod with parameter. The convergence of this method is proved for convex functionand non-convex function.Preliminary numerical experiments show that the proposedalgorithm is effective.
(1)文[2]给出了一种自适应信赖域算法，其调整信赖域半径的公式是△_(k+1)=R_(c_2)(r_k)‖d_k‖。其中R_η(t)称为R-函数。我们给出一个比文[2]简单的新的R-函数R_η(t)并采用公式△_(k+1)=R_(c_2)(r_k)△_k调整信赖域半径。在数值试验中我们发现当试探步d_k被接受时，有时d_k可能是f(x)的一个极好的下降方向。取x_(k+1)=x_k+d_k可能并没有充分利用这个好的下降方向d_k，对这种情形，我们采用一种不精确线搜索来确定x_(k+1)。另外当试探步d_k不被接受时，我们没有重解子问题或向后线搜索，而是采用了一个固定的公式给出新的迭代点x_(k+1)。对采用上述技巧的信赖域算法，在适当条件下，我们证明了它的全局收敛性。数值试验表明该算法是有效的。
(2)对非单调线搜索的Perry-Shanno无记忆拟牛顿法，我们不仅证明了f(x)是凸函数时的全局收敛性，同时在f(x)是非凸函数时的收敛性也作了深入的探讨，并给出了几个收敛的充分条件。初步的数值试验表明了算法的有效性。
(3)在第二个工作的基础上给出了非单调带参数的Perry-Shanno无记忆拟牛顿算法，我们不仅证明了f(x)是凸函数时的全局收敛性，同时在f(x)是非凸函数时的收敛性也作了深入的探讨，并给出了几个收敛的充分条件。并且可以通过参数的选取来控制解的误差，最后给出了几个演示性的算例。
In this paper, we propose three methods for unconstrained optimiza-tion.(1).a new nonmonotonic self-adaptive trust region algorithm without resolv-ing the subproblem.(2). nonmonotonic Perry-Shanno Memoryless Quasi-Newtonmethod.(3).nonmonotonic Perry-Shanno Memoryless Quasi-Newton method with pa-rameter, the dissertation can be summarized as follows:
1. Paper [2] proposes a self-adaptive trust region algorithm, and the formula oftrust region radius is△_(k+i)= R_(c_2)(r_k)‖d_k‖.Where R_η(t) names R-function.wepropose a new R-function which is simpler than Paper [2],and define a formula△_(k+1)= R_(c_2)(r_k)△_k as trust region radius, when a trial step is accepted,sometimesd_k is a good descend direction,we take a inexact line search to obtain x_(k+1).When atrial step is not accepted,the method does not reslove the subproblem but generatesa iterative point whose steplength is defined by a formula.Under mild conditions,weprove that the algorithm is global convergence.Numerical results are presented whichshow that the method is effective. Numerical results are also presented.
2. This chapter will try to discuss nonmonotonic Memoryless Quasi-Newtonmethod.The convergence of this method is proved for convex function and non-convex function. Primary numerical results demonstrate that the algorithm is efficient.
3. The chapter takes nonmonotonic Perry-Shanno Memoryless Quasi-Newtonmethod with parameter. The convergence of this method is proved for convex functionand non-convex function.Preliminary numerical experiments show that the proposedalgorithm is effective.
引文
[1] J.J. More, B.S. Garbow and K.E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software 7(1), (1981) 17-41.
[2] Long Hei, A self-Adaptive trust region algorithm, Journal of Computational Mathematics, 21, (2003), 229-236.
[3] J.Nocedal, Y.Yuan, Combing trust region and line search techniques, in Y.Yuan ed. Adavances in Nonlinear Programming,(Kluver, 1998), 153-175.
[4] Jie.Sun,Jiapu.Zhang, Global convergence of conjugate gradient methods without line search, Ann.Oper.Res. 103, (2001) 161-173.
[5] Xiongda.Chen,Jie.Sun, Global convergence of a two-parameter family of conjugate gradient methods without line search,J.Comput.Appl.Math. 146, (2002) 37-45.
[6] Jiangtao.Mo,Kecun.Zhang,Zengxin.Wei,A nonmonotone trust region method for unconstrained optimization,Applied Mathematics and Computation 171, (2005) 371-384.
[7] S.B.Yao,B.C.Shi,Y.H.Peng,A nonmonotone trust region algorithm with linesearch,J.of Math 23, (2003) 290-294.
[8] YuHong.Dai, Dachuan Xu,A new family of trust region algorithms for unconstrained optimization, Joural of Computation Mathematics 21, (2003) 221-228.
[9] Jie.Sun,Jiapu.Zhang, Global convergence of conjugate gradient methods without line search, Ann.Oper.Res. 103, (2001) 161-173.
[10] L.Grippo, ELampariello, S.Lucidi, A nonmonotonic line search technique for Newton's methods, SIAM Journal on Numerical Analysis, 23, (1986), 707-716.
[11] J.Zhang,X.Zhang,A nonmonotone adaptive trust region method and its convergence, Comput. Math. Appl.45,(10-11) (2003) 1469-1477.
[12] N.Y.Deng, Y. Xiao,F.J.Zhou, Nonmonotone trust region algorithm, for unconstrained optimization problems,J. Optim. Theory Appl, 76, (1996) 259-285.
[13] W. Sun, Nonmonotone trust-region method for solving optimization problems, Applied Mathematics and Computing, 156 (2004), 159-174.
[14] J.H. Fu, W. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems, Applied Mathematic and Computation, 163, (2005) 489-504.
[15] Jiye.Han,Guanghui.Liu,Hongxia.Yin,Convergence of Perry and Shanno's Memoryless Quassi-Newton Method for Nonconvex Optimization Problems运筹学学报，1(1)(1997)，22-28．
[16] J.Y. Fan and Y.X.Yuan,A new trust region algorithm with trust region radius converging to zero, in Proceedings of the 5th International Conference on Optimization:Techniques and Applications,Hongkong, (2001), 786-794.
[17] J.Y. Fan, A line search and trust region algorithm with trust region radius converging to zero, Journal of Computational Mathematics, 22(6) (2004), 865-872.
[18] T.Steihaug,The conjugate gradient method and trust regions inlarge scale optimization, SIAM J.Numer. Anal, 20 (1983),626-637.
[19] D.F. Shanno, Conjugate gradient methods with inexact search, Math.Oper.Res, 3 (1978), 244-256.
[20] 谢铁军，陈明文，刘任平，无记忆拟牛顿方法的收敛性，运筹与管理，9(4)(2000)，57-61．
[21] 谢铁军，陈明文，程涛，带有参数的Perry-Shanno无记忆拟牛顿方法的收敛性，北京科技大学学报，22(6)，(2000)，16-18．
[22] 颜世建，一种无记忆拟牛顿法的收敛性，南京师范大学学报(自然科学版)，27(2)(2004)，9-16．
[23] 戴或虹，无记忆拟牛顿法的收敛性质，数值计算与计算机应用，1(2000)，28-32．
[24] 于静静，焦宝聪，Perry-Shanno无记忆拟牛顿方法在非单调搜索下的收敛性，首都师范大学学报(自然科学版)，27(6)(2006)，10-14．
[25] 尉继英，一种求解无约束极值问题的无记忆拟牛顿算法，计算数学，11(3)(1990)，259-269．
[26] 李改弟，一个自动确定信赖域半径的信赖域方法，工程数学学报，23(5)(2006)，843-848．
[27] 柯小伍，韩继业一类新的信赖域算法的全局收敛性，应用数学学报，18(4)(1995)，608-615．
[28] 邓乃杨，陈志，适用拟牛顿迭代法的广义共轭梯度法(I)，计算数学，5(1983)，435-443．
[29] 袁亚湘，孙文瑜，最优化理论与方法，北京科学出版社，1997．
[30] 袁亚湘，非线性规划数值方法，上海科学技术出版社1993
[31] 盛昭瀚，最优化方法基本教程，东南大学出版社，1992．
[32] 席少霖，非线性最优化方法，高等教育出版社，(1992)．
[2] Long Hei, A self-Adaptive trust region algorithm, Journal of Computational Mathematics, 21, (2003), 229-236.
[3] J.Nocedal, Y.Yuan, Combing trust region and line search techniques, in Y.Yuan ed. Adavances in Nonlinear Programming,(Kluver, 1998), 153-175.
[4] Jie.Sun,Jiapu.Zhang, Global convergence of conjugate gradient methods without line search, Ann.Oper.Res. 103, (2001) 161-173.
[5] Xiongda.Chen,Jie.Sun, Global convergence of a two-parameter family of conjugate gradient methods without line search,J.Comput.Appl.Math. 146, (2002) 37-45.
[6] Jiangtao.Mo,Kecun.Zhang,Zengxin.Wei,A nonmonotone trust region method for unconstrained optimization,Applied Mathematics and Computation 171, (2005) 371-384.
[7] S.B.Yao,B.C.Shi,Y.H.Peng,A nonmonotone trust region algorithm with linesearch,J.of Math 23, (2003) 290-294.
[8] YuHong.Dai, Dachuan Xu,A new family of trust region algorithms for unconstrained optimization, Joural of Computation Mathematics 21, (2003) 221-228.
[9] Jie.Sun,Jiapu.Zhang, Global convergence of conjugate gradient methods without line search, Ann.Oper.Res. 103, (2001) 161-173.
[10] L.Grippo, ELampariello, S.Lucidi, A nonmonotonic line search technique for Newton's methods, SIAM Journal on Numerical Analysis, 23, (1986), 707-716.
[11] J.Zhang,X.Zhang,A nonmonotone adaptive trust region method and its convergence, Comput. Math. Appl.45,(10-11) (2003) 1469-1477.
[12] N.Y.Deng, Y. Xiao,F.J.Zhou, Nonmonotone trust region algorithm, for unconstrained optimization problems,J. Optim. Theory Appl, 76, (1996) 259-285.
[13] W. Sun, Nonmonotone trust-region method for solving optimization problems, Applied Mathematics and Computing, 156 (2004), 159-174.
[14] J.H. Fu, W. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems, Applied Mathematic and Computation, 163, (2005) 489-504.
[15] Jiye.Han,Guanghui.Liu,Hongxia.Yin,Convergence of Perry and Shanno's Memoryless Quassi-Newton Method for Nonconvex Optimization Problems运筹学学报，1(1)(1997)，22-28．
[16] J.Y. Fan and Y.X.Yuan,A new trust region algorithm with trust region radius converging to zero, in Proceedings of the 5th International Conference on Optimization:Techniques and Applications,Hongkong, (2001), 786-794.
[17] J.Y. Fan, A line search and trust region algorithm with trust region radius converging to zero, Journal of Computational Mathematics, 22(6) (2004), 865-872.
[18] T.Steihaug,The conjugate gradient method and trust regions inlarge scale optimization, SIAM J.Numer. Anal, 20 (1983),626-637.
[19] D.F. Shanno, Conjugate gradient methods with inexact search, Math.Oper.Res, 3 (1978), 244-256.
[20] 谢铁军，陈明文，刘任平，无记忆拟牛顿方法的收敛性，运筹与管理，9(4)(2000)，57-61．
[21] 谢铁军，陈明文，程涛，带有参数的Perry-Shanno无记忆拟牛顿方法的收敛性，北京科技大学学报，22(6)，(2000)，16-18．
[22] 颜世建，一种无记忆拟牛顿法的收敛性，南京师范大学学报(自然科学版)，27(2)(2004)，9-16．
[23] 戴或虹，无记忆拟牛顿法的收敛性质，数值计算与计算机应用，1(2000)，28-32．
[24] 于静静，焦宝聪，Perry-Shanno无记忆拟牛顿方法在非单调搜索下的收敛性，首都师范大学学报(自然科学版)，27(6)(2006)，10-14．
[25] 尉继英，一种求解无约束极值问题的无记忆拟牛顿算法，计算数学，11(3)(1990)，259-269．
[26] 李改弟，一个自动确定信赖域半径的信赖域方法，工程数学学报，23(5)(2006)，843-848．
[27] 柯小伍，韩继业一类新的信赖域算法的全局收敛性，应用数学学报，18(4)(1995)，608-615．
[28] 邓乃杨，陈志，适用拟牛顿迭代法的广义共轭梯度法(I)，计算数学，5(1983)，435-443．
[29] 袁亚湘，孙文瑜，最优化理论与方法，北京科学出版社，1997．
[30] 袁亚湘，非线性规划数值方法，上海科学技术出版社1993
[31] 盛昭瀚，最优化方法基本教程，东南大学出版社，1992．
[32] 席少霖，非线性最优化方法，高等教育出版社，(1992)．