A New Mixed Conjugate Gradient Method for Solving Unconstrained Optimization Problems

Tian-guo TANG

doi:10.13718/j.cnki.xsxb.2019.09.006

Based on existing conjugate gradient method, a new conjugate gradient method is proposed to solve the unconstrained optimization problem. An approximate method has been used to approximate the Hessen matrix and to overcome the problem of large computational complexity in the Hessen matrix of traditional Newton method. And under strong Wolfe line search, the global convergence of the conjugate gradient algorithm is proved. The experimental results show that, compared with the PRP(Polak-Ribiere-Polyak) method and HYBRID method based on BFGS(Broyden-Fletcher-Goldfarb-Shanno), the iterative time of the hybrid conjugate gradient algorithm proposed in this paper is less than that of former two methods, which shows that the method is feasible and effective.

HTML

最优化理论作为一门应用性强的学科，是运筹学的重要构成部分^[1]，而求解最优化方法的常用方法之一是共轭梯度法^[2]，其在算法收敛速度、存储需求等方面的综合性能要优于最速下降法和牛顿法，因此共轭梯度法用来求解无约束优化问题^[3]，特别是大规模的优化问题，在化学、经济和工程设计等领域具有较多应用，成为应用领域人员的热点研究对象.

对于连续可微函数f(x)，其无约束优化问题表示为$\min\limits _{x \in R} f(x)$，对于求解上述优化的函数共轭梯度法可用如下描述来表示：k为迭代次数，确定当前迭代点x_k的搜索方向d_k，该方向即为目标函数f(x_k)的下降方向，由搜索步长α_k得到下一个迭代点x_k+1=x_k+α_kd_k. g_k=▽(x_k)为梯度，则搜索方向与梯度的关系为

当式(1)中搜索方向确定，选择一个合适的搜索步长尤为关键，常见的线搜索方法有：标准Armijo法、Goldstein步长规则、Wolf步长规则和强Wolf步长规则等.

1.标准Armijo法，设β>0，γ∈(0，1)，取步长α_k=βγ^m_k，其中m_k是满足下式的最小非负整数

式(2)中σ∈(0，1).

2. Goldstein步长规则^[4]

式(3)中$\sigma \in\left(0, \frac{1}{2}\right)$，当α>0足够小的时候，第2个式子一定不成立.

3. Wolf步长规则

式(4)中0 < σ₁ < σ₂ < 1，α_k>0.

4.强Wolf步长规则

式(5)中$0 < \sigma_{1} < \sigma_{2} < \frac{1}{2}$，α_k>0.

共轭梯度算法中β_k为一个关键参数，常见的β_k选择方式主要有HS(Hestenes-Stiefel)，PRP，DY和CD(Conjuate-Descent)等方法，不同的共轭梯度法具有不同的β_k表达式，PRP方法和DY(Dai-Yuan)方法^[5-6]的表达式分别为

PRP方法在迭代速度方面具有优势，劣势就是全局收敛性差；DY方法则相反，其最大的优点即全局收敛性好，缺点为对搜索步长的要求较高.周雪琴^[7]给出了具有充分下降性的新共轭梯度法及全局收敛性，给出了一种新的β_k表达式，并证明了在强Wolfe搜索条件下的全局收敛性.何晓旭等^[8]将FR(Fletcher-Reeves)方法与PRP方法混合，新方法具有算法效率高，所需存储量小，不需要外来参数等优点，其公式为

车彩丽^[9]中给出了混合HS-DY共轭梯度算法，该算法的优点是具有更好的收敛性，且数值表现更优越、误差更小.刘玲等^[10]提出了一种带参数的混合共轭梯度算法，该算法的优点是不依赖线搜索的前提下，使得搜索方向满足充分下降条件，其缺点是在搜索过程中需要引入重新开始的策略，降低计算效率.常见的谱共轭梯度法公式为

本文对以上方法进行综合分析，并在此基础上提出了一种新混合共轭梯度法公式，该方法采用强Wolf步长搜索法则，解决了计算量大的问题，提高了计算效率，且具有全局收敛性和较好的数值特性.

2. 全局收敛性证明

对于全局收敛性，如果满足如下条件，则说明算法具有全局收敛性.满足条件：对于任意初始点，算法开始并产生的迭代能够收敛到最优.本文采用反证法来进行收敛性证明，具体描述如式(12).

如果满足上式，则认为算法为弱收敛，即满足条件：只有目标函数导数下界的极限需要接近零.在这里引入2个引理：

引理1 对该混合共轭梯度算法，步长选择法采用强Wolfe规则，则有如下表达式成立

证由于φ_k(α)=f(x_k+αd_k)在α>0时存在下界，故射线φ(α)=f(x_k)+σ₁αg_k^Td_k与φ_k(α)在正半轴上有交点，令该最小交点为α′，则有以下表达式成立

