求解无约束优化问题的两类修正的WYL共轭梯度方法

孙颖异,李健,孙中波,王增辉

(1.吉林农业大学信息技术学院,吉林 长春130118;2.长春工业大学电气与电子工程学院,吉林 长春130012;3.东北师范大学人文学院理工学院,吉林 长春130117)

1.引言

考虑如下无约束优化模型

其中f(x) : Rn →R是连续可微函数.共轭梯度法是求解这类问题(1.1)的有效算法之一,具体迭代格式如下

其中xk是第k次迭代点,αk是搜索步长,搜索步长可以按照某类精确线搜索准则或者非精确线搜索准则条件计算得到,dk是搜索方向,可以按照如下公式进行计算

式(1.3)中gk=▽f(xk)是目标函数梯度,βk−1是共轭梯度参数.不同的参数βk−1对应不同的共轭梯度方法.例如,Fletche-Reeves (FR)法、Hestenes-Stiefel (HS)法、Polak-Ribiere-Polyak(PRP)法、Conjugate-descent(CD)法、Liu-Storey (LS)法、Dai-Yuan (DY)法[1−7].它们对应的共轭梯度参数βk如下

其中yk=gk −gk−1,‖·‖为欧几里得范数.在精确线搜索准则条件下,如果目标函数为二次函数,上述六类共轭梯度法是等价的.但是,如果目标函数为一般函数时,这六类算法的性质差别很大.PRP共轭梯度算法和HS共轭梯度算法是这几类经典共轭梯度法中计算效率较好的两类算法.由于PRP共轭梯度算法和HS共轭梯度算法的搜索方向具有很好的性质,也即是可以克服算法在迭代步骤充分大的情况下产生小步长现象.但是,在非精确线搜索准则条件下,如果目标函数是非凸函数时,PRP 共轭梯度算法和HS共轭梯度算法无法保证产生的搜索方向为下降方向,从而,影响了算法的全局收敛性.虽然经典PRP共轭梯度法收敛性很难直接给出,但是,通过对搜索方向进行适当修正,便可得到该类算法的全局收敛性[8−11].POWELL 指出共轭梯度参数βk不应该小于零,从而可以得到更加优良的共轭梯度算法.随后,学者们提出了一系列满足共轭梯度参数βk大于零的修正类共轭梯度法[12−13].最近,WEI等[14]提出了一个新的共轭梯度法(简称WYL共轭梯度法).他们定义如下形式的共轭梯度参数

在非精确线搜索条件下,证明了WYL共轭梯度法具有全局收敛性[15].为了满足共轭梯度参数非负性,YUAN提出了一类修正的PRP共轭梯度法(MPRP方法),共轭梯度参数表达式如下

当搜索方向满足充分下降条件时,全局收敛性分析不依赖于线搜索准则条件,因此,提高了算法的计算效率.本文首先基于MPRP方法思想,提出了一类修正的WYL共轭梯度法(简称为DWYL共轭梯度法).特别地,共轭梯度参数βk按照如下公式进行计算

2.DWYL共轭梯度法和MDWYL共轭梯度法

假设2.1假设水平集Ω={x ∈Rn|f(x)≤f(x1)}有界.

假设2.2在水平集的某个邻域Ω0内,目标函数f(x)是连续可微.目标函数的梯度g满足利普希茨条件,也即是,存在一个正常数L>0,使得

由于函数迭代序列{f(xk)}是递减的,易知由算法2.1生成的迭代序列{xk}均包含在水平集Ω.另外,由算法2.1和WOLFE准则,以及{gk}有界性知,

算法2.1(DWYL共轭梯度算法)

步1 给定一些正常数ϵ,t,ρ<σ <1,选择一个初始点x1∈Rn,k:=0.

步2 计算搜索方向.按照如下公式计算搜索方向

其中,

步3 确定终止停止迭代条件.如果‖gk‖≤ϵ,算法停止.否则,转入步4.

步4 利用WOLFE线搜索准则条件确定搜索步长αk

步5 更新迭代点.令xk+1=xk+αkdk,k:=k+1,返回步2.

另外,为了便于讨论算法的全局收敛性,我们对搜索方向(2.2)进一步修正,提出另一类搜索方向的计算方法,也即是,假设存在一个正常数µ>0使得如下搜索方向计算公式成立

其他计算步骤与算法2.1相同,从而得到另一类修正的WYL共轭梯度算法(简称为MDWYL共轭梯度法).

下面将要讨论DWYL共轭梯度法和MDWYL共轭梯度法的搜索方向充分下降性.

引理2.1假设2.1和2.2成立,搜索方向按照公式(2.2)计算,搜索步长满足WOLFE线搜索准则,则搜索方向满足如下不等式

证当k=0时,根据算法2.1中步2,知dT1g1=−‖gk‖2,结论显然成立.

当k >0时,分如下两种情况讨论:

取a由a2+b2≥2ab得

因此,算法2.1中搜索方向满足充分下降性,这个性质为后续全局收敛性分析提供了便利条件.

