(修改稿)一种新的修正DY共轭梯度法的全局收敛性.doc

一种修正的DY共轭梯度法的全局收敛性 收稿日期：2013-05-07;作者简介: 敖卫斌（1987-），男，重庆九龙坡人，硕士研究生，主要从事最优化理论与研究.敖卫斌（重庆师范大学 数学学院，重庆 401331）摘要：本文提出了一种新的非线性修正的DY共轭梯度算法（MDYCG）,该算法得到的搜索方向为下降方向，它既不受线搜索规则的影响，也不受目标函数的凸性影响。在精确线搜索下，MDYCG算法化归为标准的DY共轭梯度算法。证明了该方法在Armijo型线搜索下的全局收敛性，给出了初步的数值结果。关键词：无约束优化；共轭梯度法；Armijo型线搜索；全局收敛性中图分类号：0182.11. 引言考虑无约束优化问题： （1）其中为连续可微函数，其梯度向量记为，简记为g。共轭梯度法是求解大规模无约束优化问题的有效算法之一，它像最速下降法一样在每步迭代中不需要存储和计算矩阵，其迭代格式为： (2) (3)其中，为搜索方向，是通过一维线搜索获得的步长，为标量。不同的对应着不同的共轭梯度算法。1964, Fletcher 和 Reeves首先提出非线性共轭梯度法参数，它定义为(2). 还有其他著名的，比如 ( 3-4)，(5), (6),(7), （8）；其中为欧几里得范数,。FR方法、CD方法和DY方法具有较好的理论收敛性，然而PRP方法、HS方法和LS方法具有较好的数值计算结果。张丽在文献9中提出了修正的FR方法的搜索方向，从而使得新的算法具有充分下降性和全局收敛性，得到了较好的数值试验结果。本文在文献9的启发下，选取不同的，提出了一种修正的DY算法（MDYCG）并证明了该算法在Armijo型线搜索下的全局收敛性。所采用的Armijo型线搜索准则：取步长 （4）满足 （5）其中。 2. 修正的DY新算法本文给出的新算法迭代格式为（2）和 (6)其中，我们称 (2) 和(6)为 MDY方法。当线搜索为精确线搜索时，MDYCG就得到标准的DY共轭梯度法。同时由和式（6），易知对,有： （7）下面给出新的算法步骤：（1）给出，令 k:=1,，若，立即停止；（2）找到满足Armijo型线搜索规则；（3）令, 且，若，立即停止；（4）通过计算,并由式（6）得；（5）令k:=k+1，返回（2）。本文做如下假设：（A）在水平集有下界，其中为初始点。（B）的一个领域内，连续可微且其梯度向量满足Lipschitz条件，即存在常数，使得 。 （8）同时由上述的假设可以得到存在正常数和满足： 。 （9）3.算法的收敛性引理 3.1 假设A，B成立，MDYCG算法中满足Armijo型线搜索，则有 成立，其中。证明：如果, 有 ，再由 (7) 和施瓦兹不等式, 得 则对成立。如果, 由 Armijo型线搜索规则, 不满足不等式(5). 则有： （10）由中值定理和假设B , 存在某一个使得 （11） 结合不等式（10）、（11）和（7）得 证毕。引理 3.2假设A，B成立，MDYCG算法中满足Armijo型线搜索，则有Zoutendijk条件 （12）证明： 由假设A和（5）, 有 ，再由式子（7）有 （13）由引理1和（13），可以得到，证毕。定理3.3若假设A和B成立，MDYCG算法中满足Armijo型线搜索，或者对某个k成立，或者有 。证明：反正法。假设结论不成立，则存在一个常数使得 ，成立 （14）由（6）有 。两边同时除以，结合（7）和（14）有 = = = ，则由最后一个不等式有 这与（12）矛盾，证毕。4.数值试验 本节在标准Armijo型非精确线搜索准则下，利用MARTLAB7.1， MDY方法对测试函数10进行试算。表格中Problem表示测试函数的名称,NI/NF/NG 分别代表迭代次数、函数迭代次数、梯度迭代次数，Dim表示测试函数自变量的个数，表示迭代失败。计算中参数，取，VP代表极值点，OV代表极值。终止条件为。表1 MDY方法在Armijo型搜索下的数值结果ProblemDimNI/NF/NGVPOVRosenbrock2103/1763/104(1.0000,1.0000)8.0655e-012Froth2240/6504/241(11.4128,-0.8968)48.983Powell B.S.2Beale273/1100/79(3.0000,0.5000)2.0805e-011Gaussian37/54/8(0.3990,1.0000,-0.0000)1.1317e-008Extended Rosebrock8110/1886/111(1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000)1.0833e-011上述表1简单的数值试验表明了新方法的特点，该方法是有效的。参考文献1 SHI Z J. Convergence of line search methods for unconstrained optimization J. Applied Mathematics and Computation, 2004,157:393-4052FLETCHER R, REEVES C. Function minimization by conjugate gradientsJ. Computer Journal, 1964, 7:149-1543 POLAK E ，RIBIERE G. Note sur la convergence de directions conjugeesJ. Rev Francaise Informat Recherche Operatinelle, 3e Annee, 1969, 16: 35-434 POLAK B T. The conjugate gradient method in extremem problems, USSR Comp Math and Math. Phys.1969,9: 94-1125 HESTENES M R , STEIFEL E L. Methods of conjugate gradients for solving linear systemsJ. J Res Nat Bur Standards Sect. 1952, 5(49): 409-4366 LIU Y , STIEFEL C. Efficient generalized conjugate gradient algorithmsJ. JOTA, 1991 , 69(1): 129-1527 DAI Y H , YUAN Y X. A nonlinear conjugate gradient with a strong global convergence propertyJ. SIAM Journal on Optimization, 1999, 10(1): 177-1828 FLETCHER R. Practical methods of optimization M. New York: Unconstrained Optimization,19879 ZHANG L, ZHOU W J. LI D H. Global convergence of a modified Fletcher-Reeves conjugate gradient method method with Armijo-type line searchJ. Numerische Mathematik 2006,104(4):561-57210MORE J J,GARBOW B S,HILLSTROMK E. Testing unconstrained optimization softwareJ.ACM Trans,Math.Software,1981,7(1):17-41Global convergence of a conjugate gradient method for modified DY formula Ao Wei-bin（College of Mathematics, Chongqing Normal University, Chongqing ，401331）Abstract: The article presents a nonlinear modified DY conjugate gradient (MDYCG) method. The direction generated by the method is a descent direction for the objective function, and this property depends neither on the line search used, nor on the convexity of the objective function. The modified method reduces to the standard DY method if line search is exact. Global convergence of the MDYCG method with