| 标题 | 一个充分下降的修正PRP共轭梯度法 |
| 范文 | 陈孔群 张雁 胡乔乔 陈碧玉 摘要：本文对PRP共轭梯度法参数公式进行修正得到一个新公式，以新公式为方向调控参数产生新的搜索方向，并得到一个新算法。不论采用何种线搜索条件产生步长，均可证明由算法产生的迭代方向每步均自动满足充分下降条件，且证明了新算法的全局收敛性.最后的数值结果表明新算法是有效的。 关键词：无约束优化；Wolfe非精确线搜索；共轭梯度法；充分下降；全局收敛 共轭梯度法是求解大规模优化问题最有效的方法之一。本文考虑用共轭梯度法解决如下无约束优化问题： minx∈Rnf（x） 其中f：Rn→R为一阶连续可微函数.共轭梯度法的迭代公式的一般形式为： xk+1=xk+αkdk，（1） dk=gk，k=1， gk+βkdk1，k2，（2） 其中gk= SymbolQC@ f（xk），αk是搜索步长，通常由非精确线搜索产生。βk为方向调控参数，dk为线搜索方向，通常由βk产生。通常由不同参数产生的搜索方向即称为不同的共轭梯度法，著名的有代表性的共轭梯度法（统称为经典共轭梯度法）包括HS方法，FR方法，PRP方法和DY方法，记yk=gkgk1，则它们的参数公式分别为： βHSk=gTkyk1dTk1yk1，βFRk=‖gk‖2‖gk1‖2，βPRPk=gTkyk1‖gk1‖2，βDYk=‖gk‖2dTk1yk1。 近二十多年来，以上四个共轭梯度法的收敛性以及数值性质已被广泛研究，并在此基础上提出了很多理论性质和数值表现均优良的新型共轭梯度法，文献[1]对FR方法和DY方法进行了改进，得到两个新的βk公式： βMFRk=‖gk‖2max‖gk1‖2，u|gTkdk1|， βMDYk=‖gk‖2maxdTk1（gkgk1），u|gTkdk1|。 新算法均不依赖任何线搜索条件即可自动产生充分下降方向，在标准Wolfe线搜索条件下证明了算法所产生的点列全局收敛。文[2]将FR公式改进为 βNk=gTk（gk‖gk‖‖dk1‖dk1）‖gk1‖2，（3） 显然由（3）式不难得到0 SymbolcB@ βNk SymbolcB@ 2βFRk，基于文献，[12]文[3]将（3）式修正为： βJYJk=‖gk‖2（gTkdk1）2‖dk1‖2‖gk1‖2+ugTkdk1，（4） 借鉴文[1，2，3]的思想，我们将（4）式作进一步修正，得到如下新公式： βCZHCk=‖gk‖2gTkdk1‖dk1‖‖gk1‖gTkgk1μ·max‖gk1‖2，gTkdk1μ>2（5） 本文第二部分由公式（5）产生新的搜索方向并建立新算法，并证明算法自动满足充分下降条件；第三部分在常规假设和Wolfe线搜索条件证明算法是弱敛性的；第四部分用迭代时间和迭代次数报告算法的数值测试结果。 1算法CZHC及其性质 算法CZHC 步骤0取初始值x1∈Rn，ε>0，0<δ<σ<1，d1=g1，k：=k+1。 步骤1若‖gk‖<ε，则停止。否则，由某一个非精确线搜索求得步长αk。 步骤2令xk+1=xk+αkdk，由式（5）计算βCZHCk，dk+1=gk+βCZHCkdk，k：=k+1，返回步骤1。 下面证明由算法CZHC所产生的搜索方向自动满足充分下降条件。 引理1对于任意的k1，设搜索方向dk由算法CZHC产生，则有gTkdk SymbolcB@ 12μ‖gk‖2μ>2成立。 证明：用数学归纳法。当k=1时，gT1d1=‖g1‖2 SymbolcB@ （12μ）‖g1‖2，引理1结论成立。假设k1的情形，gTk1dk1 SymbolcB@ （12μ）‖gk1‖2成立。 下面分两种情况证明当k的情形，引理1结论也成立。设gTk，dk1的夹角为θk，gTk，gk1的夹角为νk，则 gTkdk1=‖gk‖·‖dk1‖·cosθk，gTkgk1=‖gk‖·‖gk1‖cosνk。 由式（2）和（5），得 gTkdk=‖gTk‖2+gTkβCZHCkdk1=‖gk‖2+‖gk‖2（1cosθkcosνk）μmax{‖gk1‖2，|gTkdk1|}gTkdk1 1）当gTkdk1=0时，有 gTkdk=‖gk‖2+‖gk‖2（1cosθkcosνk）μmax{‖gk1‖2，|gTkdk1|}gTkdk1 =‖gk‖2 SymbolcB@ （12μ）‖gk‖2 2）當gTkdk1≠0时，有 gTkdk=‖gk‖2+‖gk‖2（1cosθkcosνk）μmax‖gk1‖2，|gTkdk1|gTkdk1 SymbolcB@ ‖gk‖2+2‖gk‖2μ|gTkdk1||gTkdk1| =（12μ）‖gk‖2 综上所述，对于k1，有gTkdk SymbolcB@ （12μ）‖gk‖2成立。即引理1得证。 2算法的全局收敛性 本文将采用标准Wolfe非精确线搜索条件求步长，即αk满足 fxk+αkdk SymbolcB@ fxk+δαkgTkdk，（6） gxk+αkdkTdkσgTkdk。（7） 为了证明新算法的全局收敛性，我们需要用到两个基本假设条件。[4] （H1）目标函数f（x）在水平集Λ={x∈Rn|f（x） SymbolcB@ f（x1）}上有下界，其中x1为初始点。 （H2）目标函数f（x）在水平面集Λ的一个邻域U内可微，且其梯度函数.g（x）= SymbolQC@ f（x）满足Lipschitz连续条件，即存在常数L>0，使‖g（x）g（y）‖ SymbolcB@ L‖xy‖，x，y∈U。 下面的引理是著名的Zoutendijk条件，在算法全局收敛性分析中起着十分重要的作用。 引理2。若假设（H1）和（H2）成立，考虑迭代，其中方向dk满足gTkdk<0，αk满足标准Wolfe非精确线性搜索准则（6）（7），则∑ SymboleB@ k=1（gTkdk）2‖dk‖2< SymboleB@ 。特别地，若dk满足充分下降条件，则有∑ SymboleB@ k=1‖gk‖4‖dk‖2< SymboleB@ 基于引理1，引理2，我們不难得到算法CZHC的全局收敛性结论。 定理1设目标函数满足（H1）（H2），xk由算法CZHC产生，其中步长αk满足弱Wolfe条件（6）（7），则有limk→ SymboleB@ inf‖gk‖=0。 证明：用反证法，假设定理1不成立。注意到‖gk‖>0，易知存在常数γ>0，使得‖gk‖2γ，k。由式（2）得dk+gk=βCZHCkdk1，移项再两边平方后得： ‖dk‖2=‖gk‖22βCZHCkgTkdk+（βCZHCk）2‖dk1‖2，（8） 又由式（5）可知 2βCZHCkgTkdk1 SymbolcB@ 2βCZHCk·gTkdk1 SymbolcB@ 4‖gk‖2μ和 βCZHCk SymbolcB@ ‖gk‖2‖gk1‖2。 于是由（8）式得 ‖dk‖2 SymbolcB@ 1+4μ‖gk‖2+‖gk‖4‖gk1‖4‖dk1‖2， 两边同时除以‖gk‖4有 ‖dk‖2‖gk‖4 SymbolcB@ 1+4μ1‖gk‖2+‖dk1‖2‖gk1‖4。 又‖d1‖2=‖g1‖2，‖gk‖2>γ，于是有 ‖dk‖2‖gk‖4 SymbolcB@ 1+4μ∑ki=11‖gi‖2 SymbolcB@ μ+4μγk， 因此‖gk‖4‖dk‖2μγ（μ+4）k，由此可知∑ SymboleB@ k=1‖gk‖4‖dk‖2= SymboleB@ ，这与引理2矛盾，证毕。 3数值实验 本节我们测试算法CZHC的数值效果，并与PRP+方法，AN方法和HZ方法进行比较。所有测试问题、算例和方法均采用弱Wolfe线搜索准则（6）（7）求步长，运行环境为Matlab2007，Pentium（R）DualCoreCPUT44001.90GHz2.43GB，测试问题部分取自无约束问题集CUTE，维数最大取200000维，有关参数选取如下：σ=0.9，δ=0.01，u=2.1，HZ方法的参数与原文一致。若‖gk‖<106或Itr>2000，则所测试算法运行终止，并记为“F”。 采用Dolan和More的性能图对迭代次数及计算时间进行刻划和报告.从图1图2可知，算法CZHC则明显优于HZ方法、AN方法和PRP+方法，故可以说算法CZHC是有效的。 参考文献： [1]JiangXZ，JianJB.AsufficientdescentDaiYuantypenonlinearconjugategradientmethodforunconstrainedoptimizationproblems，NonlinearDyn.，2013，72，pp.101112. [2]JiangXZ，JianJB.Twomodifiedconjugategradientmethodswithdisturbancefactorsforunconstrainedoptimization[J].NonlinearDynamics，2014，77：387397. [3]简金宝，尹江华，江羡珍.一个充分下降的有效共轭梯度法[J].计算数学，2015，37（4）：415424. [4]江羡珍，简金宝，马国栋.具有充分下降性的两个共轭梯度法.数学学报（中文版），2014，57（2）：365372. 基金项目：大学生创新训练项目—201610606132 作者简介：第一作者陈孔群，玉林师范学院数统学院2014级学生。 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。