A New Hybrid Conjugate Gradient Algorithm

Xin HAN; Jun-rong ZHANG; Sen-sen WANG

doi:10.13718/j.cnki.xdzk.2017.05.020

Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

Based on some previous conjugate gradient algorithms, a new hybrid conjugate gradient algorithm is put forward for solving unconstrained optimization problems. This algorithm always generates a sufficient descent direction at each iteration. Furthermore, we show that the proposed algorithm possesses global convergence under the Wolfe line search. Finally, some numerical results are reported, which also demonstrate that our algorithm possesses good computational performance.

Corresponding author: Jun-rong ZHANG ;

Received Date: 27/03/2016

Available Online: 20/05/2017

Key words:

Abstract: Based on some previous conjugate gradient algorithms, a new hybrid conjugate gradient algorithm is put forward for solving unconstrained optimization problems. This algorithm always generates a sufficient descent direction at each iteration. Furthermore, we show that the proposed algorithm possesses global convergence under the Wolfe line search. Finally, some numerical results are reported, which also demonstrate that our algorithm possesses good computational performance.

HTML

考虑下面的无约束优化问题

其中f：ℝⁿ→ ℝ是连续可微函数，ℝⁿ表示n维欧氏空间，g是f的梯度向量，即g(x)=∇f(x).共轭梯度法是求解无约束优化问题(1) 的一种十分有效的算法.该算法的一般迭代格式如下：

这里α_k是由某种线搜索获得的迭代步长，并且

为搜索方向，β_k为共轭参数.迭代步长α_k通常由如下的Wolfe线搜索

或者强Wolfe线搜索

获得.这里δ与σ均为参数，且0＜δ＜σ＜1.对于共轭参数β_k的选取^[1-7]，有如下6种经典的形式：

其中：y_k-1=g_k-g_k-1，‖·‖代表欧氏范数.

上面的6种算法的全局收敛性和数值表现有所不同.众所周知，虽然FR法、DY法和CD法实际计算效果一般，但是它们具有很好的全局收敛性；另外，尽管PRP法、HS法和LS法在一般情形下可能不收敛，但是它们具有良好的数值表现.在以上方法的基础上，很多学者试着构造一种既具有好的收敛性质又具有优秀的数值表现的新算法.一种思路是直接对上面的共轭参数β_k进行改良，例如文献[8-10].另外就是将收敛性好和数值计算性能优良的方法进行有效混合，例如文献[11].

2006年，文献[8]提出了FR法的一种改进形式：

其中：μ₁∈(0，+∞)，μ₂∈(μ₁+ε₁，+∞)，μ₃∈(0，+∞)，且ε₁为给定的正参数.在任意线搜索条件下，该方法都具有充分下降性.

此后，文献[9]给出了HS法的一种改良公式：

在强Wolfe线搜索条件(5) 下，若0＜σ＜$ \frac{1}{3} $，则该算法能生成充分下降方向并且具有全局收敛性.

最近，基于文献[8]的想法，文献[10]引进了PRP法的一种修正形式：

其中参数μ＞1.在任意线搜索条件下，该方法都具有充分下降性.在Wolfe线搜索条件(4) 下，该算法具有全局收敛性.

受文献[8]和[10]的启示，本文提出了一种新的混合共轭梯度方法HZW法，其共轭参数如下：

其中参数u＞1.由(8) 式易得，β_k^HZW为β_k^DPRP，β_k^YWH，β_k^VFR和β_k^DY的一种混合.新的混合算法HZW法继承了DPRP法、YWH法、VFR法和DY法的优点，既具有好的全局收敛性又有出色的数值表现.

1. 新的混合型共轭梯度算法及其性质

基于(8) 式，我们将给出新的混合共轭梯度法HZW的算法步骤.

HZW算法

步骤0 给定初始点x₁和精度ε＞0.令k：=1，并计算d₁=g₁.

步骤1 若‖g_k‖≤ε，停止.否则，转步骤2.

