非单调ARMIJO型线搜索下的新谱共轭梯度法

张颖

共轭梯度方法是解决大规模无约束优化问题的重要方法，从不同角度来研究共轭梯度法有着重要意义.本文在非单调线搜索技术[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

‖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].广西科学.