一种新的无优化约束问题的混合FR和PRP共轭梯度算法

2016-03-31何晓旭殷守林赵志刚

沈阳师范大学学报(自然科学版) 2016年1期

关键词：共轭收敛性沈阳

何晓旭, 殷守林, 赵志刚

(沈阳师范大学科信软件学院, 沈阳 110034)

一种新的无优化约束问题的混合FR和PRP共轭梯度算法

何晓旭, 殷守林, 赵志刚

(沈阳师范大学科信软件学院, 沈阳 110034)

混合共轭梯度法; 线性搜索; 收敛性分析

0 引言

对于无优化问题,混合共轭梯度法在寻找最优解方面起着很大的作用。问题可以描述为

(1)

其中,f:Rn→R是连续可微的目标函数。对于解决大规模无优化问题,混合梯度法是首选的一种方法,因为不像牛顿或者拟牛顿法[1-2],它们只需要一阶导数,因此只需要较少的存储容量。而且他们也相对很容易编程。给定一个初始值x0∈Rn,混合梯度法产生对于式(1)的一个序列{xk},用下述方式表示:

(2)

其中,αk是线性搜索确定的一个步长,dk是在xk位置目标函数的下降方向。αk可以由执行一个确切或者不确切的一维线性搜索过程获得。如果对于一个确切的线性搜索,那么αk可以是

(3)

如果对于不确切的线性搜索,在Amirjo条件下,需要αk满足条件

(4)

和标准的Wolfe条件,也需要满足公式(4)和曲率条件

(5)

其中,0<μ<σ<1。强Wolfe条件用于很多文章,由式(4)和式(6)给出。

(6)

混合梯度法的搜索方向dk可以由式(7)得到。

(7)

其中,gk=f(xk)是f的梯度在xk位置,βk是一个标量,被称为共轭梯度系数。不同的共轭梯度系数选择导致不同的共轭梯度法。一些应用比较广泛的共轭梯度法包括)共轭算法[3-4],Polak-Ribiè)共轭算)共轭算)共轭算法[9],conjugate)共轭算法,)共轭算法[10]。所列文献展示了二元函数是等价的,但是它们的性能还是依靠系数βk。共轭梯度法和拥有强大的全局收敛性性[11-12],但是它们有更少的计算性能;另一方面,和方法不总是收敛,但是表现出良好的计算性能[13-14]。

1 新的混合共轭梯度算法

(8)

(9)

(10)

第2步使用任意一个线性搜索方法计算αk>0,并找到下一个迭代。xk+1=xk+αkdk,计算f(xk+1),gk+1=f(xk+1),如果‖gk+1‖≤ε,算法停止。

第4步令k=k+1,返回执行第二步。

2 收敛性分析

为验证新方法的收敛性,做如下关于在很多混合梯度算法中的应用分析收敛性目标函数的基本假设。

假设1f在水平集合S={x∈Rn:f(x)≤f(x0)}上有下界,x0是初始点。

假设2 在一些S的邻居点N,函数f是连续可微的梯度函数。g(x)=f(x)是利普希茨连续,也就是说存在一个常数L>0,对于所有的x,y∈N使‖g(x)-g(y)‖≤L‖x-y‖。

引理上述两点假设存在的条件下,以xk+1=xk+αkdk此格式和式(7)为基础,并且在dk时下降方向,步长αk满足标准Wolfe条件(4)、(5)情况下,混合共轭梯度算法可以得到

(11)

3 数值结果

表1 4种方法数值结果

图1 函数评价次数性能概况

为了更好地比较4种算法的数值效果,使用性能配置属性,在图1中有展示,其中的功能评估性能由曲线绘制。令P={p1,…,p14}是所有问题的集合,S={s1,s2,s3,s4}是4种算法集合。令ap,s代表性能测量次数,所以可以得出一个性能比值公式:rp,s=ap,s/min{ap,s:s∈S}。

4 结论

在未来研究中将进一步开发更多混合共轭梯度法解决大规模无约束优化问题。虽然低维的测试问题主要用于测试本文新的算法,未来会在算法中向更高维层面延伸。另一个方向是扩展共轭梯度法来约束优化问题以及最优控制问题。

[1]冯冬冬. 一类精细修正牛顿法和拟牛顿法研究[D]. 长沙:中南大学, 2012.

[2]ANTNIOU A,LU W S. Practical optimization, algorithms and engeneering applications[M]. New York:Springer, 2007.

[3]WEI Zengxin, HUANG Haidong, TAO Yanrong. A modified hestenes-stiefel conjugate gradient method and its convergence[J]. 数学研究与评论, 2010,30(2):297-308.

[4]戚后铎,韩继业,刘光辉. 修正Hestenes-Stiefel共轭梯度算法[J]. 数学年刊A辑:中文版, 1996(3):277-284.

[5]A Globally Convergent Polak-Ribiere-Polyak Conjugate Gradient Method with Armijo-Type Line Search[J]. Numerical Mathematics A Journal of Chinese Universities(English Series), 2006,04(15):357-366.

[6]段侠彬,袁功林,王晓亮,等. 一种含参数的修正HS共轭梯度法及其收敛性[J]. 广西大学学报(自然科学版), 2015,40(3):750-757.

[7]马国栋,简金宝,江羡珍. 一个具有下降性的改进Fletcher-Reeves共轭梯度法[J]. 应用数学学报, 2015,1(38):89-97.

[8]张静. 一类新的修正Fletcher-Reeves算法[J]. 安徽大学学报(自然科学版), 2009,33(3):31-35.

[9]胡亚萍. 非线性单调方程组和非光滑优化问题的算法研究[D]. 上海：华东理工大学, 2015.

[10]张劲松,李红. 含参数Dai-Yuan共轭梯度法及其收敛性[J]. 华东交通大学学报, 2008,1(25):127-129.

[11]BAAIE-KAFAKI S. A hybrid conjugate gradient method based on a quadratic relaxation of the Dai-Yuan Hybrid conjugate gradient parameter[J]. Optimization, 2013,62(7):929-941.

[12]DAI Y H. Convergence of conjugate gradient methods with constant step sizes[J]. Optimization Methods and Software, 2011,26(6):895-909.

[13]HAGER W, ZHANG H. A survey of nonlinear conjugate gradient methods[J]. Pacific Journal of Optimization, 2006(2):35-58.

[14]GILBET J, NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992,2(1):21-42.

A new hybrid conjugate gradient FR and PRP method for unconstrained optimization problems

HEXiaoxu,YINShoulin,ZHAOZhigang

(Software College, Shenyang Normal University, Shenyang 110034, China)