步骤2 按Wolfe线搜索(4) 式，计算迭代步长α_k.

步骤3 由x_k+1=x_k+α_kd_k，g_k+1=g(x_k+1)生成新的迭代点并根据(8) 式计算β_k+1^HZW.

步骤4 由d_k+1=-g_k+1+β_k+1^HZWd_k计算新的搜索方向.令k：=k+1，转步骤1.

下面，我们将给出算法HZW中的共轭参数β_k^HZW所具有的性质.

引理1 若共轭参数β_k^HZW由(8) 式定义，则

证根据β_k^HZW的定义，有

另一方面，对β_k^HZW适当放大，就有

综上，结论得证.

下面的引理将说明算法HZW具有充分下降性.

引理2 若目标函数f(x)是光滑的.设{g_k}和{d_k}是由算法HZW生成的序列.则

对任意的k≥1都成立，其中c和u均为参数，且c=1-$ \frac{1}{u}$，u＞1.

证由β_k^HZW的定义和(9) 式，可知

结合(3) 式，有

从而，结论得证.

2. 全局收敛性

为了证明算法HZW的全局收敛性，下面给出一些标准假设：

假设A 目标函数f(x)的水平集ℒ={x∈ℝⁿ：f(x)≤f(x₁)}有界，其中x₁为所给的初始点.

假设B 在ℒ的某个邻域$\mathcal{N} $内，目标函数f(x)在$\mathcal{N} $上连续可微且导函数g(x)在$\mathcal{N} $上Lipschitz连续，即存在常数L＞0，使得

接下来给出著名的Zoutendijk条件.该引理经常被用来证明共轭梯度算法的全局收敛性.

引理3^[12] 假设A和B都成立.考虑形如(2) 式和(3) 式的任意迭代算法，若搜索方向d_k是一个下降方向，步长α_k满足Wolfe线搜索条件(4)，则

根据(11) 式，不难得到与Zoutendijk条件(13) 等价的不等式

现在，我们建立算法HZW的全局收敛定理.

定理1 假设A和B都成立. {g_k}和{d_k}是由算法HZW生成的序列，则

证假设(15) 式不成立，即存在常数r＞0以及无穷多个k，有

在(3) 式中，令β_k=β_k^HZW.当k≥2时，对(3) 式两边取模的平方，可得

由β_k^HZW的定义和(12) 式，可知

将(10) 式和(18) 式应用到(17) 式中，有

(19) 式两边同时除以‖g_k‖⁴，可得

对(20) 式，使用递归法.并注意到

就有

结合(16) 式和(21) 式，有

(22) 式说明

这与(14) 式相矛盾，也即与引理3矛盾.因此，原结论成立.

3. 数值实验

为了清楚的检验算法HZW的实际计算效果利用文献[13]中的11个测试函数进行数值测验.现将要比较的算法，一一列举如下：

DY：戴彧虹和袁亚湘^[2]提出的经典算法，共轭参数β_k=β_k^DY；

YWH：文献[9]引进的算法，共轭参数β_k=β_k^YWH由(6) 式给出；

DPRP：文献[10]定义的算法，共轭参数β_k=β_k^DPRP由(7) 式给出；

HZW：本文所提出的算法，共轭参数β_k=β_k^HZW由(8) 式确定.

实验采用Wolfe线搜索条件(4)，并且均利用MATLAB编程实现.算法测试的环境是Windows 7操作系统，AMD Athlon(tm) Ⅱ Dual-Core M320 2.00 GB内存.算法中参数取值为：u=1.1，δ=0.000 1，σ=0.1.终止条件为：‖g_k‖≤10^-7，或者算法的迭代时间超过3 600 s.将HZW算法与DPRP，YWH以及DY法进行比较，20个算例详细报告见表 1.在表 1中：F为测试函数的名称；M为共轭梯度算法的名称；n为测试函数的维数；I为算法解决某一测试问题的迭代次数；T为算法解决某一测试问题的计算时间；N_g为算法解决某一测试问题的最终梯度范数，即‖g_k‖；S为若算法的终止条件满足，令S=1，否则，令S=0.

