1. 引言
本文考虑求解如下无约束优化问题
(1.1)
其中
连续可微,此问题在经济管理、生产运作、工程设计等领域具有广泛的应用背景。共轭梯度法是求解问题(1.1)的有效方法之一,该方法具有算法结构简单、计算存储量少、数值效果明显的优点,其迭代公式的一般形式为:
其中
为第
次迭代点,
为搜索步长,
为搜索方向且其更新方式为
(1.2)
其中
是方向调控参数。数值优化方法是根据搜索方向的选择来定义其方法类型,从上式可以看出,搜索方向
是由参数
决定的,所以根据
的选取方式可以定义不同的共轭梯度公式,下面给出几个著名的公式:
[2] [3] ,
[4] ,
[5] ,
[6] ,
[7] ,
[8] ,
其中
和
表示函数
在
和
的梯度值,
是欧氏向量范数。众多优化专家都希望能找到理论性质良好且数值表现又好的算法,已取得众多成果(见 [9] - [25] ),其中Yuan [9] 给出如下PRP修改公式:
其中
是常数,
,同时又将此公式推广到了其它5个公式中,得到了修改的FR公式、修改的HS公式、修改的DY公式、修改的CD公式和修改的LS公式,其中文 [1] 修改的LS为:
, (1.3)
其中
,
。
本文将在此公式的基础上进一步研究,从上式可以看出公式中不含函数值信息,这势必影响此方法的有效性。众所周知,拟牛顿方法不仅含有梯度值信息也含有函数值信息,且具有更好的理论和实际表现 [10] [11] 。也有许多学者将拟牛顿法的技术思想应用到共轭梯度公式中,从而获得更好的理论性质和实际数值效果 [12] [13] 。Zhang等 [11] 给出了一个如下形式的拟牛顿方程
, (1.4)
其中
,
及
此公式包含有梯度值信息和函数值信息,理论上能更高阶地近似目标函数的Hesse矩阵。基于公式(1.3),(1.4)和文 [12] [13] 的思想,本文给出如下修改的LS共轭梯度公式
,(1.5)
其中
。相对于原LS方法,本文的创新点主要有:1) 新公式能保证方向调控参数
;2) 新方法具有充分下降性;3) 新方法不仅使用了梯度值信息还有函数值信息。
2. 算法的描述
基于搜索方向,给出一个基于拟牛顿方程改进的非线性共轭梯度算法。
算法1:
步骤0:给定
,
,令
,置
。
步骤1:若
,停止。否则,进入步骤2。
步骤2:利用弱Wolfe-Powell(WWP)线搜索技术产生步长
(2.1)
(2.2)
步骤3:令
。如果
,停止。
步骤4:利用公式(1.5)计算
,并按如下公式计算搜索方向
(2.3)
步骤5:置
,转步骤2。
3. 算法的充分下降性和全局收敛性
引理3.1:对所有
,搜索方向
满足下面两式
(3.1)
和
(3.2)
是常数。
证明:首先证明(3.1)成立。根据算法1,如果
,则
,式(3.1)显然成立。下面利用归纳法,当
,假如公式(2.3)满足(3.1),对
,有
(3.3)
由
取
。下面我们分两种情形分别讨论(3.3)式:
情形I:如果
,显然
成立。
情形II:如果
,(3.3)式可化为
上述不等式利用了
的关系。取
,则(3.1)成立。根据线搜索技术(2.2)可推出(3.2)也成立。证毕。
我们将采用反证法来证明算法1的全局收敛性,假设存在常数
满足
(3.4)
根据(3.4)导出矛盾,从而证明
成立。
为证明算法1的收敛性,还需要下面的常规假设条件。
假设A:1) 定义水平集
且有界,存在
满足
2) 目标函数
在水平集
上连续可微并有下界,目标函数梯度满足Lipschitz条件,所谓Lipschitz条件就是存在常数
满足下式
。 (3.5)
下面引理3.2和引理3.3在共轭梯度算法文献中有类似的结论,本文只给出引理3.3证明过程。
引理3.2:设假设A成立,序列
和
由算法1产生,则
及
,其中
。
Gilbert和Nocedal [14] 给出下面性质(P),具体内容是:
性质(P)对于两参数
,且满足
。 (3.6)
若对所有
,存在常数
和
满足
和
,有
成立。
引理3.3:如果假设A满足且序列
和
由算法1产生,且存在常数
使得
成立,则
满足性质(P)。
证明:对于公式(2.3),如果
成立,结论显然成立。否则,利用假设A(1),可推出存在常数
使下式
(3.7)
成立。利用
,(3.1),(3.2),(3.5)~(3.7),有
取
和
利用(3.8),
和
,则
和
因此公式(2.3)满足性质(P),引理得证。
利用假设A,引理3.1~3.3,与文献 [15] 中的定理3.2的证明类似,可得到算法1的全局收敛性定理,定理的证明请参照文献 [15] 中的定理3.2完成。
定理3.1:序列
由算法产生,若假设A成立,则
成立。
4. 数值结果
这部分将给出数值检验,Benchmar问题 [16] 在工程领域具有广泛应用背景。
1) Sphere函数:
2) Schwefel’s函数:
3) Rastrigin函数:
4) Griewank函数:
参数选取如下:
,停止准则采用Himmeblau准则:如果
,令
;否则,令
。如果
或者
满足,算法终止,
。若迭代次数超过1000次,程序也将终止。为比较算法1的有效性,也给出通常LS方法的数值检验,并进行比较。以下是各代码含义:
:初始点;Dim:问题的维数;NI:迭代次数;NFG:函数值与梯度值迭代次数和;Time:以秒为单位的计算机CPU时间;
:算法终止时的函数值。
为比较算法1与原LS算法的效率,我们采用下述技术即两算法的所有NFG的乘积的比值再开二十四分之一(结果的总个数)次方,以通常LS算法作为底,定义为1,比值见表2,此技术见文献 [17] 。
从表1的结果可看,算法1和LS算法对上述4个问题都能有效地求解,迭代次数可以接受,最终函数值很接近最优函数值,新算法的CPU时间相对少一些,更具竞争力。表2的效率表明,算法1相对于原LS算法,效率提高2%。
基金项目
2017年国家级大学生创新创业训练计划项目(201710606041),广西自然科学基金(2018JJA110039)和玉林师范学院校级科研项目(2019YJKY16)。
NOTES
*第一作者。
#通讯作者。