一种线搜索下DY共轭梯度法的全局收敛性

一种线搜索下DY共轭梯度法的全局收敛性 一种线搜索下DY共轭梯度法的全局收敛性 第19卷第1期 2006年3月 青岛大学(自然科学版)vO1.19No.1 JOURNALOFQINGDAOUNIVERSITY(NaturalScienceEdition)Mar.2006 文章编号:loo6—1037(2006)01—0027—03 一 种线搜索下DY共轭梯度法的全局收敛性 郑希锋,田志远,杜守强,王艳 (青岛大学理工学院系,山东青岛266O71) 摘要:利用王长钰等人提出的一种新型线搜索条件对Dai--Yuan非线性共轭梯度法进行 了研究.根据这一新型的线搜索条件,结合DY共轭梯度法的方向,我们在文中 提出了一个求解非线性无约束优化问题的算法.当搜索方向为下降方向时,给出了算法 的全局收敛性结果及证明过程. 关键词:无约束优化;共轭梯度法;全局收敛;线搜索 中图分类号:0224文献标识码:A 考虑无约束优化问题: minf() z? 其中厂()是R一R的连续可微函数,在解决这一类问题的方法当中,共轭梯度法是一类有效的方法,特别 当很大时,共轭梯度法因无需计算-厂()的二阶导数矩阵,更加显示出它的优越性卜. 一 般的共轭梯度法的迭代格式为 抖l—+乜d(1) 一 g焉 其中事先给定,d是搜索方向,a是由线搜索或由特定的公式计算出的步长因子,常用的线搜索有精确线 搜索,Armijo线搜索,Wolfe线搜索等.为标量,着名的计算公式有 一 一 一 筹 一 (Fletcher—Reeves), (Ploak—Ribiere—Polyak), 其中,g—Vf(x),d代搜索方向.Dai和Yuan在文献E53中利用Wolfe线搜索,证明了DY方法 的全局收敛性.文献Eli给出了如下一种新的线搜索并证明了其是可行的: f(xk+akd)一f(x^)?一llldll(3) g(x+akd)rd?一2mlldll(4) 其中0<』D<<1. 本文给出了在这种线搜索下DY方法的一个新算法,并证明了在这种新的线搜索下DY方法的全局收敛陛. 收稿日期:2005—12—29;修回日期:2006—02—28 作者简介:郑希锋(1981一),女,山东潍坊人,青岛大学理工学院数学系04级研,研究方向为最优化理论与方法. 28青岛大学(自然科学版)第19卷 l假设条件及算法 假设(a)厂(z)在水平集L一{X?R"l厂(z)?f(x.)}上下有界; (b)在L的一个邻域【,内,厂连续可微,且其导数g满足Lipschitz条件:即存在常数L>0使: }g(z)一g()ll?LllX—Yll,VX,Y?U 算法 Step1给定Xl?R",,>0,di一一gi,k:一l; Step2如果llll<,则停止.否则,进行线搜索求得Ot使其满足线搜索(3)(4),Xk4-1 一X+口d; Step3计算麟一,抖1一一g蚪1+1d,k:一是+l,转&Pp2. 2全局收敛性 引理1若假设条件(a)成立,厂(z)为R,l上的严格凸函数,则DY方法产生的搜索方向为下降方向,即 对Vk—l,2,…都有dTg<0. 证明用归纳法证. 当一1时,d1一一g1,有dTg1一一llg1ll<0成立. 假设一k—l时有dL1g卜1<0成立,下证对一k有dTg<0成立.由厂(z)是严格凸函数知:(z — z卜1)(一g卜1)>0,即口卜1}1(gk—g卜1)>0也即: }1(gk—g卜1)>0 则有 dTg—g(一+flkd~-1)一一ll+g卜一一ll+g卜 一—gL1d卜1<0(5)alL ,(gk—g卜1)一,… 即对于—k的情况定理也成立.证毕. 引理2[若假设(a),(b)成立,考虑一般方法z蚪1一X+口d,其中d是下降方向,口由线搜索(3), (4)得到,则有<?. 证明过程见文献[1]. 定理:设目标函数厂(z)满足假设(a),(b),且厂(z)为R,l上的严格凸函数,考虑方法 (1),(2),其中 一—, 步长.由线搜索(3),(4)给出,则或者g一0对某个k成立,或者有iminfllll一0. 1(gk—g一1o. 证明I利用反证法.假设定理不成立,则存在C>0,使得 llll?C,k—l,2,…(6) 由d一一g+flkd~1可得 +gk—Adk-i(7) 对(7)式两边取模平方并移项可得: lldll一ll卜1ll一2g—llll(8) 由(5)式可知 一llll一g d}1(一g卜1)gL1d卜1 将此式带入(8)式并两边除以(g)可得 !!尘一!!一一!!' 一 — (gTid—k_ i)2一一 第1期郑希锋,等:一种线搜索下DY共轭梯度法的全局收敛性29 由于k一1时有 一一 c+ 则对(9)式依次递推可得 ?+ 由假设可知 所以有 lld.JJ (grd1) gJJ?+ ^ ?一 1 击g?IIII llgJJ一 IIgII g1 ? d?三 kJJJJ,/ 则有 (g^) 台JJ}J=C). 这与引理2矛盾,故假设错误,定理成立,全局收敛性得证. 3结论 + gJJ gII k ?i一1 (9) 该文研究了一种新型线搜索条件下的DY非线性共轭梯度法,证明了提出的算法 是全局收敛的,在理论 上推广了DY非线性共轭梯度法. 参考文献: [1]WangChangyu,DuShouqiang,ChenYuanyuamGlobalCovergencePropertiesofThree- TermConjugateGradientMeth— odwithNew-typeLineSearch[J].JournalofSystemsScienceandComplexity,2004,17(3):4 12—420. [2]DaiYuhong,HanJiYe,LiuGuanghui,etc.ConvergencePropertiesofNonlinearConjugateGradientMethods[J].SIAM JournalofOptimization,2000,10:345—358. [3]王长钰,张玉 忠.GlobalConvergencePropertiesofS-RelatedConjugateGradientMethods[J].科学通 报,1998,43: 1959—1965. [4]戴志锋,陈兰平.一种混合的HS-DY共轭梯度法[J].计算数学,2005,4:429—436. [53DaiYuhong,YuanYaxiang.ANonlinearConjugateGradientwithaStrongGlobalConvergenceProperty[J].SIAM JournalofOptimization,2000,10:177—182. GlobalConvergencePropertiesofDYConjugate GradientMethodWithaNewLineSearch ZHENGXi—feng,TIANZhi—yuan,DUShou—qiang,WANGYan (DepartmentofMathematics.CollegeofScience,QingdaoUniversity,Qingdao266071,China) Abstract:TheDYnonlinearconjugategradientmethodwithanewtypelinesearchispresented.Anewal— gorithmwiththenewtypelinesearchandDYmethodisgiven.Theglobalconvergenceofthenewalgo— rithmiSobtainedwhenthesearchdirectioniSdescent. Keywords:unconstrainedoptimization;coniugategradientmethod;globalconvergence;linesearch + 一