引理2.2假设2.1和2.2成立,搜索方向按照公式(2.5)计算,搜索步长满足WOFLE线搜索准则,则搜索方向满足如下不等式

证证明思想与引理2.1相同,因此省略.

3.全局收敛性

引理3.1[17−18]假设2.1和2.2成立,搜索方向和搜索步长按照算法2.1和步4进行计算,则有

定理3.1假设2.1和2.2成立,迭代序列{xk}和搜索方向dk分别通过算法2.1计算得到,则存在一个常数0,使得

证根据算法2.1,分如下两种情况讨论:

情况1 当k=0时,搜索方向dk=−gk,从而=1,结论显然成立.

情况2 当k >0时,搜索方向dk=−gk+βDWYLk−1dk−1,其中,

当gTk dk−1≤0时,搜索方向dk=−gk,从而=1,结论显然成立.

当gTk dk−1>0时,搜索方向

定理3.2假设2.1和2.2成立,迭代序列{xk}和搜索方向dk分别通过算法2.1和公式(2.5) 计算得到,若存在一个常数ω >0,使得‖gk‖≥ω,则存在一个常数¯0,使得

证从(2.5)出发,分如下两种情况讨论:

1)若|gTk+1y∗k|‖dk‖≥µ‖gk+1‖,则‖dk+1‖=‖gk+1‖,此时,=1,结论显然成立.

2)若|gTk+1y∗k|‖dk‖<µ‖gk+1‖,令

由上式,有

于是,由(3.4)可以估计‖dk+1‖

令

因此,结论成立.

定理3.4假设条件2.1和2.2成立,迭代序列{xk}和搜索方向dk分别通过算法2.1,则有

证假设(3.7)不成立,则存在一个常数>0,存在k ∈N 使得

由(3.2)可以得到

所以结论成立.

4.数值实验

本文采用文[19]中的部分函数为测试函数.在Matlab7.1环境下编写程序代码,CPU为奔腾(R),2.19 GHz,1 Gb内存.程序代码中的参数选取为

具体数值结果见表1-表4,表1代表本文DWYL共轭梯度算法数值结果,表2代表本文MDWL共轭梯度算法数值结果,表3代表WYL共轭梯度算法数值结果[14],表4代表修正的WYL 共轭梯度算法数值结果[15].其中P代表测试问题,N代表测试问题的变量维数,NI代表算法迭代次数,NG代表目标函数梯度计算次数,NF目标函数计算次数,CPU-TIME 代表计算机实际计算时间,s代表秒.

表1 本文DWYL共轭梯度算法数值结果

表2 本文MDWYL共轭梯度算法数值结果

表3 WYL共轭梯度算法数值结果[14]

表4 修正的WYL共轭梯度算法数值结果[15]

从表1-表2可见,本文提出的两类算法是可行的、有效的.表3和表4是文[14-15]数值仿真结果.从迭代次数和CPU 时间来看,本文提出的算法要好于文[14-15]算法.同时,由于本文的算法产生的搜索方向具有充分下降的性质,而且算法的收敛性也独立于线搜索准则,从而,使得算法具有较好的计算效率.另外,本文算法DWYL虽然好于文[14-15]算法,但是,通过对搜索方向的讨论,我们采用(2.2)公式计算搜索方向,在不依赖于线搜索准则条件下,实现了算法的全局收敛,从而提高了算法的计算效率.从表2的数值结果可以看出,线搜索准则对收敛性分析的影响还是比较明显.

表5 测试问题和变量维数

表6 测试问题和变量维数

图1 基于时间性能指标的对比图

为了进一步说明本文提出的DWYL共轭梯度算法和MDWYL共轭梯度算法适合大规模无优化问题,我们选取了CUTEr测试库中的40个无约束优化问题,其中测试函数的维数为50000,具体见表5和表6.图1的左侧代表DWYL共轭梯度算法和MDWYL共轭梯度算法以及WYL共轭梯度算法[14]和修正的WYL共轭梯度算法[15]的运行最快速度,右侧代表的是各个算法求解问题的成功率,上侧代表各个算法在规定的迭代终止条件下可以求解测试库中函数的数量.从图1知,本文提出的两类算法从收敛速度及CPU运行时间上均优于WYL 共轭梯度算法[14]和修正的WYL共轭梯度算法[15].因此,本文提出的两类算法不仅拥有很好的全局收敛特性而且数值试验效果也好于经典算法[14−15].

5.总结

本文提出了两类修正的WYL充分下降的共轭梯度法,算法在每次迭代过程中产生的搜索方向均为充分下降方向.在水平集有界和目标函数的梯度满足李普希兹函数连续条件下,证明了算法的全局收敛性.数值结果表明算法是可行、有效的.进一步的工作是如何把该类算法用于求解非凸优化问题是未来研究方向之一.另外,针对求解大规模的数值优化问题,把这些计算效率高的共轭梯度算法与智能优化算法相结合,充分发挥算法各自优点,提出快速收敛的混合优化算法也是未来主要研究工作.