非精确线搜索条件下共轭梯度法的收敛性分析

鞠静洁，庞德艳，杜守强

（青岛大学 数学科学学院，山东 青岛 266071）

0 引言

讨论无约束最优化问题

其中f为RN上的可微函数.本文中‖·‖为欧几里得范数.

共轭梯度法自创立以来就被广泛应用于解无约束最优化问题，是求解大规模无约束优化问题的一种很有效的方法［1－11］，原因在于它在计算过程中只需要目标函数值和梯度函数值，不需要矩阵存储，却比最速下降法有更好的数值效果，如由Hideaki与Yasushi提出的使用目标函数值的共轭梯度法.

传统的求解问题（1）的共轭梯度法的迭代公式为

其中gk＝▽f（xk），αk＞0是步长，dk是搜索方向，βk是一个参数.

本文将介绍两种改进的共轭梯度法，它们的步长都是由一种新的Wolfe线搜索方法［5］

与

本文结构为：在第1、2部分中将分别给出在新的Wolfe型线搜索条件下的两种算法，并详细介绍其收敛性质；第3部分给出这两种算法在其它的非精确线搜索条件下的一些讨论；最后，分别给出这几种算法的数值实例以说明它们的有效性.

1 算法Ⅰ及其收敛性分析

算法Ⅰ

步骤0：选取初始点x1∈RN，给定参数0＜ρ＜，0＜σ＜1且ρ＜σ，容许误差0＜ε≪1，令d1＝－g1，k＝1.

步骤1：给定xk，dk∈RN，计算满足不等式（4），（5）的αk＞0.由（2）式计算xk＋1∈RN.

步骤2：若gk＋1＝0，停止.否则转第3步.

步骤3：由（6）式计算βk＋1∈R，计算搜索方向

步骤4：令k＝k＋1.转到步骤1.

为了建立算法Ⅰ的全局收敛性，先给出如下假设及引理.

假设1 A1）f：RN→R在水平集Γ＝｛x∈RN：f（x）≤f（x1）｝中有下界，x1∈RN为初始点.A2）▽f：RN→RN在Γ的某个邻域N中是Lipsichitz连续的，即存在L＞0满足

引理1 若假设1成立，则Wolfe型线搜索方法（4）和（5）可行.

引理1的证明见文献［5］.

引理2 算法Ⅰ中的序列（dk）k∈N满足下降条件，即gkTdk＜0（k∈N）.

证 显然d＝－g∈RN满足gTd＜0.设gTd ＜0对任意n∈N成立，则由不等式（4）知1111nn

若gTn＋1dn≤0，则

因此，由归纳法可知gTkdk＜0（k∈N）.

引理3 设假设1成立，并结合等式（2）的任意方法，这里αk满足不等式（4），（5），则

证 由线搜索（4），（5）及假设1可知（2σ＋L）αk‖dk‖2≥－gTkdk，从而有

对上式两边同时平方可得

由（4）式可知

引理得证.

由假设1和引理3可推出如下引理.

引理4 设假设1成立，且βk满足

则由等式（2）和（3）产生的（xk）k∈N在稳定点停止或者在收敛点停止，即

证 若‖gk0‖＝0（k0∈N），则立即可得结果.考虑‖gk‖≠0（k∈N）的情形.由等式（3），有

从而

因此，对于∀k∈N，有

从而有

假设存在c1＞0，对∀k∈N，有‖gk‖≥c1，则可得

这证明了

定理1 设假设1成立，则算法Ⅰ在一个稳定点停止或者收敛，即

证 不等式（4）和引理2说明对∀k∈N，有

因此可得βk＞0（∀k∈N）.再由引理2，对∀k∈N，有

搜索方向的定义及（6）式保证了

因此，对∀k∈N，有

这确保了（βk＋1）k≥1满足引理4中的条件.因此算法Ⅰ全局收敛.

2 算法Ⅱ及其收敛性分析

算法Ⅱ

步骤0：选取初始点x1∈RN，给定参数，容许误差0＜ε≪1，令d1＝－g1，k＝1.

步骤1：给定xk，dk∈RN，由不等式（4），（5）计算步长αk＞0.由（2）式计算xk＋1∈RN.

步骤2：若gk＋1＝0，停止.否则转第3步.

步骤3：由（7）式计算βk＋1∈R，再由（8）计算搜索方向dk＋1.

步骤4：令k＝k＋1.转到步骤1.

同算法Ⅰ一样，在给出算法Ⅱ的全局收敛性之前先给出一些假设与性质.

假设2 A3）水平集Γ⊂RN在初始点有界.

引理5［7］结合等式（2），（3）的方法，设γ＞0，且对任意k∈N，存在，使得γ≤‖gk‖≤.若b＞1，且存在λ＞0，使得｜β｜≤b，且‖s‖≤λ（s＝x－x），则｜β｜≤.kkkk＋1kk

由引理5可以推出如下定理.

定理2 结合（2），（3）的方法，同时

i）对∀k∈N，βk≥0；

ii）假设1和假设2及引理5都满足；

iii）（dk）k∈N满足充分下降条件，则全局收敛到问题（1）的稳定点或者至少存在一个聚点是问题（1）的稳定点.