表 1的测试结果表明，算法HZW的计算性能比另外3种算法要好得多.另外，DPRP法在求解120维dixmaane问题与dixmaang问题时迭代失败，DY法在求解120维dixmaang问题和1 000维raydan2问题时迭代失败，但HZW法和YWH法均迭代成功.

4. 结论

本文构造的算法HZW，在任何线搜索条件下，都具有充分下降性.采用Wolfe线搜索时，算法HZW具有良好的全局收敛性，且在实际计算中，具有出色的数值表现.

Table (1) Reference (13)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	FLETCHER R, REEVES C. Function Minimization by Conjugate Gradients[J]. Computer Journal, 1964, 7(2): 149-154. doi: 10.1093/comjnl/7.2.149 CrossRef Google Scholar
[2]	DAI Y H, YUAN Y X. A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property[J]. SIAM Journal of Optimization, 2000, 10(1): 177-182. Google Scholar
[3]	FLETCHER R. Practical Methods of Optimization, Unconstrained Optimization[M]. New York: John Wiley and Sons, 1987. Google Scholar
[4]	POLAK E, RIBIÉRE G. Note Sur La Convergence De Directions Conjuguéee[J]. Rev Francaise Infromat Recherche Operationelle 3e Année, 1969, 16(16): 35-43. Google Scholar
[5]	POLIAK B T. The Conjugate Gradient Method in Extreme Problems[J]. USSR Computational Mathematics and Mathematical Physics, 1969, 9(4): 94-112. doi: 10.1016/0041-5553(69)90035-4 CrossRef Google Scholar
[6]	HESTENES M R, STIEFEL E L. Methods of Conjugate Gradients for Solving Linear Systems[J]. Journal of Research of National Bureau of Standards, 1952, 49(6): 409-436. doi: 10.6028/jres.049.044 CrossRef Google Scholar
[7]	LIU Y, STOREY C. Efficient Generalized Conjugdte Gradient Algorithms[J]. Journal of Optimization Theory Application, 1991, 69(1): 129-137. doi: 10.1007/BF00940464 CrossRef Google Scholar
[8]	WEI Z, LI G, QI L. New Nonlinear Conjugate Gradient Formulas for Large-Scale Unconstrained Optimization Problems[J]. Applied Mathematics and Computation, 2006, 179(2): 407-430. doi: 10.1016/j.amc.2005.11.150 CrossRef Google Scholar
[9]	YAO S W, WEI Z X, HUANG H. A Note about WYL's Conjugate Gradient and Its Application[J]. Applied Mathematics and Computation, 2007, 191(2): 381-388. doi: 10.1016/j.amc.2007.02.094 CrossRef Google Scholar
[10]	DAI Z F, WEN F H. Another Improved Wei-Yao-Liu Nonlinear Conjugate Gradient Method with Sufficient Descent Property[J]. Applied Mathematics and Computation, 2012, 218(14): 7421-7430. doi: 10.1016/j.amc.2011.12.091 CrossRef Google Scholar
[11]	JIAN J B, HAN L, JIANG X Z. A Hybrid Conjugate Gradient Method with Descent Property for Unconstrained Optimization[J]. Applied Mathematical Modelling, 2014, 39(3-4): 1281-1290. Google Scholar
[12]	GILBERT J C, NOCEDAL J. Global Convergence Properties of Conjugate Gradient Methods for Optimization[J]. SIAM Journal of Optimization, 1992, 2(1): 21-42. doi: 10.1137/0802003 CrossRef Google Scholar
[13]	ANDREI N. An Unconstrained Optimization Test Functions Collection[J]. Advanced Modeling and Optimization, 2008, 10(1): 147-161. Google Scholar

Message Board

A New Hybrid Conjugate Gradient Algorithm

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors