Advances in Applied Mathematics
Vol. 09  No. 09 ( 2020 ), Article ID: 37608 , 10 pages
10.12677/AAM.2020.99173

一类修正的共轭梯度法及其数值计算效果

陈秀芳,李锋*

云南师范大学数学学院,云南 昆明

收稿日期:2020年8月19日;录用日期:2020年9月8日;发布日期:2020年9月15日

摘要

给出一个新的 β k C δ k 公式,新的共轭梯度法继承了FR方法的优点,在SWP线搜索下,具备良好的全局收敛性。在WWP线搜索下,给出谱共轭梯度法相应的分析。数值实验表明,本文提出的共轭梯度法数值计算性能更有效。

关键词

谱共轭梯度法,共轭梯度法,SWP线搜索,WWP线搜索,全局收敛性

A Kind of Modified Conjugate Gradient Method and Its Numerical Calculation Effect

Xiufang Chen, Feng Li*

School of Mathematics, Yunnan Normal University, Kunming Yunnan

Received: Aug. 19th, 2020; accepted: Sep. 8th, 2020; published: Sep. 15th, 2020

ABSTRACT

A new formula β k C and δ k is given. The new conjugate gradient method inherits the advantages of the FR method. Under the SWP line search, it should have good global convergence. Under the WWP line search, the corresponding analysis of the spectral conjugate gradient method is given. Numerical experiments show that the numerical calculation performance of the conjugate gradient method proposed in this paper is more effective.

Keywords:Spectral Conjugate Gradient Method, Conjugate Gradient Method, SWP Line Search, WWP Line Search, Global Convergence

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

考虑无约束优化问题:

min { f ( x ) : x n } (1)

其中,函数 f : n 的光滑函数,由于该方法低存储性,易于计算,目前被广泛运用于石油勘探、大气模拟、航天航空和工程优化等领域的求解问题上 [1]。一般地,求解问题(1),需给定初始点 x 0 n ,共轭梯度法由最初的线性优化推广到非线性优化问题上,用于求解大规模无约束优化问题,其早期的迭代公式如下:

x k + 1 = x k + α k d k (2)

α k 为搜索步长, d k 为搜索方向, d k 的定义如下:

