一个充分下降的修正PRP 型谱共轭梯度法

简金宝, 宋 丹, 江羡珍

(广西民族大学数学与物理学院，南宁 530006)

0 引言

共轭梯度法是求解光滑无约束优化问题min{f(x)|x ∈Rn}最有效的方法之一，其迭代公式的一般形式为

其中gk=g(xk) =∇f(xk)为当前迭代点的梯度，βk为共轭参数，αk为步长。常用于产生步长的非精确线搜索准则有三种：

1) Armijo 线搜索准则，选择步长αk=max{ρ0,ρ1,ρ2,···},0<ρ<1，满足

2) 标准Wolfe 线搜索准则，即

3) 强Wolfe 线搜索准则，即

其中，(3)式中的参数满足δ ∈(0,1)，(4)式及(5)式中的参数δ和σ满足0<δ<σ<1。众所周知，共轭参数βk对共轭梯度法的理论和数值性质有重要影响。著名的参数βk计算公式有[1–5]

不难推知

由(7)式可知，修正的JSJ 公式不仅保持了PRP 公式的结构和性能，并且传承了FR方法的收敛性质。

谱共轭梯度法是共轭梯度法的一种推广，其搜索方向结构为

其中θk称为谱参数。它最大优点是通过共轭参数和谱参数的二维度调整使得搜索方向满足某一预设条件，比如，充分下降条件或共轭条件等。特别是当谱参数θk>1 时，算法可获得较大的下降量。较早的谱共轭梯度法由Birgin 和Martin´ez[8]提出，相应的谱参数为

随后，谱共轭梯度法得到进一步研究，并且获得了一些收敛性和数值表现良好的计算方法，详见文献[9—12]。

文献[11]取定共轭参数为

再由牛顿方向和拟牛顿方程设计谱参数为

由(11)式和(12)式产生的谱共轭梯度法简记为NA 方法。由NA 方法产生的搜索方向不依赖于任何线搜索均满足充分下降条件，在强Wolfe 线搜索准则下证明了NA 方法的全局收敛性，获得较好的数值效果。为了使方向dk的充分下降性不依赖于线搜索，文献[12]在假设

的条件下，构造谱参数为

并由此建立了一类新的谱共轭梯度法，该方法在标准的Wolfe 线搜索准则下全局收敛，并且数值表现良好。

易见，由(13)式及(14)式构造的搜索方向dk恒满足充分下降条件

基于(6)式、(13)式和(14)式，我们在第1 部分建立一个修正PRP 型谱共轭梯度算法，并证明算法的全局收敛性；在第2 部分对算法进行数值测试与比较，并报告测试结果。

1 算法及其收敛性

基于搜索方向(13)及强Wolfe 线搜索准则，我们给出修正PRP 型谱共轭梯度算法(简记为JSJ 算法)的步骤如下：

初始步 任取初始点x1∈Rn，参数0<δ<σ< 1。给定终止精度ϵ> 0。d1=−g1，置k:=1；

步骤1 若//gk//≤ϵ，则停止。否则，转入步骤2；

步骤2 采用强Wolfe 线搜索条件(5)求步长αk；

步骤3 按xk+1=xk+αkdk产生新的迭代点，计算gk+1:=g(xk+1)，并由(6)式、(13)式和(14)式计算搜索方向dk+1；

步骤4 令k:=k+1，返回步骤1。

为获得JSJ 算法的全局收敛性，目标函数需要有以下两个常规假设条件：

(H1) 目标函数f(x)在水平集Λ={x ∈Rn|f(x)≤f(x1)}上有界，其中x1为JSJ算法的初始点；

(H2) 目标函数f(x)在水平集Λ 的一个邻域U 内可微，且其梯度函数g(x)满足Lipschitz 条件，即存在L>0，使

下面引理所给出的是著名的Zoutendijk 条件[14]，其在下降迭代算法全局收敛性分析中起着重要作用。

引理1 设假设(H1)和(H2)成立，考虑一般迭代方法xk+1=xk+αkdk，若搜索方向dk满足下降条件<0，步长因子αk满足标准Wolfe 线搜索准则(4)，则

特别地，当搜索方向dk满足充分下降条件时，有

基于充分下降性(15)式和引理1，可建立JSJ 算法的全局收敛性定理。

定理1 若假设(H1)和(H2)成立，则由JSJ 算法产生的点列xk满足lim infk→∞//gk//=0。

进而由(14)式，有

结合强Wolfe 线搜索条件(5)以及充分下降性(15)式，得

另一方面，由(13)式，得dk=−θkgk+βkdk−1。对上式两边分别平方后得

对等式两边同时除以//gk//4并结合(17)式、(18)式以及充分下降性(15)式，得

由此递推可知

因此

这与(16)式相矛盾，从而lim infk→∞//gk//=0 获证。

2 数值试验

为了检验JSJ 算法的有效性，本文对100 个算例进行数值实验，并在相同的计算环境下，与五个相近的算法进行比较。他们分别是NA[11]和LFZ[12]谱共轭梯度法，数值效果好的三项共轭梯度法KD[15]，以及两个带有新型共轭条件的下降共轭梯度法HZ[16–17]和DK[18]。100 个测试算例的前50 个(从bard 到woods)取自CUTEr 问题集[19]，其余50 个问题取自测试问题集[20–21]，问题的维数在2∼6 000 000 之间，所有测试都在强Wolfe 非精确线搜索准则(5)下完成。测试环境为Matlab R2016a, Windows 7 操作系统，DELL 电脑4GB 内存。相关选取参数为：δ=0.01, σ=0.1。本文算法的终止准则为以下两者情形之一：

终止准则2)出现时认为该方法对相应例子失效，并记为“F”。

为了综合比较，在试验中，我们分别对迭代次数(Itr)，函数计算次数(NF)，梯度计算次数(NG)，CPU 计算时间(Tcpu)，精度//g∗//五个指标进行观察和比较，数值结果详见表1 和表2。

表1 前50 个算例的数值试验报告

续表

续表

表2 其余50 个算例的数值试验报告

续表

同时，我们还采用Dolan 和Mor`e[22]性能图对试验效果进行直观刻划，图1 至图4 分别对应CPU 计算时间(Tcpu)，函数计算次数(NF)，梯度计算次数(NG)和迭代次数(Itr)的比较结果。图中

其中size A 表示集合A 的元素个数，P表示由测试问题p构成的问题集，np表示问题集中问题个数，S表示由算法s组成的算法集，定义：tp,s=算法s在求解问题p所消耗的计算时间(或迭代次数或函数计算次数或梯度计算次数)，且给表1 中“F”的比率rp,s均赋值为2 max{rp,s:s ∈S}。性能图的具体解释参见文献[22]。总体来说，ρ(τ)的曲线越居上，其对应方法的数值性能越好。

从表1 和表2，图1 至图4 可以看出，JSJ 算法成功地解决了96%的测试问题，是所有测试的6 个算法中占比最高的，同时，JSJ 算法在成功解决的问题中有约41%的算例在所考查的四个指标中占优，略高于KD 算法和LFZ 算法，明显高于其余的三个算法。故JSJ 算法在我们所测试的100 个问题中的数值效果总体上要优于其他五个算法。

图1 CPU 计算时间比较

图2 函数计算次数比较

图3 梯度计算次数比较

图4 迭代次数比较