基于四阶拟牛顿方程的信赖域算法研究
|
摘要
拟牛顿算法是牛顿法的一种推广，牛顿法在每一次迭代过程中都需要很大的工作量来计算海森阵,而且海森阵不好计算，甚至可以说很难求.为了克服牛顿法的这一缺点，研究者以拟牛顿方程为基础构造了拟牛顿算法.利用目标函数的一阶导数信息，构造目标函数的近似曲率，这种算法不需计算海森阵并且在一定的条件下具有超线性收敛性.
在拟牛顿算法中拟牛顿方程具有至关重要的作用.传统的拟牛顿方程忽略了目标函数值的信息只是利用它的梯度信息.考虑到充分利用信息资源，许多研究人员对传统的拟牛顿方程进行了修正，在此基础上提出了新的拟牛顿算法.本文主要是基于文献[7]提出的四阶拟牛顿方程，结合信赖域算法、线搜索技术、非单调技术、自适应技术，针对二次模型及新锥模型进行了研究，提出了关于二次模型及新锥模型的非单调信赖域算法和非单调自适应信赖域算法.这些基于拟牛顿方程的混合算法不仅能保留原有拟牛顿算法的大多数良好性质，并且在近似目标函数的二次曲率时比拟牛顿算法具有更高的精度.本文的主要研究的内容如下：
第一、对于二次模型的研究，在四阶拟牛顿方程及其修改的BFGS校正公式的基础上，将非单调技术、自适应技术与Armijo线搜索、信赖域算法相结合提出了两类非单调自适应信赖域算法．在一定的条件下证明了算法的收敛性.并且给出了相应的数值实验结果.
第二、对于新锥模型的研究，利用四阶拟牛顿方程及其修改的BFGS校正公式，将非单调技术与Wolfe线搜索、信赖域算法相结合提出了一类拟牛顿非单调信赖域算法.在较弱的条件下，证明了此算法的全局收敛性.数值结果表明该算法是有效的.
第三、对于新锥模型的研究，，在四阶拟牛顿方程及其修改的BFGS校正公式的基础上，将非单调技术、自适应技术与Armijo线搜索、信赖域算法相结合提出了两类关于新锥模型的非单调自适应信赖域算法，在一定的条件下证明了算法的收敛性.并且给出了相应的数值实验结果.
Quasi-Newton algorithm is the promotion of the Newton method. It needsmuch of work in each iteration of using the Newton method to calculate theHessian matrix. By using Newton method and it is not easy or even difficult tocalculate the Hessian matrix. In order to overcome this disadvantage of Newtonmethod, the researchers constructed a method named quasi-Newton algorithmbased on quasi-Newton equation. By using the information of the first derivativeof the objective function, quasi-Newton constructs the approximate curvature ofthe objective function. This algorithm don＇t need to calculate to the Hessianmatrix and has super linear convergence.
The quasi-Newton algorithm plays a crucial role in unconstrainedoptimization process. Traditional quasi-Newton equation ignores theinformation of the objective function value; it only uses its gradient information,it is a great waste of information resources. Taking the full use of informationresources into account, at present many researchers modified the traditionalquasi-Newton equation and proposed a new quasi-Newton algorithm. In thispaper, combining with the trust region algorithm, line search technologies, takesa research on the second model and cone model based on the literature [7] inwhich put forward four-order quasi-Newton equation. These mixed algorithmbasing on the quasi-Newton algorithm not only retain the majority properties ofthe old quasi-Newton algorithm, but also can be more exact than the old one inquadratic curvature approximate of the objective function. The main contentsof this paper are as follows:
Firstly, on the basis of the new quasi-Newton equation with four order anda BFGS corrector formula, we introduce a concept of self-adapt. According toArmijo line search technique, a new non-monotonic trust region algorithm isproposed. In the paper, the convergence of the algorithm is proved in certaincondition, and the relevant numerical result is given at the same time.
Secondly, on the basis of the new quasi-Newton equation with four order and a BFGS corrector formula, we propose a quasi-Newton non-monotonic trustregion algorithm combining both the non-monotonic Wolfe line searchtechnique and trust region method about the new cone model. In lowercondition, we prove that the new algorithm is convergence. And the numericalresult shows the algorithm is effective.
Thirdly, on the basis of the new quasi-Newton equation with four order anda BFGS corrector formula, we propose a non-monotonic trust region algorithmabout the new cone model, and the convergence of the algorithm in certaincondition is proved, and the relevant numerical result is given at the same time.
在拟牛顿算法中拟牛顿方程具有至关重要的作用.传统的拟牛顿方程忽略了目标函数值的信息只是利用它的梯度信息.考虑到充分利用信息资源，许多研究人员对传统的拟牛顿方程进行了修正，在此基础上提出了新的拟牛顿算法.本文主要是基于文献[7]提出的四阶拟牛顿方程，结合信赖域算法、线搜索技术、非单调技术、自适应技术，针对二次模型及新锥模型进行了研究，提出了关于二次模型及新锥模型的非单调信赖域算法和非单调自适应信赖域算法.这些基于拟牛顿方程的混合算法不仅能保留原有拟牛顿算法的大多数良好性质，并且在近似目标函数的二次曲率时比拟牛顿算法具有更高的精度.本文的主要研究的内容如下：
第一、对于二次模型的研究，在四阶拟牛顿方程及其修改的BFGS校正公式的基础上，将非单调技术、自适应技术与Armijo线搜索、信赖域算法相结合提出了两类非单调自适应信赖域算法．在一定的条件下证明了算法的收敛性.并且给出了相应的数值实验结果.
第二、对于新锥模型的研究，利用四阶拟牛顿方程及其修改的BFGS校正公式，将非单调技术与Wolfe线搜索、信赖域算法相结合提出了一类拟牛顿非单调信赖域算法.在较弱的条件下，证明了此算法的全局收敛性.数值结果表明该算法是有效的.
第三、对于新锥模型的研究，，在四阶拟牛顿方程及其修改的BFGS校正公式的基础上，将非单调技术、自适应技术与Armijo线搜索、信赖域算法相结合提出了两类关于新锥模型的非单调自适应信赖域算法，在一定的条件下证明了算法的收敛性.并且给出了相应的数值实验结果.
Quasi-Newton algorithm is the promotion of the Newton method. It needsmuch of work in each iteration of using the Newton method to calculate theHessian matrix. By using Newton method and it is not easy or even difficult tocalculate the Hessian matrix. In order to overcome this disadvantage of Newtonmethod, the researchers constructed a method named quasi-Newton algorithmbased on quasi-Newton equation. By using the information of the first derivativeof the objective function, quasi-Newton constructs the approximate curvature ofthe objective function. This algorithm don＇t need to calculate to the Hessianmatrix and has super linear convergence.
The quasi-Newton algorithm plays a crucial role in unconstrainedoptimization process. Traditional quasi-Newton equation ignores theinformation of the objective function value; it only uses its gradient information,it is a great waste of information resources. Taking the full use of informationresources into account, at present many researchers modified the traditionalquasi-Newton equation and proposed a new quasi-Newton algorithm. In thispaper, combining with the trust region algorithm, line search technologies, takesa research on the second model and cone model based on the literature [7] inwhich put forward four-order quasi-Newton equation. These mixed algorithmbasing on the quasi-Newton algorithm not only retain the majority properties ofthe old quasi-Newton algorithm, but also can be more exact than the old one inquadratic curvature approximate of the objective function. The main contentsof this paper are as follows:
Firstly, on the basis of the new quasi-Newton equation with four order anda BFGS corrector formula, we introduce a concept of self-adapt. According toArmijo line search technique, a new non-monotonic trust region algorithm isproposed. In the paper, the convergence of the algorithm is proved in certaincondition, and the relevant numerical result is given at the same time.
Secondly, on the basis of the new quasi-Newton equation with four order and a BFGS corrector formula, we propose a quasi-Newton non-monotonic trustregion algorithm combining both the non-monotonic Wolfe line searchtechnique and trust region method about the new cone model. In lowercondition, we prove that the new algorithm is convergence. And the numericalresult shows the algorithm is effective.
Thirdly, on the basis of the new quasi-Newton equation with four order anda BFGS corrector formula, we propose a non-monotonic trust region algorithmabout the new cone model, and the convergence of the algorithm in certaincondition is proved, and the relevant numerical result is given at the same time.
引文
[1]袁亚湘，孙文瑜.最优化理论与方法[M].科学出版社，2001.
[2]陈兰平，焦宝聪.一类非拟Newton算法及其收敛性[J].应用数学与计算数学学报，1997,2:9-17.
[3] J.Z. Zhang, N.Y. Deng, L.H. Chen. New Quasi-Newton Equation and RelatedMethods for Unconstrained Optimization., J.optim.Theory Appl.,1999,102:147-167.
[4]陈兰平，焦宝聪.非凸无约束优化问题的广义拟牛顿法的全局收敛性[J].应用数学，2005,18（4）:573-579.
[5] D.Li, M. Fukushima. On the global convergence of the BFGS method fornonconvex unconstrained optimization problems[J]. SIMA J. Optim. Anal.,2001,11:1054-1064.
[6] Z.X. Wei, G.H. Yu. Some recent progress in unconstrained nonlinearoptimization numerical linear algebra and optimization: proceedings ofthe2003’s International Conference on Numerical Optimization andNumerical Linear Algebra [C]. Yuan Y, eds. Beijing/New York: SciencePress,2004,110-141.
[7]王希云，时平平.一种基于新拟牛顿方程的拟牛顿法[J].运筹学学报，2007,5:190-195.
[8] YIXUN SHI. Globally convergent algorithms for unconstrainedoptimization[J]. Computational Optimization and Applications,2000,16:295-308.
[9]杨月婷，纪颖，王大力.改进的有限内存BFGS算法的二次终止性质.中国运筹学会第七届学术交流会，山东青岛，2004,10.
[10]袁亚湘，孙文瑜.最优化理论与方法[M].科学出版社，2007.
[11]徐成贤，陈志平，李乃成.近代优化方法[M].科学出版社,2002.
[12]尉继英.一种求解无约束极值问题的无记忆拟牛顿算法[J].计算数学，1990,3:259-269.
[13]谢铁军，陈明文，刘任平.无记忆拟牛顿方法的收敛性[J].运筹与管理，2000,4:57-61.
[14] J.Z. Zhang, C.X.Xu., Properties and numerical performance of Quasi-Newton methods with modified quasi-Newton equations, Journal ofComputational and Applied Mathematics,2001,137:269-278.
[15]李董辉，童小娇，万中.数值最优化[M].科学出版社，2005.
[16] Deng N Y, Xiao Y, Zhou F J.A nonmontonic trust region algorithm[J].JOTA,1993,26:259-285.
[17]柯小伍，韩继业.一类新的信赖域算法的全局收敛性[J].应用数学学报，1995,18（4）:608-615.
[18] E.Michael Gertz. A quasi-Newton trust-region method[J].Math Program,2004,Ser.A.
[19]杨洁，焦宝聪.带线搜索的修正拟牛顿非单调信赖域算法[J].首都师范大学学报，2010,31（1）：1-5.
[20]刘培培，陈兰平.一类拟牛顿非单调信赖域算法及其收敛性[J].数学进展，2008,37（1）：92-100.
[21] Nocedal.J, Yuan Y X. Combining trust region and line search techniques,Advances in Nonlinear Programming,1998,153-175.
[22]李红，焦宝聪.一类带线搜索的非单调自适应信赖域算法[J].首都师范大学学报，2008,29（2）：1-5.
[23]赵绚，王希云.一类新的带线搜索的自适应非单调信赖域算法[J].太原科技大学学报，2010,31（1）：68-71.
[24]吴海平，倪琴.一个新锥模型信赖域算法[J].高等学校计算数学学报，2008,30（1）：57-67.
[25]李改弟.一个自动确定信赖域半径的信赖域方法[J].工程数学学报，2006,23（5）：843-848.
[26] Ni Q. Optimality Conditions for trust-region subproblems involving aconic model. SIAM J. Optim.,2005,15(3):826-837
[27]陆晓平,倪勤,刘浩．解新锥模型信赖域子问题的折线法[J]．应用数学学报,2007,30(5):854-871
[28]杨春，倪勤.变步长非单调模式搜索法[J].高等学校计算数学学报，2005,(27):160-168
[29] Deng N Y, Xiao Y, Zhou F J.A nonmontonic trust region algorithm[J].JOTA,1993,26:259-285.
[30] Sun W．Nonmonotone trust region method for optimization[J]. Appl．Math．Comput,2004,156:159-174
[31] Sun W Y, Yuan J Y and Yuan Y X．Trust region method of conic model for linearlyConstrained optimization[M]．ICM-96-003,1996
[32] J.Zhang,A nonmonotone adaptive trust region method for unconstrainedoptimization based on conic model[J],Applied thematics andComputation,2010,217:4265-4273
[33] Ni Q． Optimality Conditions for trust-region subproblems involving a conic model.SIAM J[J]．Optim,2005,15(3):826-837
[34]王庆,王希云．锥模型信赖域算法中水平向量的选取[J].太原科技大学学报,2008,29(6):446-448
[35]诸梅芳,薛毅,张凤圣．锥模型的拟NEWTON型信赖域方法[J]．高等学校计算学学报,1995,17(1):36-47
[36]时平平.关于无约束优化问题的拟牛顿算法研究[D].太原:太原科技大学.2008
[37]王庆.新锥模型赖域算法[D].太原:太原科技大学,2009
[38]赵绚.新锥模型信赖域算法研究[D].太原:太原科技大学.2010
[39]杨旭岩,王东升,王宏杰．锥模型的拟牛顿信赖域方法中水平向量的选取[J]．河南机电高等专科学校学报,2001,9(4):43-45
[40] Ya-Xiang Yuan, A Modified BFGS Algorithm for Unconstrained Optimization,IMA Journal of Numerical Analysis,1991,11:325-332.
[2]陈兰平，焦宝聪.一类非拟Newton算法及其收敛性[J].应用数学与计算数学学报，1997,2:9-17.
[3] J.Z. Zhang, N.Y. Deng, L.H. Chen. New Quasi-Newton Equation and RelatedMethods for Unconstrained Optimization., J.optim.Theory Appl.,1999,102:147-167.
[4]陈兰平，焦宝聪.非凸无约束优化问题的广义拟牛顿法的全局收敛性[J].应用数学，2005,18（4）:573-579.
[5] D.Li, M. Fukushima. On the global convergence of the BFGS method fornonconvex unconstrained optimization problems[J]. SIMA J. Optim. Anal.,2001,11:1054-1064.
[6] Z.X. Wei, G.H. Yu. Some recent progress in unconstrained nonlinearoptimization numerical linear algebra and optimization: proceedings ofthe2003’s International Conference on Numerical Optimization andNumerical Linear Algebra [C]. Yuan Y, eds. Beijing/New York: SciencePress,2004,110-141.
[7]王希云，时平平.一种基于新拟牛顿方程的拟牛顿法[J].运筹学学报，2007,5:190-195.
[8] YIXUN SHI. Globally convergent algorithms for unconstrainedoptimization[J]. Computational Optimization and Applications,2000,16:295-308.
[9]杨月婷，纪颖，王大力.改进的有限内存BFGS算法的二次终止性质.中国运筹学会第七届学术交流会，山东青岛，2004,10.
[10]袁亚湘，孙文瑜.最优化理论与方法[M].科学出版社，2007.
[11]徐成贤，陈志平，李乃成.近代优化方法[M].科学出版社,2002.
[12]尉继英.一种求解无约束极值问题的无记忆拟牛顿算法[J].计算数学，1990,3:259-269.
[13]谢铁军，陈明文，刘任平.无记忆拟牛顿方法的收敛性[J].运筹与管理，2000,4:57-61.
[14] J.Z. Zhang, C.X.Xu., Properties and numerical performance of Quasi-Newton methods with modified quasi-Newton equations, Journal ofComputational and Applied Mathematics,2001,137:269-278.
[15]李董辉，童小娇，万中.数值最优化[M].科学出版社，2005.
[16] Deng N Y, Xiao Y, Zhou F J.A nonmontonic trust region algorithm[J].JOTA,1993,26:259-285.
[17]柯小伍，韩继业.一类新的信赖域算法的全局收敛性[J].应用数学学报，1995,18（4）:608-615.
[18] E.Michael Gertz. A quasi-Newton trust-region method[J].Math Program,2004,Ser.A.
[19]杨洁，焦宝聪.带线搜索的修正拟牛顿非单调信赖域算法[J].首都师范大学学报，2010,31（1）：1-5.
[20]刘培培，陈兰平.一类拟牛顿非单调信赖域算法及其收敛性[J].数学进展，2008,37（1）：92-100.
[21] Nocedal.J, Yuan Y X. Combining trust region and line search techniques,Advances in Nonlinear Programming,1998,153-175.
[22]李红，焦宝聪.一类带线搜索的非单调自适应信赖域算法[J].首都师范大学学报，2008,29（2）：1-5.
[23]赵绚，王希云.一类新的带线搜索的自适应非单调信赖域算法[J].太原科技大学学报，2010,31（1）：68-71.
[24]吴海平，倪琴.一个新锥模型信赖域算法[J].高等学校计算数学学报，2008,30（1）：57-67.
[25]李改弟.一个自动确定信赖域半径的信赖域方法[J].工程数学学报，2006,23（5）：843-848.
[26] Ni Q. Optimality Conditions for trust-region subproblems involving aconic model. SIAM J. Optim.,2005,15(3):826-837
[27]陆晓平,倪勤,刘浩．解新锥模型信赖域子问题的折线法[J]．应用数学学报,2007,30(5):854-871
[28]杨春，倪勤.变步长非单调模式搜索法[J].高等学校计算数学学报，2005,(27):160-168
[29] Deng N Y, Xiao Y, Zhou F J.A nonmontonic trust region algorithm[J].JOTA,1993,26:259-285.
[30] Sun W．Nonmonotone trust region method for optimization[J]. Appl．Math．Comput,2004,156:159-174
[31] Sun W Y, Yuan J Y and Yuan Y X．Trust region method of conic model for linearlyConstrained optimization[M]．ICM-96-003,1996
[32] J.Zhang,A nonmonotone adaptive trust region method for unconstrainedoptimization based on conic model[J],Applied thematics andComputation,2010,217:4265-4273
[33] Ni Q． Optimality Conditions for trust-region subproblems involving a conic model.SIAM J[J]．Optim,2005,15(3):826-837
[34]王庆,王希云．锥模型信赖域算法中水平向量的选取[J].太原科技大学学报,2008,29(6):446-448
[35]诸梅芳,薛毅,张凤圣．锥模型的拟NEWTON型信赖域方法[J]．高等学校计算学学报,1995,17(1):36-47
[36]时平平.关于无约束优化问题的拟牛顿算法研究[D].太原:太原科技大学.2008
[37]王庆.新锥模型赖域算法[D].太原:太原科技大学,2009
[38]赵绚.新锥模型信赖域算法研究[D].太原:太原科技大学.2010
[39]杨旭岩,王东升,王宏杰．锥模型的拟牛顿信赖域方法中水平向量的选取[J]．河南机电高等专科学校学报,2001,9(4):43-45
[40] Ya-Xiang Yuan, A Modified BFGS Algorithm for Unconstrained Optimization,IMA Journal of Numerical Analysis,1991,11:325-332.