d k = { g k ; k = 1 g k + β k d k 1 ; k > 1 (3)

其中, g k = f ( x k ) ,是f在 x k 处的梯度,由(3)式可知,共轭梯度法的两个核心问题分别是步长因子 α k 的计算和搜索方向 d k 的选取,需要寻找合适的步长搜索规则,如弱Wolfe线搜索(WWP)、强Wolfe线搜索(SWP)和推广的Wolfe线搜索,分别如下:

{ f ( x k + α k d k ) f ( x k ) + δ α k g k T d k g k + 1 T d k σ g k T d k

{ f ( x k + α k d k ) f ( x k ) + δ α k g k T d k | g k + 1 T d k | σ | g k T d k |

{ f ( x k + α k d k ) f ( x k ) + δ α k g k T d k σ g k T d k g k + 1 T d k σ 1 g k T d k

0 < δ < σ < 1 σ 1 0 是常数, β k 为共轭参数,常用的 β k 公式 [2] [3] [4] [5] 如下:

β k F R = g k 2 g k 1 2 ( Fletcher-Reeves , 1964 ) β k D Y = g k 2 d k 1 T y k 1 ( DaiYuan , 1999 ) β k P R P = g k T y k 1 g k 1 2 ( Polak-Ribiere-Polyak , 1969 ) β k H S = g k T y k 1 d k 1 T g k 1 ( Hestenses-Stiefel , 1952 ) (4)

其中, · 为Euclidean范数, y k 1 = g k g k 1 ,一般而言,目标函数为严格凸时,PRP方法与HS方法的数值计算效果优于FR方法和DY方法,但收敛性却没有后两种方法好。当目标函数非凸时,即使采用Curry原则选取步长因子,即 α k 为一维函数 Φ k ( α ) = { f ( x k + α d k ) : α > 0 } 的第一个极小点,也无法保证它们全局收敛,以上方法在收敛性分析和数值计算性能上有所差异。近年来,共轭梯度法的许多变种被广泛研究,在一定程度上继承了经典方法的某些特性。2012年,在文献 [6] 的基础上,Dai等 [7] 提出一种新的DPRP方法,分母变成线性组合的形式,其共轭参数 β k D P R P 定义为

β k D P R P = g k 2 g k g k 1 | g k T g k 1 | μ | g k T d k 1 | + g k 1 2 (5)

其中 μ > 1 ,Dai等人首先证明了该方法在不进行任何线搜索的情况下具有充分下降性,其次证明在Wolfe线搜索或Armijo线搜索下的全局收敛性。并把这个结果扩展到HS方法中 [8],也是进行相应的收敛性分析,数值实验结果表明DPRP方法比文献 [6] 中方法更有效。

2019年,景书杰等 [9] 提出一类改进的谱共轭梯度法,新的共轭系数和谱系数公式定义为

β k S N = g k T ( g k 1 g k g k g k 1 d k 1 ) d k 1 2 + μ | g k T d k 1 | , μ > 1 θ k = 1 + β k S N g k T d k 1 g k 2 (6)

根据现有的共轭系数公式,构造一个新的共轭系数公式和谱系数公式,从而提出一种新的谱共轭梯度法,保证算法在每次迭代时不依赖于任何线搜索总能产生充分下降的搜索方向,并在Armijo线搜索和一般假设条件下,给出算法的全局收敛性证明。将式(5)的分子或者分母推广到其它共轭梯度法上,或者建立混合共轭梯度法,也具备良好的数值计算效果。更多的可以参看文献 [10] [11] [12] [13] [14]。

文章结构如下:第2节两种新算法的提出;第3节共轭梯度法及其全局收敛性;第4节谱共轭梯度法及其全局收敛性;第5节数值实验和第6节全文总结。

2. 修改的共轭梯度法和谱共轭梯度法

基于以上文献的思想,特别是 β k D P R P β k S N 的构造,本文对文献 [15] 的公式做出如下的修改,给出一个新的 β k C 公式

β k C = g k T ( 2 g k 1 g k g k g k g k 1 d k 1 ) g k 1 2 + μ | g k T d k 1 | + λ , μ 0 , λ > 0 (7)

基于公式(7),采用SWP线搜索条件来修正共轭梯度算法如下:

算法1

Step 1:初始值 x 0 R n ε > 0 ,令 μ 0 λ > 0 0 < ρ < σ < 1 k : = 1 d 1 = g 1 ,计算 g k ,若 g 1 ε ,则停止。

Step 2:用SWP线搜索公式计算 α k

Step 3:令 x k + 1 = x k + α k d k ,若 g k + 1 ε ,则停止,

Step 4:用式(3)和(7)分别计算 d k + 1 , β k + 1 C

Step 5:使得 k : = k + 1 ,转Step 2。

谱共轭梯度法作为求解问题(1)的另一方式被提出,通过调整谱系数和共轭参数,建立合适的算法,本文降低线搜索条件,故采用WWP线搜索条件设计谱共轭梯度算法如下:

算法2

Step 1:初始值 x 0 R n ε > 0 ,令 μ 0 λ > 0 0 < ρ < σ < 1 k : = 1 d 1 = g 1 ,计算 g k ,若 g 1 ε ,则停止。

Step 2:用WWP线搜索公式计算 α k

Step 3:令 x k + 1 = x k + α k d k ,若 g k + 1 ε ,则停止,

Step 4:用(7)式计算 β k + 1 C ,由下式计算搜索方向 d k + 1

d k + 1 = δ k + 1 g k + 1 + β k + 1 d k δ k + 1 = 1 + β k + 1 C g k + 1 T d k g k + 1 2

Step 5:使得 k : = k + 1 ,转Step 2。

以下常规性假设在共轭梯度法的研究中经常被用到

假设H [9] (H1)定义目标函数 f ( x ) 在水平集 Ω = { x n ; f ( x ) f ( x 0 ) } 有下界,且 x 0 为初始点。

(H2) 目标函数 f ( x ) 在水平集 Ω 的一个领域N内连续可微,其梯度函数满足Lipschitz连续,即存常数 L > 0 ,使得 g ( x ) g ( y ) L x y , x , y N

3. 共轭梯度法及其全局收敛性

引理3.1:若假设H成立,考虑序列 x k + 1 = x k + α k d k ,序列 { g k } { d k } 由算法1生成,如果

1) 对所有k均成立 g k + 1 > 3 L α k d k

2) 存在常数 r > 0 ,使得对任给 k > 0 ,都有 g k > r 成立,则存在一个充分大的 k 0 ,使得 k > k 0 时, β k + 1 C 满足

0 β k + 1 C β k + 1 F R = g k + 1 2 g k 2 (8)

证明:因为 β k + 1 C 的定义为

β k + 1 C = g k + 1 T ( 2 g k g k + 1 g k + 1 g k + 1 g k d k ) g k 2 + μ | g k + 1 T d k | + λ (9)

1) 证明分子 g k + 1 T ( 2 g k g k + 1 g k + 1 g k + 1 g k d k ) g k + 1 3 L α k d k 成立

g k + 1 T ( 2 g k g k + 1 g k + 1 g k + 1 g k d k ) g k + 1 2 g k g k + 1 g k + 1 g k + 1 g k + 1 + g k + 1 g k g k + 1 ( 2 g k g k + 1 g k + 1 g k + 1 g k + 1 + g k + 1 g k ) ( 2 g k g k + 1 ) g k + 1 g k + 1 g k + 1 + g k + 1 g k + 1 g k 2 g k g k + 1 g k + 1 + g k + 1 g k + 1 g k 3 g k + 1 g k + 1 g k g k + 1 3 L α k d k

2) 将以上化简结果代入式(9)中

