一种修正的LS共轭梯度法
2015-04-24焦佳佳
焦佳佳
考虑无约束优化问题

其中R n是n维欧几里得空间,f:Rn→R是一个连续可微的函数.
众所周知,共轭梯度法是求解该类问题的一种重要方法,它具有如下的迭代格式

其中αk是某种线搜索下的步长,dk满足

其中βk是共轭参数.不同的βk的取法会产生不同的共轭梯度法,常见的βk有如下定义:

对应的方法分别叫做FR(Fletcher-Revees),PRP(Polak-Ribiere-Polyak),HS(Hestenes-Stiefel),LS(Liu-Storey),CD(Conjugate Descent)和DY(Dai-Yuan)共轭梯度法.常用的线搜索有:Wolfe线搜索,强Wolfe线搜索,Armijo-type线搜索等,其中强Wolfe线搜索要求αk满足

与其他共轭梯度法相比,PRP方法的数值表现是目前认为最好的方法之一,但该方法的收敛性不理想.研究发现,PRP方法收敛性不好的原因在于它不具有充分下降性.充分下降性是指,对所有的k,不等式

成立,其中c为常数.此性质在收敛性分析中起着非常重要的作用.因此,许多学者都希望找到数值表现可与PRP相媲美同时性质又比其好的方法.文献[1]将标准的共轭梯度法迭代格式(3)推广为如下谱共轭梯度形式

文献[2]取βk=βkFR,在式(7)下满足gkTdk=-‖gk‖2.本文受这些思想的启发,基于谱共轭梯度法迭代式(7),考虑如下参数

结合强Wolfe线搜索建立新的谱共轭梯度算法,并分析了算法的全局收敛.
NLS算法:
初始步:给定x0∈Rn,ε≥0.令d0=-g0,k=0.
第一步:若 ‖g0‖ ≤ε,则停止;
第二步:求出满足强Wolfe线搜索的步长αk;
第三步:计算xk+1=xk+αkdk,若 ‖gk+1‖ ≤ε,则停止;
第四步:通过式(5),(6),求得dk+1;令k=k+1,转第二步.
为了讨论新算法的全局收敛性,假定目标函数满足如下基本假设:
(A)水平集Ω={x∈Rnf( x)≤f( x0)}有下界,即存在常数a>0,使得 x≤a.
(B)f在水平集Ω的一个邻域Ν内连续可微,且其梯度g满足Lipschitz连续,即存在正的常数……
