共轭梯度方法是解决大规模无约束优化问题的重要方法，从不同角度来研究共轭梯度法有着重要意义.本文在非单调线搜索技术[1]基础之上，提出的一种新的非单调谱共轭梯度方法，并证明该方法具有充分下降性和全局收敛性.
　　【关键词】Armijo线搜索；无约束最优化；谱共轭梯度法；全局收敛性
　　【中图分类号】O241.5 【文献标识码】A
　　引 言
　　在1998年Barzilai与Borwein[2]提出谱梯度法.在2001年Birgin与Martinez[3]把谱梯度法与共轭梯度法结合提出一类新的谱共轭梯度法.谱共轭梯度法数值试验结果与收敛情况表明，与相应的共轭梯度法相比，谱共轭梯度法更有效[4].
　　对于无约束优化问题
　　minx∈Rnf（x）
　　其中f：Rn→R是连续可微的.
　　本文构造了一种新的谱共轭梯度法：
　　xk 1=xk αkdk，（1）
　　dk=-gk，k=1；-1δkgk βkdk-1，k≥2.（2）
　　βk=δk-1uk（‖gk-gk-1‖2）δk（‖gk‖·‖dk-1‖ dTk-1gk-1），0　　其中
　　δk=sTk-1yk-1‖sk-1‖2，（sk=xk 1-xk，yk=gk 1-gk）（4）
　　在线搜索条件的选择上，在本文中将选择由Grippo等人提出的一种Armijo型的非单调线搜索技术[1]：令β>0，γ∈（0，1），取一正的整数M，并且取步长为αk=βγmk，我们要求mk是满足下面不等式的最小的非整数
　　f（xk βλmkdk）≤max0≤j≤m（k）{fk-1} σβγmkgkTdk，（5）
　　其中要求0<σ<1，并且
　　m（0）=0，0≤m（k）≤min{m（k-1） 1，M}.
　　利用Armijo型的非单调线搜索技术构造的谱共轭梯度法的优点在于，数值试验表明该算法具有良好计算效能，也能用于维数较高的无约束优化问题[5-6].本文证明了新算法不仅具有充分下降性，并在Armijo线搜索下具有全局收敛性.
　　1.充分下降性及新的谱共轭梯度算法
　　为了证明充分下降性，我们首先假设：
　　（a）目标函数f（x）在如下水平集中有界，
　　L={x∈Rn|f（x）≤f（x0）}.
　　其中x0为初始点.
　　（b）f在水平集L的开凸集U连续可微，并且它的梯度向量g满足Lipschitz条件，即存在一个常数τ，使得：
　　‖g（x）-g（y）‖≤τ‖x-y‖，x，y∈U
　　根据假设（a）和（b），我们容易知道存在一个常数ν，满足：
　　‖g（x）‖≤ν，x∈L..
　　定理1.1 考虑迭代方法（1）-（4），步长因子ak满足了非单调步长规则（5），
　　βk=δk-1uk（‖gk-gk-1‖）δk（‖gk‖·‖dk‖ dTk-1gk-1），0　　那么存在正常數N，对k≥l，有
　　gTkdk≤-N‖gk‖.
　　证明
　　我们对k分情况考虑如下：
　　（ⅰ）当k=1时，gT1d1=-N‖g1‖<0有，结论显然成立，
　　（ⅱ）当k≥2时，
　　若gTkdk-1=0，则
　　gTkdk=-1δk‖gk‖2<-1T‖gk‖2.
　　结论成立，
　　若gTkdk-1≠0，则
　　gTkdk=-1δk‖gk‖2 βkgTkdk-1
　　=-1δk‖gk‖2 δk-1uk（‖gk-gk-1‖2）δk（‖gk‖·‖dk-1‖ dTk-1gk-1）gTkdk-1≤-1δk‖gk‖2 δk-1uk（‖gk-gk-1‖2）δk‖gk‖·‖dk-1‖‖gk‖·‖dk-1‖=-1δk‖gk‖2 δk-1ukδk（‖gk‖ ‖gk-1‖）2
　　（6）
　　又由于假设（a）跟（b），我们有存在一个常数v，使得
　　‖g（x）‖≤ν，x∈L.
　　故存在rn>0，使得有
　　‖gk-1‖=m‖gk‖.（7）
　　则由（6）和（7）有
　　gTkdk≤-1δk‖gk‖2 δk-1δkμk（1 m）2‖gk‖2
　　=-1δk（1-δk-1μk（1 m）2）‖gk‖2.
　　取μk充分小，存在正常数N0满足k≥1有
　　1-μkδk-1（1 m）2>N0>0.
　　假设0<δk　　-N0δk<-N0T.
　　所以
　　gTkdk≤-1δk（1-δk-1μk（1 m）2）‖gk‖2≤-N0δk‖gk‖2
　　<-N0T‖gk‖2=-N‖gk‖2.
　　其中N=N0T.
　　综上，结论成立，
　　2.算法
　　算法2.1
　　·Step1，给定x1∈Rn，ε>0，d1=-g1，k：=1；
　　·Step2.如果‖gk‖<ε，则停止，否则找至αk满足非单调线搜索条件（5）；
　　·Step3.令xk 1=xk αkdk，若‖gk 1‖≤ε，则停止，否则转Step4；
　　·Step4.由（3）与（ 4）计算βk 1和δk，进而计算dk 1=-1δkgk 1 βk 1dk；
　　·Step5.令k：=k 1，转Step2.
　　3.新算法的全局收敛性
　　引理3.1 算法产生序列{xk}，若对{δk}满足0<ρmin<δk<ρmax，则对k∈N，存在常数H，有 　　‖dk‖≤H‖gk‖.
　　证明 （ⅰ）当k=l时，由于d1=-g1，所以我们有‖d1‖=‖g1‖，结论显然成立，
　　（ⅱ）当k≥2时，由βk的定义和（7）我们有
　　‖dk‖≤1δk‖gk‖ βk‖dk-1‖
　　=1δk‖gk‖ dk-1‖gk-gk-1‖2dk（‖gk‖·‖dk-1‖ |dTk-1gk-1|）‖dk-1‖
　　≤1ρmin‖gk‖ ρmax（1 m）2‖gk‖2ρmin（‖gk‖·‖dk-1‖）‖dk-1‖
　　≤1 ρmax（1 m）2ρmin‖gk‖.
　　设H=1 ρmax（1 m）2ρmin，则结论成立.
　　引理3.2 [7]假设（a）和（b）成立，考虑迭代（1）-（4），为本文算法产生的序列，则有，
　　limk→∞αk‖dk‖=0
　　定理3.3 假设（a）和（b）成立，考虑方法（1）-（2），由式（3）与（4）定义，由单调线搜索条件（5）决定，则有
　　limk→∞inf‖gk‖=0
　　证明 假设结论不成立，那么存在着一个常数c>0，使得
　　‖gk‖2≥c，k=1，2，……
　　如若limk→∞infαk>0，由引理3.2证明的最后，我们知道limk→∞αkgTkdk=0，并且由定理1.1可知limk→∞‖gk‖=0，产生矛盾，
　　如若limk→∞infαk=0，那么一定存在着无穷子列I满足条件：
　　limk→∞，k∈Iαk=0. （8）
　　由αk的定义以及γ∈（0，1），我们有αkγ不满足非单调线搜索（5），也就是：
　　fxk akγdk≥max0≤j≤m（k）{fk-j} σakγgTkdk≥f（xk） σakγgTkdk.（9）
　　由微分中值定理，Lipchitz条件以及引理3.1可知，存在一个常数θ，满足
　　f（xk αkγdk）-f（xk）=αkγgxk θαkγdkTdk
　　=αkγgTkdk αkγgxk θαkγdkTdk-αkγgTkdk
　　=αkγgTkdk αkγgxk θαkγdk-gkTdk
　　≤αkγgTkdk Lθα2kγ2‖dk‖2
　　≤αkγgTkdk Lθα2kγ2H2‖gk‖2 （10）
　　由式（9）、（10），我們知道可以得到对任意的k∈I有
　　akγgTkdk Lθa2kγ2H2‖gk‖2≥σakγgTkdk（11）
　　又由假设（a）与（b），我们容易知道存在一个常数ν，满足：
　　‖g（x）‖≤ν，x∈L
　　整理式（11）我们有
　　（1-σ）akγgTkdk≥-Lθα2kγ2H2‖gk‖2
　　≥-Lθα2kγ2H2ν2（12）
　　由定理1.1，我们知道gTkdk<-N‖gk‖2，由上式我们有
　　‖gk‖2≤LθH2ν2Hγ（1-σ）αk（13）
　　由引理3.2与（13），我们可以得到 limk→∞inf‖gk‖=0.与假设产生矛盾.
　　综上，结论成立.
　　4.结 论
　　本文结合Grippo等人提出的非单调线搜索技术，给出了一种新的非单调谱共轭梯度法，证明了这种方法在不依赖于线搜索条件的情况下，具有着充分的下降性，并且证明新算法具有全局收敛性.
　　【参考文献】
　　[1]孙中波，段复建.一类无约束优化的非单调共轭梯度法[J].河北师范大学学报，38（1）：12–15，2010.
　　[2]莫利柳，洪玲，韦增欣.一类无约束优化问题的非单调谱共轭梯度方法[J].广西科学.