β k + 1 C = g k + 1 T ( 2 g k g k + 1 g k + 1 g k + 1 g k d k ) g k 2 + μ | g k + 1 T d k | + λ g k + 1 3 L α k d k g k 2 + μ | g k + 1 T d k | + λ g k + 1 3 L α k d k g k 2

因为

0 α k d k < g k + 1 3 L

则引理3.1得证。

引理3.2:如果参数 σ < 1 2 , μ 0 , λ > 0 ,则存在常数 c 1 = 1 2 σ + σ k 1 σ , c 2 = 1 σ k 1 σ 对所有的k,有下式成立:

c 2 g k 2 g k T d k c 1 g k 2 , k 1 (10)

证明:数学归纳法:当 k = 1 , d 1 = g 1 , g 1 T d 1 = g 1 2 ,则(10)式成立。

假设 k > 1 ,都有 g k T d k < 0 成立,令(3)式中k为k + 1时与 g k + 1 T 作内积,结合(8)式得

g k + 1 T d k + 1 g k + 1 2 = 1 g k + 1 T d k g k 2

在上式中用

σ d k T g k d k T g ( x k + α k d k ) σ d k T g k

则有

1 + σ g k T d k g k 2 g k + 1 T d k + 1 g k + 1 2 1 σ g k T d k g k 2 (11)

利用(11)式递推可得:

c 1 = 1 2 σ + σ k 1 σ g k + 1 T d k + 1 g k + 1 2 1 σ k 1 σ = c 2

由归纳法知,上述引理成立。当 σ < 1 2 时,充分下降条件对正常数 c = 1 2 σ 1 σ 也成立。

由引理3.2和文献 [1] 引理1.4.1,可得以下引理。

引理3.3:若假设H成立,序列 { x k } 由算法1生成, d k 满足 g k T d k < 0 α k 由SWP线搜索得到,则Zoutendijk条件成立:

k 1 g k 4 d k 2 < +

证明:由SWP线搜索得 d k T y k ( σ 1 ) g k T d k

由Lipschitz条件得 d k T y k α k L d k 2 ,把两式结合,则有

α k σ 1 L g k T d k d k 2 (12)

由SWP线搜索和(12)式得

f k f k + 1 c ( g k T d k ) 2 d k 2

其中, c = δ ( 1 σ ) L ,对上式从 k = 1 , 2 , 求和,由假设H(1)知, k 1 ( g k T d k ) 2 d k 2 < + 成立,由充分下降条件 g k T d k c g k 2 成立,则有

k 1 g k 4 d k 2 < +

以下是算法1的全局收敛性结果。

定理1:若假设H成立,序列 { g k } { d k } 由算法1生成,若 σ < 1 2 ,则 lim k inf g k = 0

证明:反证法,即存在常数 r > 0 ,有 g k r , k 1

d k + 1 = g k + 1 + β k + 1 C d k d k + 1 2 = ( β k + 1 C ) 2 d k 2 2 β k + 1 C g k + 1 T d k + g k + 1 2

两边同除 g k + 1 4

d k + 1 2 g k + 1 4 = ( β k + 1 C ) 2 d k 2 g k + 1 4 2 β k + 1 C g k + 1 T d k g k + 1 4 + 1 g k + 1 2

由SWP线搜索、(8)式和(10)式知

| g k + 1 T d k | g k 2 σ | g k T d k | g k 2 σ 1 σ

|| d k + 1 || 2 | | g k + 1 | | 4 ( β k + 1 F R ) 2 d k 2 g k + 1 4 + 2 β k + 1 F R | g k + 1 T d k | g k + 1 4 + 1 g k + 1 2 d k 2 g k 4 + 2 σ | g k T d k | g k + 1 4 g k 2 + 1 g k + 1 2 d k 2 g k 4 + 1 g k + 1 2 ( 1 + 2 σ 1 σ ) 1 + σ 1 σ i = 1 k + 1 1 g i 2 1 + σ 1 σ k + 1 r 2

