下载: -
考虑下面的无约束优化问题
其中f：ℝn→ ℝ是连续可微函数，ℝn表示n维欧氏空间，g是f的梯度向量，即g(x)=∇f(x).共轭梯度法是求解无约束优化问题(1) 的一种十分有效的算法.该算法的一般迭代格式如下：
这里αk是由某种线搜索获得的迭代步长，并且
为搜索方向，βk为共轭参数.迭代步长αk通常由如下的Wolfe线搜索
或者强Wolfe线搜索
获得.这里δ与σ均为参数，且0＜δ＜σ＜1.对于共轭参数βk的选取[1-7]，有如下6种经典的形式：
其中：yk-1=gk-gk-1，‖·‖代表欧氏范数.
上面的6种算法的全局收敛性和数值表现有所不同.众所周知，虽然FR法、DY法和CD法实际计算效果一般，但是它们具有很好的全局收敛性；另外，尽管PRP法、HS法和LS法在一般情形下可能不收敛，但是它们具有良好的数值表现.在以上方法的基础上，很多学者试着构造一种既具有好的收敛性质又具有优秀的数值表现的新算法.一种思路是直接对上面的共轭参数βk进行改良，例如文献[8-10].另外就是将收敛性好和数值计算性能优良的方法进行有效混合，例如文献[11].
2006年，文献[8]提出了FR法的一种改进形式：
其中：μ1∈(0，+∞)，μ2∈(μ1+ε1，+∞)，μ3∈(0，+∞)，且ε1为给定的正参数.在任意线搜索条件下，该方法都具有充分下降性.
此后，文献[9]给出了HS法的一种改良公式：
在强Wolfe线搜索条件(5) 下，若0＜σ＜
$ \frac{1}{3} $ ，则该算法能生成充分下降方向并且具有全局收敛性.最近，基于文献[8]的想法，文献[10]引进了PRP法的一种修正形式：
其中参数μ＞1.在任意线搜索条件下，该方法都具有充分下降性.在Wolfe线搜索条件(4) 下，该算法具有全局收敛性.
受文献[8]和[10]的启示，本文提出了一种新的混合共轭梯度方法HZW法，其共轭参数如下：
其中参数u＞1.由(8) 式易得，βkHZW为βkDPRP，βkYWH，βkVFR和βkDY的一种混合.新的混合算法HZW法继承了DPRP法、YWH法、VFR法和DY法的优点，既具有好的全局收敛性又有出色的数值表现.
全文HTML
-
基于(8) 式，我们将给出新的混合共轭梯度法HZW的算法步骤.
HZW算法
步骤0 给定初始点x1和精度ε＞0.令k：=1，并计算d1=g1.
步骤1 若‖gk‖≤ε，停止.否则，转步骤2.
步骤2 按Wolfe线搜索(4) 式，计算迭代步长αk.
步骤3 由xk+1=xk+αkdk，gk+1=g(xk+1)生成新的迭代点并根据(8) 式计算βk+1HZW.
步骤4 由dk+1=-gk+1+βk+1HZWdk计算新的搜索方向.令k：=k+1，转步骤1.
下面，我们将给出算法HZW中的共轭参数βkHZW所具有的性质.
引理1 若共轭参数βkHZW由(8) 式定义，则
证 根据βkHZW的定义，有
另一方面，对βkHZW适当放大，就有
综上，结论得证.
下面的引理将说明算法HZW具有充分下降性.
引理2 若目标函数f(x)是光滑的.设{gk}和{dk}是由算法HZW生成的序列.则
对任意的k≥1都成立，其中c和u均为参数，且c=1-
$ \frac{1}{u}$ ，u＞1.证 由βkHZW的定义和(9) 式，可知
结合(3) 式，有
从而，结论得证.
-
为了证明算法HZW的全局收敛性，下面给出一些标准假设：
假设A 目标函数f(x)的水平集ℒ={x∈ℝn：f(x)≤f(x1)}有界，其中x1为所给的初始点.
假设B 在ℒ的某个邻域
$\mathcal{N} $ 内，目标函数f(x)在$\mathcal{N} $ 上连续可微且导函数g(x)在$\mathcal{N} $ 上Lipschitz连续，即存在常数L＞0，使得接下来给出著名的Zoutendijk条件.该引理经常被用来证明共轭梯度算法的全局收敛性.
引理3[12] 假设A和B都成立.考虑形如(2) 式和(3) 式的任意迭代算法，若搜索方向dk是一个下降方向，步长αk满足Wolfe线搜索条件(4)，则
根据(11) 式，不难得到与Zoutendijk条件(13) 等价的不等式
现在，我们建立算法HZW的全局收敛定理.
定理1 假设A和B都成立. {gk}和{dk}是由算法HZW生成的序列，则
证 假设(15) 式不成立，即存在常数r＞0以及无穷多个k，有
在(3) 式中，令βk=βkHZW.当k≥2时，对(3) 式两边取模的平方，可得
由βkHZW的定义和(12) 式，可知
将(10) 式和(18) 式应用到(17) 式中，有
(19) 式两边同时除以‖gk‖4，可得
对(20) 式，使用递归法.并注意到
就有
结合(16) 式和(21) 式，有
(22) 式说明
这与(14) 式相矛盾，也即与引理3矛盾.因此，原结论成立.
-
为了清楚的检验算法HZW的实际计算效果利用文献[13]中的11个测试函数进行数值测验.现将要比较的算法，一一列举如下：
DY：戴彧虹和袁亚湘[2]提出的经典算法，共轭参数βk=βkDY；
YWH：文献[9]引进的算法，共轭参数βk=βkYWH由(6) 式给出；
DPRP：文献[10]定义的算法，共轭参数βk=βkDPRP由(7) 式给出；
HZW：本文所提出的算法，共轭参数βk=βkHZW由(8) 式确定.
实验采用Wolfe线搜索条件(4)，并且均利用MATLAB编程实现.算法测试的环境是Windows 7操作系统，AMD Athlon(tm) Ⅱ Dual-Core M320 2.00 GB内存.算法中参数取值为：u=1.1，δ=0.000 1，σ=0.1.终止条件为：‖gk‖≤10-7，或者算法的迭代时间超过3 600 s.将HZW算法与DPRP，YWH以及DY法进行比较，20个算例详细报告见表 1.在表 1中：F为测试函数的名称；M为共轭梯度算法的名称；n为测试函数的维数；I为算法解决某一测试问题的迭代次数；T为算法解决某一测试问题的计算时间；Ng为算法解决某一测试问题的最终梯度范数，即‖gk‖；S为若算法的终止条件满足，令S=1，否则，令S=0.
表 1的测试结果表明，算法HZW的计算性能比另外3种算法要好得多.另外，DPRP法在求解120维dixmaane问题与dixmaang问题时迭代失败，DY法在求解120维dixmaang问题和1 000维raydan2问题时迭代失败，但HZW法和YWH法均迭代成功.
-
本文构造的算法HZW，在任何线搜索条件下，都具有充分下降性.采用Wolfe线搜索时，算法HZW具有良好的全局收敛性，且在实际计算中，具有出色的数值表现.