2000年5月May2000JOURNALOFENGINEERINGMATHEMATICS文章编号:100523085(2000)0220099206α无约束优化的超记忆梯度算法时贞军(曲阜师范大学运筹学研究所,山东曲阜273165)(大连理工大学应用数学系,辽宁大连116024)摘要提出了一种无约束优化超记忆梯度算法,分析了算法的收敛性,并对算法进行了数值试验,结果表明算法比Armijo搜索下的FR和PR共轭梯度法及Cauchy方法有效,特别适于求解大规模无约束最优化问题。关键词无约束优化,超记忆梯度法,收敛性,数值试验分类号AMS(1991)49M,90C45中图分类号:O221.2文献标识码:A引言1考虑无约束优化问题:minf(x);x∈Rn;其中f:Rn→R1,f∈C1构造迭代算法:(1)(2)其中dk为搜索方向,Αk为搜索步长。对Αk和dk的不同选择就构成了不同的迭代算法。在无约束优化算法中,一般要求dk为下降方向,或者要求gTkdk<0;其中,gk=Vf(xk).若dk=-gk,则算法称为Cauchy方法1。若f(x)二阶连续可微,dk=-2f(xk)-1gk;则算法称为Newton型方法2;其中VV2f(xk)非奇异。若dk=-Hkgk,其中Hk为V尺度方法2。2f(xk)-1的某种近似,这类方法称为拟Newton方法或变α收稿日期:1999206207.基金项目:国家自然科学基金基金项目(19871049);山东省自然科学基金资助项目(Q98A06114)工程数学学报第17卷100前一类算法结构简单,每次迭代的计算工作量小,但其收敛速度慢且易产生拉锯现象,故不是一类理想算法。后两类算法在一定条件下收敛速度较快,但每次迭代的计算工作量较大,不适于求解大规模无约束优化问题。60年代中期,Fletcher等人3dk=-gk+Βkdk-提出一种共轭梯度法,其基本结构是(3)当Βk选取不同的公式时就得到了不同的共轭梯度法4,三个有代表性的公式是ΒFR22(Fletcher-Reeves)(4)k=gk/gk-1;gTk(gk-1]/gk-12;)(Polak2Ribiere)()Βk=Βk=gk-gk-5gTk(gk-1]/[dT)k-1(gk-gk-1);(Hestenes2Stiefel)(6)这类方法适于求解大规模问题,由于共轭梯度法是针对正定二次函数设计的,虽然在精确搜索下具有二次终止性,但对一般非线性目标函数,有些共轭梯度法不具有全局收敛性,有些则数值性能较差5。近年来,文9分析了Beale2Powell重新开始算法的收敛性,所论算法具有很好的数值计算效果,特别适于求解大规模无约束优化问题。本文提出的超记忆梯度法,不需要重新开始,对非线性目标函数不但具有全局收敛性,而且具有良好的数值计算效果。通过与Armijo搜索下FR,PR共轭梯度法及Cauchy方法的比较发现超记忆梯度法具有明显的优越性。本文第2节叙述算法及其性质,第3节分析算法算法及其性质假设(H):水平集L0=超记忆梯度法如下:2{x∈Rnff(x)Φf(x1)}有界。0<Λ2<1;x1∈Rn;k=1;初始步:0<Λ1<1;2第一步:若gk=第二步:0,停!否则转第二步;--gk;k=1dk=其中gk+Βkgk-1;kΕ2∞,bk;ak,bk;ak,∞);(---Ηk=0<0Ηk<Βk∈ΠΗk=Π这里Ηk表示gk和gk-1之间的夹角,而gkak(1-cosΗk)=gk-1,.gkbk(1+cosΗk)=gk-11,1,第三步:xk+1=Αkdk,其中Αk为{1,}中满足下式的最大者,xk+(xk+222f(xk)-Αdk)Ε-Αk‘Λ1‘gTdk;(7)fk第四步:k=k+1转第一步。首先证明算法的两个性质:©1994-2013ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net第2期时贞军:无约束优化的超记忆梯度算法101引理1假设(H)成立,则对Πk有1gT2kdkΦ-2gk()8证明由dk之定义很容易验证(8)式成立,此略。引理2假设(H)成立,若算法产生无穷点列{xk},则gTkdkcos(Ηk)=-gdΕΛ(10)kk其中Ηk为-gk与dk之间的夹角证明由Βk的取法可知下式成立gk4-2Βkgk2(gTgk-1)+Β2[(gTgk-1)2gk2gk-12]Ε0.kkk上式两边同乘以1-Λ2可得Λ2)gk4-2Βgk2(gTgk-1)(1-Λ2)+(1-kΒ22)(gTgk-1)2(1-Λ2)gk2gk-12]Ε0.k[(1-Λk由于1-Λ2<1,1-Λ2>Λ2,从而下式成立Λ2)gk4-2Βgk2(gTgk-1)(1-Λ2)+(1-kΒ2T2222k[(gkgk-1)-Λgkgk-1]Ε0经整理得gk4-2Βkgk2(gTgk-1)+Β2gTgk-1)2ΕΛ2gk2[gk2-k(kk2ΒkgTgk-1Β2gk-12.kk由于gTdk=-gk2+ΒkgTgk-1,dk2=gk2-2ΒkgTgk-1+Β2gk-12,故kkkk(gTdk)2ΕΛ2gk2dk2k由引理1可得-gTdkΕΛgkdk从而(10)式成立。证毕全局收敛性3定理1若假设(H)成立,则算法或有限步终止于问题的稳定点,或产生无穷点列{xk},其任意极限点都是问题的稳定点。若有gk=0,则xk为稳定点,假...