由上式得

k 1 g k + 1 4 d k + 1 2 1 σ 1 + σ r 2 k 1 1 k + 1 = +

与引理3.3矛盾,故定理1得证。

4. 谱共轭梯度法及其全局收敛性

引理4.1:序列 { g k } { d k } 由算法2生成, k 1 ,都有 g k T d k = g k 2 < 0

证:当 k = 1 时, d 1 = g 1 , g 1 T d 1 = g 1 2 < 0 成立,

k > 1 时, g k T d k = δ k g k 2 + β k C g k T d k 1 = ( 1 + β k C g k T d k 1 g k 2 ) g k 2 + β k C g k T d k 1 = g k 2 β k C g k T d k 1 + β k C g k T d k 1 = g k 2 < 0

故算法2中产生的搜索方向 d k 满足充分下降性。

引理4.2:若假设H成立, d k 满足 d k T g k < 0 α k 满足WWP线搜索,则Zoutendijk条件成立:

k 1 ( g k T d k ) 2 d k 2 < +

定理2:若假设H成立,序列 { g k } { d k } 由算法2生成,则 lim k inf g k = 0

证明:假设结论不成立,则存在一个常数 r > 0 ,使得 g k r , k 0 ,因为

δ k + 1 = ( 1 + β k + 1 C g k + 1 T d k g k + 1 2 )

由算法2中定义的搜索方向 d k + 1 ,两边取范数模平方得

d k + 1 2 = ( β k + 1 C ) 2 d k 2 2 δ k + 1 d k + 1 T g k + 1 δ k + 1 2 g k + 1 2

两端同除 g k + 1 4 ,又因为 d k + 1 T g k + 1 = g k + 1 2

又因为引理3.1

d k + 1 2 g k + 1 4 = ( β k + 1 C ) 2 d k 2 g k + 1 4 + 2 δ k + 1 g k + 1 2 δ k + 1 2 g k + 1 2 ( g k + 1 2 g k 2 ) 2 d k 2 g k + 1 4 ( δ k + 1 1 ) 2 g k + 1 2 + 1 g k + 1 2 d k 2 g k 4 + 1 g k + 1 2

k = 0 时, d 0 = g 0 ,上式写成

1 g 0 2 + 1 g k + 1 2 i = 0 k + 1 1 g i 2 k + 2 r 2

所以有

i = 0 k g k + 1 4 d k + 1 2 r 2 i = 0 k 1 k + 1 = +

此结论与引理4.2的Zoutendijk条件矛盾,故定理2成立。

5. 数值实验

本节中,我们分析所提出新方法的数值性能,分别与文献 [15] 的方法作比较,记为WSWP,还有文献 [16] 的方法作比较,记为RMIL+,本文的共轭梯度法和谱共轭梯度法分别记为FSWP和PCWWP,无约束测试问题选自文献 [17],算法运行的终止条件为 g k 10 6 或迭代次数超过10,000,所有代码实现都在Matlab2016a中进行,数值结果以NI,NF,NG的形式表示,其中,NI指迭代次数,NF指函数取值,NG指梯度取值。“-”指算法运行失效。各符号和参数说明如下:

RMIL + SWP:RMIL + 公式用SWP线搜索, σ = 0.1 , δ = 0.01

WSPW:韦等提出的公式用SWP线搜索, σ = 0.1 , δ = 0.01

FSWP:本文提出的共轭梯度法用SWP线搜索, σ = 0.2 , δ = 0.01 , μ = 4.5 , λ = 0.2

PCWWP:本文提出的谱共轭梯度法用WWP线搜索, σ = 0.1 , δ = 0.01 , μ = 4.5 , λ = 0

Table 1. Numerical results of each method

表1. 各方法的数值计算结果

表1中可以看出,基于新的参数公式,本文提出的共轭梯度法(FSWP)的数值计算性能优于表中其它方法,能解决绝大部分测试问题,相反,本文提出的谱共轭梯度法收敛性条件减弱,但数值计算性能(PCWWP)却没有共轭梯度法的好,如何调整谱共轭梯度法的两个参数,使之达到更好的计算效果,仍需进一步研究。

6. 总结