定理3 在假设1和引理5的条件下，设算法Ⅱ中的（dk）k∈N满足充分下降条件，则算法Ⅱ在一个稳定点停止或收敛，即

证 由（7）式可知，对∀k∈N，βk≥0，只需证算法满足引理5即可.

不等式（4），（5）及定理2中的条件确保了∃c＞0，使得对∀k∈N，有

另一方面，假设2确保了∃M1，＞0使得‖sk‖≤M1，且‖gk‖≤（k∈N）.因此，有

假设∃M＞0，满足‖gk＋1‖≥M（k∈N），有，并令.若‖sk‖≤λ（∀k∈N），由不等式（9）可知，对∀k∈N，有

这证明引理5是满足的，因此定理3确保了算法Ⅱ的全局收敛性.

3 讨论

除了由（4），（5）定义的线搜索方法以外，还有许多种非精确线搜索方法可以应用于这两种新的共轭梯度算法中，如

其中0＜δ＜σ＜1，0＜γ＜1.

下面将给出使用由（10），（11）定义的线搜索方法的两种新的共轭梯度算法.

3.1 算法Ⅲ

步骤0：选取初始点x1∈RN，给定参数0＜δ＜σ＜1，0＜γ＜1，容许误差0＜ε≪1，令d1＝－g1，k＝1.

步骤1：给定xk，dk∈RN，计算满足（10），（11）的αk＞0.由（2）式计算xk＋1∈RN.

步骤2：若gk＋1＝0，停止.否则转第3步.

步骤3：由（6）式计算βk＋1∈R，由（8）式计算搜索方向dk＋1.步骤4：令k＝k＋1.转到步骤1.

3.2 算法Ⅳ

步骤0：选取初始点x1∈RN，给定参数0＜δ＜σ＜1，0＜γ＜1，容许误差0＜ε≪1，令d1＝－g1，k＝1.

步骤1：给定xk，dk∈RN，由不等式（10），（11）计算步长αk＞0.由（2）式计算xk＋1∈RN.

步骤2：若gk＋1＝0，停止.否则转第3步.

步骤3：由（7）式计算βk＋1∈R，再由（8）式计算搜索方向dk＋1.

步骤4：令k＝k＋1.转到步骤1.

4 数值试验

分别给出算法Ⅰ，Ⅱ，Ⅲ，Ⅳ的一些数值试验结果，比较它们的性能.从CUTE测试函数库中选择了无约束优化问题完成本次试验.表1中列出了本次数值实验的测试问题及结果，其中Problem表示测试问题的名称，NI为迭代次数，NF为函数值计算次数，NG为梯度值计算次数，g为最终得到的梯度的范数.所有算法均采用 Matlab编程，在程序中参数设置为：ρ＝0.4，δ＝0.5，σ＝0.6，γ＝0.8，且ε＝10－4.

表1 算法Ⅰ，Ⅱ，Ⅲ，Ⅳ的数值结果Tab.1 The numerical results of the Algorithm Ⅰ，Ⅱ，Ⅲ，Ⅳ

由表1可知，算法Ⅰ，Ⅱ，Ⅲ，Ⅳ在不同的函数上性能表现有很大差异.因此，并没有一种算法适应于所有的函数.对于不同的函数应该进行大量的实验以找出最适合函数自身的一种或几种算法.因此，对于共轭梯度算法进行全面的研究是很有必要的.

［1］Yuan Yaxiang.Analysis on the conjugate gradient method［J］.Optim Methods softw，1993，2（1）：19.

［2］Yu Gaohang，Zhao Yalin，Wei Zengxin.A descent nonlinear conjugate gradient method for large－scale unconstrained optimization［J］.Appl Math Comput，2007，187（2）：636.

［3］Dai Yuhong，Yuan Yaxiang.A nonlinear conjugate gradient method with a strong global convergence property［J］.SIAM J Optim，1999，10（1）：177.

［4］Dai Yuhong.Further insight into the convergence of the Fletcher－Reeves method［J］.Sci China：Ser A，1999，42（9）：905.

［5］Du Shouqiang，Chen Yuanyuan.Global convergence of a modified spectral FR conjugate gradient method［J］.Appl Math Comput，2008，202（2）：766.

［6］Hideaki I，Yasushi N.Conjugate gradient methods using value of objective function for unconstrained optimization［J］.Optim Lett，2012，6（5）：914.

［7］Gilbert J C，Nocedal J.Global convergence properties of conjugate gradient method for optimization［J］.SIAM J Optim，1992，2（1）：21.

［8］马昌凤.最优化方法及其 Matlab程序设计［M］.北京：科学出版社，2010：47.

［9］张秀军，徐安农.一种新的非线性共轭梯度法的全局收敛性［J］.广西科学，2005，12（4）：283.

［10］李敏，屈爱平.一种充分下降的PRP共轭梯度法的全局收敛性［J］.高等学校计算数学学报，2013，35（2）：148.

［11］Qian Weiyi，Cui Haijuan.A new method with sufficient sescent property for unconstrained optimization［J］.Abstr Appl Anal，to be published.