线搜索（LS）共轭梯度法非单调算法的全局收敛性

线搜索（LS）共轭梯度法非单调算法的全局收敛性 线搜索(LS)共轭梯度法非单调算法的全局 收敛性 第24卷第2期 2007年6月 上海第二工业大学 JOURNALOFSHANGHAISECONDPOIYTECHNICUNIVERSITY ,,01.24No.2 Jun.2007 文章编号:1001.4543(2007)01.0098-05 线搜索(LS)共轭梯度法非单调算法的全局收敛性 陈茜,桂胜华2 (1.同济大学应用数学系,上海200092;2.上海第二工业大学理学院,上海201029) 摘要:非单调线搜索技巧在非线性优化中得到成功的应用与扩展,非单调线搜索下的共轭梯度法则可以提高大规 模非线性优化问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的收敛速度.对LS共轭梯度法做了某些变型,在非单调线搜索下,该方法保证每次迭带都会产 生下降的方向,在较弱的条件下得到算法全局收敛性. 关键词:非单调线搜索;全局收敛性;修正LS算法;无约束优化 中图分类号:0221.2文献标识码:A 0引言 考虑尢约束优化I_口J越 minf(z),z?R(1) 其中f:R"一R是连续可微函数,g=vf(z) 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示它的梯度函数.我们用迭代方法求解问题(1)的共轭梯 度方法有下述迭代格式: 『-.gk,k=0, === 1+_l'七12 z+1=z+0(3) 其中为参量,步长Q>0通过一维线搜索得到,如Wolfe线搜索?,Armijo线搜索等.有关的公式如 下: [3】 "s===gkTyk- 1 川一l2[4】'一 [5,6】 === 等 收稿日期:2006.07.18;修回日期:2007.01.20 作者简介:陈茜(1982一),女,硕士,主要研究领域为非线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 . 基金项目:上海市教委科研基金项目(No.05RZ12) 第24卷陈茜,桂胜华:线搜索(Ls)共轭梯度法非单调算法的合局收敛性99 DY一 0 /ak—dk_lTy一 l 其中I1"0表示Euclidean范数,Yk一1=gk—gk一1. 非单调算法是解决大规模的非线性问题,尤其是病态问题的一类非常有效的方法.在文献【lO】中,Gnppo, Lampariello及Lucidi引入一类非单调牛顿方法并 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了其收敛性.非单调算法通过非单调线搜索策略得到 非单调性.数值结果表明,运用非单调线搜索策略可以提高算法的收敛效率.然而,在非线性共轭梯度法 中,若要应用非单调线搜索技巧,比较困难的方面是搜索方向可能会不满足充分下 降条件: dk一c0 其中C>0为一常数,且k1. 由文献【11】对PRP算法的修正想到对LS算法进一步修正,使其具有好的性质, 于是在 dk=一g+dk一1的基础上构造新的,使其有充分下降性.本文将非单调线搜索应用 于这一修正的Ls 算法,在一定的假设下得到全局收敛性. ,我们给出了非单调修正LS的算法及 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 中必要的假设条本文结构如下:第2节 件;在第3节中,我们 给出了全局收敛性的证明. 1算法及假设条件 考察如下非单调Armijo线搜索 0<<,?(0,1),P?(0,1),M为一给定正整数,在第k次迭代中,给定?(,),步长 =maxf,hk=0,1,2…),满足 f(Xk+akdk)0<m<am x () ,(?一J)+Pakgkdk(4) 其中m(0)=0,0m(k)min[m(k一1)+1,M],k1. 我们修正的如下 『--gk,k=0, === 1一+Lsl_1+一1,1(5) 其中 = ffkTyk- 1 , = ffk'rdk_l(6) 由(5)式及(6)式得 dk=一0 因此搜索方向具有充分下降性. 为讨论方便我们给出如下算法. 算法 步骤0给出起始点X0,0<<,?(0,1),P?(0,1),,>0,正整数,令k:=0; 步骤1计算g,如果I0,停止; 步骤2由(5)式计算; 步骤3计算Q使其满足(4)式,令Xk+1=Xk+dk,k:=k+1,转步骤1. 1oo上海第二工业大学2007年第2期 为得到全局收敛性,我们假设函数,满足下面的假设条件(H): (H1)水平集={?R:,()f(Xo))有界; (H)在L的某一邻域?内,f一阶连续可微,其梯度函数9()是Lipschitz连续的,即存在一个常数P, 使得 IIg()一g(y)lIPIIx一0,V,?? 由此假设条件可知,存在一常量>0,使得 IIg()0,Vx?N 2全局收敛性 为简便起见,我们引入下面的记号: )=max{ilO七一m(f(zi)=m<m(ax),(-j)) 即 k—m(k)f(k)k 引理1若,满足假设(H),dE由(5)式得到,O:k满足(4)式,令=Pakgkdk,则序列{,(c)))单调 递减 ,((+1))f(Xt(k—M))+Q(k+D一1 进而 一 limQ(k+D一1=0 — ?.o 证明由(4)式,我们有 f(Xk+1)f(Xt(k))+(7) 因 所以不等式 =p=一paIIg<0 f(Xk+1),(勋()) 对所有的都成立. 又 m(k)m(k一1)+1, 所以,我们有 ,())<m(ma?x)+1f(Xk—J)=max{._1),(+J),f(Xk)j:== max{f(x,(H)),f(Xk))=,(勋(H)),k=1…2??; 因此,序列{,(()))单调递减. 因f(Xl(1)1=f(x1),所以 f(Xk),(勋(一1))…f(X/(1))=f(X1) 因 f(七+1)一1k+1一m(k+1)一1k—M 第24卷陈茜,桂胜华:线搜索(LS)共轭梯度法非单调算法的合局收敛性101 所以 所以 因此 由此式及(7)式得 由假设条件(H1),即得 因 .厂((+1)).厂((一)) f(xl(k+1))f(xz(z(k+1)一1))+(+1)一1 .厂(f(一))+(+1)一1 0"---~Z(k+1)一 1.厂((一))一f(xl(a+1)) aim(+1)一1=0 g---~O0 +1)一1gl(k+1)-ITdz(七+1)一 (七+1)一1=paj(七 1=一paj(七+1)一1I]gz(七+1)一102 ()_l卜1II=0 定理2若,满足假设(H),dk由(5)式得到,满足(4)式,.[].是算法产生的序列,则有 li.minfIIgk0=0 证明假设(9)式不成立,则存在常数r>0,使得 II0r,Vk=1,2,… 由(8)式可知,若li, minf>0,则li,minfllgk0=0,这与假设矛盾. 若li. minf=0,则存在无限子集,满足 1. i— mQ=0 K七? 则由(4)式对任一k?K有 f(xk+(/dk)>m<a啡x),(J)一p(~k/)IIdkII f(Xk)一JD(/)Ildkll 再由中值定理,对充分大的k?K,存在常数?(0,1),使得 f(xk+(Q/))一f(xk)=(Q/)9(+(Q/))= (Q/o")gkdk+(Q/)【9(+(Q/a)dk)一9()]_Idk (ak/a)gkdk+P(Q/)I 由此式及(11)式得 IIgkII(+JD)(/)0 又因(10)式,liminfIIgk0=0,这与假设矛盾.所以liminfIIg0=0,全局收敛性得证. (8) (9) (10) (11) 102上海第二工业大学2007年第2期 参考文献: 【1】WOLFEPConvergenceconditionsforascentmethods【J】.SIAMReview,969,11:226-235. 【2】 ARMIJOL.Minimizationoffunctionshavinglipsehitzcontinuousfwstpartialderivatives 【J】.PacificJournalofMathematics,1966,16:1-3. [3】 HESTENESMR,STIEFELE.Methodofconjugategradientforsolvinglinearequations[J】 .J.Res.Nat.Bur.Standards,1952,49:409—436. [4]FLETCHERR,REEVESC.Functionminimizationbyconjugategradients【J】.Comput.J.,1964,7:149—154. 【5】 POLYAKBT.Theconjugategradientmethodinextremeproblems[J】.U.S.S.R.Comput.M ath.Phys.,1969,9:94—112. [6】 6POLAKE,RIBIEREGNotesurlaconvergencededirectionsconjugees[J]Rev.FrancaiseI nformatRechercheOperationelle,3eAnnUl,1969, 16:35-43. 【7】FLETCHERR.PracticalMethodofOptimization【M】.2ndEdition,NewYork:Wiley,1987. 【8】8LIUSTOREYC.Efficientgeneralizedconjugategradientalgorithms【J】.J.Optim.TheoryApp1.,1991,69:129—137. 【9】 DAIYH,YUANYAnonlinearconjugategradientmethodswithastrongglobalconvergenceproperty【J】-SIAMJournalonOptimization,1999, 10:177-182. 【10]GRIPPOL,LAMPAR正 LLOLUCIDIS.Anonmonotonelinesearchtechniquefornewton'smethod【J】 _SIAMJournalonNumericalAnalysis, 1986,23:707-716. [I1】易芳.一类非单调修正PRP算法的全局收敛性.[J】经济数学,2006,23(1):99— 103. GlobalConvergenceofLineSearch(LS)ConjugateGradientAlgorithm,)I,ith NonmonotoneTechnique CHENQian,GUISheng.hua (1.DepartmentofAppliedMathematics,TongjiUniversity,Shanghai200092,P.R.China: 2.SchoolofScience,ShanghaiSecondPolytechnicUniversity,Shanghai201029,P.R.China) Abstract:Thetechniqueofnonmonotonelinesearchhasreceivedmanysuccessfulapplicationsandextensionsinthenonlinear optimizationandthespeedofconvergenceofconjugategradientmethodsundernonmonotonelinesearch.Change.TheLSconjugate gradientmethodwaschangedinthispaper,inwhichthetechniqueofnonmonotonelinesearchisused.Undermildassumption,the globalconvergenceofthemethodwasproved. Keywords:nonmonotonelinesearch;globalconvergence~modifiedLSalgorithm;unconstrainedoptimization