利用中值定理可得，存在α″∈(0，α′)使得式(15)成立

根据强Wolfe步长搜索条件，由式(14)和式(15)可得

由此可得g_k^Td_k < 0，引理1得证.

引理2 对于任意的k，有以下不等式成立

由数据归纳法可知，当k=0时d₀=-g₀，上式显然成立；先需要验证在k>0时该不等式也成立，则通过FR计算公式有

由引理1可得

利用归纳假设对上式中不等式右侧的项进行处理可得

由此，引理2得证.从引理2我们可得如下不等式

在全局收敛性的证明中还需要满足2个条件.

1.目标函数有界

2.函数f(x)连续可微，其导函数g(x)是Lipschitz连续的

首先由式(5)中强Wolf线性搜索步长规则可以得出

结合引理1与β_k-1的公式，可得d_k的递推表达式

将式(25)中的‖d_k-1‖²进行代换，由此可得反复的迭代不等式

根据式(12)，当满足式(12)中条件则认为该算法收敛，使用反证法来证明本文算法具有收敛性，首先假设不收敛，则存在一常数ε>0，使得式(27)成立

根据假设1可知g_k在水平集上有界，则对于r，ε满足式(28)中表达式

将式(28)对式(26)进行不等式放缩，得到式(29)成立

其中η为一常数.同时由引理2可知

由$\sigma_{2} < \frac{1}{2}$和式(31)可知常数τ>0，使得如下表达式成立

由于级数$\sum\limits_{k=0}^{\infty} \frac{1}{k+1}$是发散的，可以得到$\sum\limits_{k=0}^{\infty} \cos ^{2} \theta_{k}$也是发散的.另外，梯度函数g(x)满足Lipschitz连续条件，则有

从式(32)中可以得出

由强Wolf步长选择法则可得

对于以上证明过程可知，当数列f(x_k)是单调下降且有下界的，则‖g_k‖²cos²θ_k是收敛的.另外，由‖g_k‖≥ε，可得$\sum\limits_{k=0}^{\infty} \cos ^{2} \theta_{k}$是收敛的.这样的证明结果与结论相互矛盾，从而得到假设‖g_k‖≥ε是不成立的，本文算法的收敛性得证.

4. 结论

本文在已有共轭梯度算法求解无约束优化问题的基础上，提出了一种新混合共轭梯度方法，并给出了在强wolfe线搜索条件下的全局收敛性证明.实验结果表明，本文方法在迭代时间性能方面要优于PRP方法和HYBRID方法.

Figure (3) Table (1) Reference (10)

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]	王宜举, 修乃华.非线性最优化理论与方法[M].北京:科学出版社, 2012. Google Scholar
[2]	黎勇, 韦增欣.一种自动充分下降的共轭梯度法[J].西南师范大学学报(自然科学版), 2016, 41(5):36-40. Google Scholar
[3]	黄海.非线性无约束优化问题的新共轭梯度法[J].河南大学学报(自然科学版), 2014, 44(2):141-145. doi: 10.3969/j.issn.1003-4978.2014.02.004 CrossRef Google Scholar
[4]	焦宝聪, 陈兰平, 潘翠英.Goldstein线搜索下混合共轭梯度法的全局收敛性[J].计算数学, 2007, 29(2):137-146. doi: 10.3321/j.issn:0254-7791.2007.02.002 CrossRef Google Scholar
[5]	刘艳, 李雷.基于PRP共轭梯度的重构算法研究[J].计算机技术与发展, 2016, 26(8):55-59. Google Scholar
[6]	关哲, 于宪伟.标准Wolfe线搜索下修正的DY共轭梯度法[J].西南师范大学学报(自然科学版), 2016, 41(1):31-34. Google Scholar
[7]	周雪琴.一个新的PRP共轭梯度法的全局收敛性[J].重庆工商大学学报(自然科学版), 2015, 32(11):31-33. Google Scholar
[8]	何晓旭, 殷守林, 赵志刚.一种新的无优化约束问题的混合FR和PRP共轭梯度算法[J].沈阳师范大学学报(自然科学版), 2016, 34(1):92-95. doi: 10.3969/j.issn.1673-5862.2016.01.021 CrossRef Google Scholar
[9]	车彩丽.基于HS-DY共轭梯度算法的概率布尔网络解法研究[D].沈阳: 东北大学, 2014.http://cdmd.cnki.com.cn/Article/CDMD-10145-1016012081.htm Google Scholar
[10]	刘玲, 田志远, 商春雷.带参数的混合共轭梯度算法及其收敛性研究[J].青岛大学学报(自然科学版), 2016, 29(3):16-20, 24. Google Scholar

Message Board

A New Mixed Conjugate Gradient Method for Solving Unconstrained Optimization Problems

Abstract

References

Access History

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

Article Metrics

Access History

Other Articles By Authors