李倩

【摘要】本文通过构造含有双参数的公式βk，提出了一个新的共轭梯度算法.该法具有充分下降性，与所选用的搜索准则及目标函数f凸性均无关，在强Wolfe线搜索下给出该算法具有全局收敛性.

【关键词】无约束优化;共轭梯度法;全局收敛性

【分类号】AMS（1991）49M，90C45

【中图分类号】O221.1 【文献标识码】A

1.引 言

考虑无约束优化问题：

minf（x），x∈Rn，其中f： Rn→R1，f∈C1.

构造迭代算法 xk+1=xk+αkdk，其中dk为搜索方向，αk为搜索步长.对αk和dk的不同选择就构成了不同的算法.60年代Fletecher等人提出一种共轭梯度算法，其基本结构是：dk=-gk+βkdk-1，当βk选择不同的公式时就得到不同的共轭梯度算法.几个代表性的公式是：

βHSk=gTk（gk-gk-1）dTk-1（gk-gk-1），βFRk=‖gk‖2‖gk-1‖2，

βPRk=gTk（gk-gk-1）‖gk-1‖2，

βCDk=-‖gk‖2gTk-1dk-1，

βLSk=-gTk（gk-gk-1）dTk-1gk-1，βDYk=‖gk‖2dTk-1（gk-gk-1）.

这些公式分别在文献[1-3]给出，这些方法的收敛性在文献[1-2，4-6]中已经给出.

共轭梯度法适于求解大规模无约束优化问题.

2.算法与性质

本文总假设目标函数满足以下假设：

假设（a）水平集L1=x∈Rnf（x）≤f（x0）有下界，其中x0为初始点;

（b） 在水平集L1的一个邻域U内，f连续可微，其导数函数g满足Lipschitz条件，即存在常数L>0，使：‖g（x）-g（y）‖≤L‖x-y‖，x，y∈U.

本文步长αk由强Wolfe准则得到：

f（xk+αkdk）≤f（xk）+δαkgTkdk，（1）

gTkdk-1≤-σgTk-1dk-1，（2）

其中0<δ<σ<1.

求解无约束优化问题的共轭梯度算法：

Step 1 选一个初始点x0∈Rn，ε∈（0，1），λ1≥0，λ2≥0，置d0=-g0=-

c2=1+λ11-σσ1-λ2σ，有：c1≥0，c2≥0，

则：c1≤-gTkdk‖gk‖2≤c2.（4）

3.全局收敛性证明

定理2 设序列gk，dk 由以上算法产生，步长αk由强Wolfe准则得到，设λ1<σ1-σ，0≤λ2<12σ，σ<12，目标函数f满足假设（a）和假设（b），则对算法产生的迭代点列有：limk→∞inf‖gk‖=0.

证明：由引理1和（4）式，我们有：

∑∞k=0‖gk‖4‖dk‖2<+∞.（5）

令 tk=‖dk‖2‖gk‖4，（5）式可写为：∑∞k=01tk<+∞.

用反证法，假设定理2不成立，那么存在一个常数γ>0，使

‖gk‖≥γ，由dk=-gk+βkdk-1 两边平方取模并除以‖gk‖4得：

‖dk‖2‖gk‖4=1‖gk‖2-2βkgTkdk-1‖gk‖4+（βk‖dk‖）2‖gk‖4，

tk≤1‖gk‖2+2gTkdk-1‖gk‖2‖gk-1‖2+‖dk-1‖2‖gk-1‖4=tk-1+1‖gk‖21+2gTkdk-1‖gk-1‖2≤tk-1+1‖gk‖21+2σgTk-1dk-1‖gk-1‖2≤tk-1+1‖gk‖2（1+2σ·max（c1，c2）），

tk≤1+2σ·max（c1，c2）∑ki=01‖gk‖2≤[1+2σ·max（c1，c2）]k+1γ2，

于是有：∑∞k=01tk=+∞，矛盾.所以有：limk→∞inf‖gk‖=0.

【参考文献】

[1]Hestenese M R，Stiefel E.Method of conjugate gradient for solving linear equations[J].J Res Nat Bur Stand，1952，49：409-436.

[2]Polak E，Ribigravere G.Note sur la convergence de directions conjug Rev[J].Francaise Informat Recherche Operationelle，1969，16：35-43.

[3]Polyak BT.The conjugate gradient method in extreme problems[J].UUSR Comput Math and Math Phys，1969，9：94-112.

[4]Fletcher R.Practial method of optimization[M].2nd edtition.New York：Wiley，1997.

[5]Liu Y，Storey C.Efficient generalized conjugate gradient algorithms[J].Journal of Optiimization Theory and Appplication，1992，69：129-137.