一类新的基于信赖域技术的非单调共轭梯度算法
|
摘要
为有效求解大规模无约束优化问题,本文基于信赖域技术和修正拟牛顿方程,同时结合Zhang H.C.策略和Gu N.Z.策略,设计了一种新的非单调共轭梯度算法,应用信赖域技术保证了算法的稳健性和收敛性,并给出了算法的全局收敛性分析.在适当条件下,证明了该算法具有线性收敛性.数值实验表明新算法能够有效求解病态和大规模问题.与单独结合其中一种非单调策略的算法相比,新算法需要较少的迭代次数和运行时间,利用其得到的函数值与最优值更接近.
In order to effectively solve the large-scale unconstrained optimization problem,based on the trust region technique and the modified quasi-Newton equation, a new nonmonotone conjugate gradient algorithm is presented by combining Zhang H. C. and Gu N. Z.strategy in this paper. The trust region technique is applied to ensure the robustness and convergence of the algorithm, and the global convergence property of the algorithm is also analyzed.Under some reasonable conditions, it is proved that the proposed algorithm is linear convergent.Numerical examples indicate that the new algorithm can effectively solve ill-conditioned and large-scale problems. Compared with the algorithm that combines one of the non-monotonic strategies, the new algorithm requires fewer iteration numbers and less running time, and the function value obtained by the new algorithm is closer to the optimal value.
In order to effectively solve the large-scale unconstrained optimization problem,based on the trust region technique and the modified quasi-Newton equation, a new nonmonotone conjugate gradient algorithm is presented by combining Zhang H. C. and Gu N. Z.strategy in this paper. The trust region technique is applied to ensure the robustness and convergence of the algorithm, and the global convergence property of the algorithm is also analyzed.Under some reasonable conditions, it is proved that the proposed algorithm is linear convergent.Numerical examples indicate that the new algorithm can effectively solve ill-conditioned and large-scale problems. Compared with the algorithm that combines one of the non-monotonic strategies, the new algorithm requires fewer iteration numbers and less running time, and the function value obtained by the new algorithm is closer to the optimal value.
引文
[1]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1997Yuan Y X,Sun W Y.Theory and Method of Optimization[M].Beijing:Science Press,1997
[2]戴彧虹,袁亚湘.非线性共轭梯度法[M].上海:上海科学技术出版社,2000Dai Y H,Yuan Y X.Nonlinear Conjugate Gradient Method[M].Shanghai:Shanghai Science and Technology Press,2000
[3]Grippo L,Lampariello F,Lucidi S.A nonmonotone line search technique for Newton’s method[J].SIAM Journal on Numerical Analysis,1986,23(4):707-716
[4]Zhang H C,Hager W W.A nonmonotone line search technique and its application to unconstrained optimization[J].SIAM Journal on Optimization,2004,14(4):1043-1056
[5]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(9):2158-2172
[6]Powell M J D.A new algorithm for unconstrained optimization[M]//Rosen J B,Mangasarian O L,Ritter K.Nonlinear Programming.New York:Academic Press,1970:31-65
[7]时贞军,孙国.无约束优化问题的对角稀疏拟牛顿法[J].系统科学与数学,2006,26(1):101-112Shi Z J,Sun G.A diagonal-sparse quasi-Newton method for unconstrained optimization problem[J].Journal of System Science and Mathematical Science,2006,26(1):101-112
[8]Wei Z X,Li G Y,Qi L Q.New quasi-Newton methods for unconstrained optimization problems[J].Applied Mathematics and Computation,2006,175(2):1156-1188
[9]孙清滢,徐敏才,刘丽敏.基于信赖域技术的非单调非线性共轭梯度算法[J].工程数学学报,2011,28(5):686-692Sun Q Y,Xu M C,Liu L M.Non-monotone nonlinear conjugate gradient method based on the trust region technique[J].Chinese Journal of Engineering Mathematics,2011,28(5):686-692
[10]Yuan Y X,Stoer J.A subspace study on conjugate gradient algorithms[J].Journal of Applied Mathematics and Mechanics Zeitschrift F¨ur Angewandte Mathematik Und Mechanik,1995,75(1):69-77
[11]张祖华,时贞军.解无约束优化的一种新的共轭梯度法[J].数学进展,2009,38(3):340-344Zhang Z H,Shi Z J.A new conjugate gradient method for unconstrained optimization[J].Advances in Mathematics,2009,38(3):340-344
[12]孙清滢,王宣战,宫恩龙,等.基于信赖域技术和修正拟牛顿方程的非单调共轭梯度算法[J].高等学校计算数学学报,2012,35(1):49-62Sun Q Y,Wang X Z,Gong E L,et al.Non-monotone conjugate gradient method based on trust region technique and modified quasi-Newton equation[J].Journal of Computing Mathematics in Colleges and Universities,2012,35(1):49-62
[2]戴彧虹,袁亚湘.非线性共轭梯度法[M].上海:上海科学技术出版社,2000Dai Y H,Yuan Y X.Nonlinear Conjugate Gradient Method[M].Shanghai:Shanghai Science and Technology Press,2000
[3]Grippo L,Lampariello F,Lucidi S.A nonmonotone line search technique for Newton’s method[J].SIAM Journal on Numerical Analysis,1986,23(4):707-716
[4]Zhang H C,Hager W W.A nonmonotone line search technique and its application to unconstrained optimization[J].SIAM Journal on Optimization,2004,14(4):1043-1056
[5]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(9):2158-2172
[6]Powell M J D.A new algorithm for unconstrained optimization[M]//Rosen J B,Mangasarian O L,Ritter K.Nonlinear Programming.New York:Academic Press,1970:31-65
[7]时贞军,孙国.无约束优化问题的对角稀疏拟牛顿法[J].系统科学与数学,2006,26(1):101-112Shi Z J,Sun G.A diagonal-sparse quasi-Newton method for unconstrained optimization problem[J].Journal of System Science and Mathematical Science,2006,26(1):101-112
[8]Wei Z X,Li G Y,Qi L Q.New quasi-Newton methods for unconstrained optimization problems[J].Applied Mathematics and Computation,2006,175(2):1156-1188
[9]孙清滢,徐敏才,刘丽敏.基于信赖域技术的非单调非线性共轭梯度算法[J].工程数学学报,2011,28(5):686-692Sun Q Y,Xu M C,Liu L M.Non-monotone nonlinear conjugate gradient method based on the trust region technique[J].Chinese Journal of Engineering Mathematics,2011,28(5):686-692
[10]Yuan Y X,Stoer J.A subspace study on conjugate gradient algorithms[J].Journal of Applied Mathematics and Mechanics Zeitschrift F¨ur Angewandte Mathematik Und Mechanik,1995,75(1):69-77
[11]张祖华,时贞军.解无约束优化的一种新的共轭梯度法[J].数学进展,2009,38(3):340-344Zhang Z H,Shi Z J.A new conjugate gradient method for unconstrained optimization[J].Advances in Mathematics,2009,38(3):340-344
[12]孙清滢,王宣战,宫恩龙,等.基于信赖域技术和修正拟牛顿方程的非单调共轭梯度算法[J].高等学校计算数学学报,2012,35(1):49-62Sun Q Y,Wang X Z,Gong E L,et al.Non-monotone conjugate gradient method based on trust region technique and modified quasi-Newton equation[J].Journal of Computing Mathematics in Colleges and Universities,2012,35(1):49-62