基于凸组合技术的加速FR型共轭梯度算法*

李丹丹，王松华

(1.广州华商学院应用数学系，广东广州 511300；2.百色学院数学与统计学院，广西百色 533000)

0 引言

在振动系统、潮流方程等科学与工程计算领域存在许多大规模优化问题[1,2]，而这些优化问题往往能够转化为非线性方程组问题。因此，研究求解大规模非线性方程组的高效数值算法具有重要的理论价值与实际意义。

本文主要考虑以下非线性方程组问题：

F(x)=0,x∈Rn，

(1)

minf(x),x∈Rn。

近年来，求解上述优化问题的常见算法有牛顿法、信赖域法、拟牛顿法、Levenberg-Marquardt算法及其各种变形[3-8]。在选择合理初始点的前提下，上述算法对于小规模优化问题具有快速收敛和数值效果良好等特点，但在迭代过程中，需要计算和存储相关矩阵信息，给求解大规模优化问题带来一定的局限性。为建立求解大规模优化问题的高效算法体系，研究者提出具有算法简单、计算和存储量低等优点的共轭梯度法[9-11]。

经典共轭梯度法的一般迭代公式为

xk+1=xk+αkdk，k=0,1,2,...,

其中αk为由某种线搜索所决定的步长。搜索方向dk为

其中,βk为共轭参数，Fk为F(xk)的简写。

本文基于Abubakar等[12]提出的修正FR搜索方向，借鉴Yuan等[13]的凸组合思想，构造凸组合系数如下：

同时，采用Andrei[14]的加速线搜索技术，提出一个求解大规模非线性方程组问题的加速FR型共轭梯度算法。

1 算法描述与性质

本节主要讨论搜索方向的构建并介绍线搜索技术，同时提出凸组合修正共轭梯度算法。

首先，Abubakar等[12]在2019年提出一种修正FR共轭梯度法，其搜索方向为

dk=

其中，ωk-1=xk-xk-1,μ>0。该搜索方向具备充分下降性和信赖域特征，能有效求解大规模无约束优化问题。基于Yuan等[13]的凸组合思想，本文构建一个新型的凸组合搜索方向：

(2)

其次，本文通过下述方法计算步长αk=rmk，使得mk满足下式的最小非负整数，即

(3)

其中，σ∈(0,1),r∈(0,1)。Andrei[14]研究表明，合理地应用加速线搜索，将有效提高算法的计算效率。于是借鉴于Andrei[14]的加速线搜索技术思想，对步长αk做出修正，即

最后，建立求解非线性方程组问题(1)的凸组合加速FR型共轭梯度算法(MMFR)。

步骤1：给定初始点x0∈Rn，参数ε,σ,r,β,μ∈(0,1)，令k:=0；

步骤2：若‖Fk‖≤ε，则算法停止；

步骤3：通过式(2)计算搜索方向dk；

步骤4：若‖F(xk+dk)‖≤β‖Fk‖，则令步长αk=1，转步骤6，否则转步骤5；

步骤5：通过式(3)决定步长αk；

步骤7：(更新步)更新新的迭代点xk+1=xk+αkdk，令k:=k+1，转步骤2。

为后续证明算法的全局收敛性质，下面分析搜索方向dk的两个重要性质：充分下降性和信赖域特性。

引理1算法MMFR产生的序列{dk}和{Fk}满足以下性质：

(4)

及

‖dk‖≤τk‖Fk‖，

(5)

-Nk‖Fk‖2。

此外，由式(2)和Cauchy-Schwartz不等式可知

‖dk‖=‖-NkFk+(1-Nk)·

Nk‖Fk‖+(1-Nk)·

综上所述，式(4)和式(5)成立,引理1得证。

2 全局收敛性分析

为进一步分析算法MMFR的收敛性，本节做如下假设：

假设H

(H1)函数F(x)在开凸集Ω1⊆Ω=

{x|‖F(x)‖≤‖F(x0)‖}是连续可微的；

(H2)函数F(x)的雅可比矩阵为∇F(x)是有界的且为对称正定矩阵，即存在正常数ξ1≥ξ2>0，使得有‖∇F(x)‖≤ξ1和ξ2‖p‖2≤pT∇F(x)

p≤ξ1‖p‖2,p∈Rn。

证明：由Brown等[15]的引理3.8可得

由引理1和式(3)可推出

(6)

这说明函数f(x)沿着下降方向dk是充分下降的。公式(6)结合f(x) 的定义可知，对于任意的k，都有‖Fk+1‖≤‖Fk‖。此外，由式(3)和式(4)得出

由假设H1中函数的有界性，再结合上式得

αkdk)<∞，

下面给出算法MMFR的全局收敛性定理。

(7)

假设结论不成立，即存在正整数ξ，对于任意k，那么有

‖∇f(xk)‖>ξ。

(8)

另外，由假设H1可知，集合为有界集合，则序列{xk}是有界的，于是可得序列{dk}也是有界的。不失一般性，设点x*和d*分别为序列{xk}和{dk}的聚点。因此，对式(7)取极限得

∇f(x*)Td*≥0。

同理，对式(6)取极限得

定理1说明序列{xk}至少是线性收敛的，下面定理给出算法MMFR具有强收敛性质。

定理2在假设H条件下，若算法MMFR产生的任一子序列{xk}收敛于聚点x*，则非线性方程组问题(1)的最优解为x*，进一步有序列{xk}整列收敛于x*。

证明：类似于Yuan[16]中定理3.4的证明方法，易证结论成立，故省略证明过程。

3 数值试验

本节通过比较算法MMFR、经典FR、三项FR算法在求解大规模非线性方程组问题上的数值结果，验证算法MMFR的有效性与稳定性。

下面给出经典FR算法和三项FR算法的搜索方向，分别为

(9)

dk=

(10)

在算法MMFR的步骤2中，分别采用式(9)和式(10)产生搜索方向，其余步骤不变，得到的算法记为FR算法和MFR算法。

参数设置：r=0.5,σ=0.068,μ=0.25,β=0.5。程序运行环境：MATLAB(2014a)软件实现，Windows10 (64 bite)，RAM:8 G，CPU 3.60 GHz。

算法终止准则为‖Fk‖≤10-5或Iter>3000，维数为[4500,12000,24000,30000,45000]。测试问题的函数名称和初始点[17]见表1，数值试验结果如表2所示，其中Pro (Problem)为问题序号，Dim (Dimension)为维数，Iter (Iterations)为迭代次数，NF(The number of function)为函数F(x)计算次数，Time为程序运行时间(单位：s)。根据迭代次数、函数计算次数和运行时间可以看出，总体上算法MMFR最好，算法MFR其次，算法FR最差(表2)。

表1 测试函数

表2 数值结果

为直观地展示3种算法的性能差异，本节采用性能曲线描绘方法[18]分别描绘出迭代次数性能图、函数计算次数性能图和运行时间性能图(图1-3)。由图1-3可知，算法MMFR总体上比算法MFR和算法FR更优，且具有更好的鲁棒性，因此本文提出的算法MMFR是有效的和鲁棒的。

图1 迭代次数性能图

图2 函数计算次数性能图

图3 运行时间性能图

4 结论

本文在修正FR算法的基础上，结合凸组合思想，构造出一个新的修正搜索方向，并利用加速线搜索技术，提出一个加速FR型共轭梯度算法。新的搜索方向不依赖线搜索,具有充分下降和信赖域特性，还具有良好的理论性质与数值效果。因计算简单，存储量小，十分适合求解大规模非线性方程组问题。同时，也可尝试将新算法进一步推广到信号恢复等实际应用中。