本文借鉴已有文献的思路,对经典的共轭梯度法中的共轭参数作简单的分解或变形,而不改变原公式的大致结构,从而提出类似的 β k 新参数公式,并分别在SWP线搜索下建立新的共轭梯度法的全局收敛性分析和WWP线搜索下建立谱共轭梯度法的全局收敛性分析,数值实验与经典方法作比较,本文提出的共轭梯度法更有效。

文章引用

陈秀芳,李 锋. 一类修正的共轭梯度法及其数值计算效果
A Kind of Modified Conjugate Gradient Method and Its Numerical Calculation Effect[J]. 应用数学进展, 2020, 09(09): 1469-1478. https://doi.org/10.12677/AAM.2020.99173

参考文献

  1. 1. 戴彧虹, 袁亚湘. 非线性共轭梯度法[M]. 上海: 上海科技出版社, 1999.

  2. 2. Fletcher, R. and Reeves, C.M. (1964) Function Minimization by Conjugate Gradients. The Computer Journal, 7, 149-154. https://doi.org/10.1093/comjnl/7.2.149

  3. 3. Dai, Y.H. and Yuan, Y. (1999) A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property. SIAM Journal on Optimization, 10, 177-182. https://doi.org/10.1137/S1052623497318992

  4. 4. Polak, E. and Ribiére, G. (1969) Note sur la convergence de directions conjugées. Rev. Francaise Informat Recherche Opèrationelle, 3e Anné e, 16, 35-43. https://doi.org/10.1051/m2an/196903R100351

  5. 5. Hestenes, M.R. and Stiefel, E. (1952) Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards, 49, 409-436. https://doi.org/10.6028/jres.049.044

  6. 6. Zhang, L. (2009) An Improved Wei-Yao-Liu Nonlinear Conjugate Gradient Method for Optimization Computation. Applied Mathematics and Computation, 215, 2269-2274. https://doi.org/10.1016/j.amc.2009.08.016

  7. 7. Dai, Z. and Wen, F. (2012) Another Improved Wei-Yao-Liu Nonlinear Conjugate Gradient Method with Sufficient Descent Property. Applied Mathematics and Computation, 218, 7421-7430. https://doi.org/10.1016/j.amc.2011.12.091

  8. 8. 姜彬. 基于Armijo搜索的谱共轭梯度法研究[D]: [硕士学位论文]. 太原: 太原科技大学, 2013.

  9. 9. 景书杰, 李亚敏, 牛海峰. 一类基于Armijo线搜索的新的谱共轭梯度法[J]. 河南理工大学学报(自然科学版), 2019, 38(4): 154-158.

  10. 10. Du, X., Zhang, P. and Ma, W. (2016) Some Modified Conjugate Gradient Methods for Unconstrained Optimization. Journal of Computational and Applied Mathematics, 305, 92-114. https://doi.org/10.1016/j.cam.2016.04.004

  11. 11. Sellami, B., Belloufi, M. and Chaib, Y. (2017) Globally Convergence of Nonlinear Conjugate Gradient Method for Unconstrained Optimization. RAIRO—Operations Research, 51, 1101-1117. https://doi.org/10.1051/ro/2017028

  12. 12. Zheng, X. and Shi, J. (2018) A Modified Sufficient Descent Polak-Ribiére-Polyak Type Conjugate Gradient Method for Unconstrained Optimization Problems. Algorithms, 11, 133. https://doi.org/10.3390/a11090133

  13. 13. (2018) Broyden-Fletcher-Goldfarb-Shanno Conjugate Gradient Methods. Journal of Optimization Theory and Applications, 178, 860-884. https://doi.org/10.1007/s10957-018-1324-3

  14. 14. Mtagulwa, P. and Kaelo, P. (2018) A Convergent Modified HS-DY Hybrid Conjugate Gradient Method for Unconstrained Optimization Problems. Journal of Information and Optimization Sciences, 40, 1-18. https://doi.org/10.1080/02522667.2018.1424087

  15. 15. 韦春妙, 庞建华, 黄李韦, 罗杰明. 新的Armijo线搜索下PRP共轭梯度法及其收敛性分析[J]. 广西科技大学学报, 2019, 30(2): 107-114.

  16. 16. Rivaie, M., Mamat, M. and Abashar, A. (2015) A New Class of Nonlinear Conjugate Gradient Coefficients with Exact and Inexact Line Searches. Applied Mathematics and Computation, 268, 1152-1163. https://doi.org/10.1016/j.amc.2015.07.019

  17. 17. Morè, J., Garbow, B.S. and Hillstrome, K.E. (1982) Testing Unconstrained Optimization Software. ACM Transactions on Mathematical Software, 7, 17-41. https://doi.org/10.1145/355934.355936

期刊菜单