文摘
共轭梯度法是一种有效的方法解决大规模非线性优化问题。在本文中,我们提出一种非线性共轭梯度方法可以被认为是一个混合的DL和WYL共轭梯度方法。给定的方法具有充分下降条件下Wolfe-Powell线搜索和全局收敛的一般功能。我们的数值结果表明,该方法很健壮和高效的测试问题。
1。介绍
非线性共轭梯度(CG)方法发挥了特殊作用在解决大规模非线性优化的简单迭代和非常低的内存需求。事实上,CG方法并不在最快或最健壮的现有优化算法对非线性问题,但它仍然是非常受欢迎的工程师和数学家解决大规模问题感兴趣。正如我们所知,非线性共轭梯度法是扩展的基于线性共轭梯度法。第一个提出的线性共轭梯度法是Hestenes和施蒂费尔19521求解线性方程组。1964年,弗莱彻和里夫斯(2)扩展到非线性问题和获得第一个非线性共轭梯度法(FR方法)。
在本文中,我们专注于解决非线性无约束优化问题的共轭梯度法: 在哪里是一个光滑、非线性函数的梯度会用吗。给出了共轭梯度法的迭代公式 在那里,搜索方向在哪里和步长。对于非线性共轭梯度方法,是计算 在哪里是一个标量和表示渐变。不同的共轭梯度方法对应不同的计算方法。一些著名的公式Fletcher-Reeves (FR), Polak-Ribiere (PR), Hestense-Stiefel (HS), Dai-Yuan (DY)和CG-DESCENT给出,分别 (见[2]), (见[3]), (见[1]), (见[4]), (见[5]),表示梯度变化。
尽管所有这些方法在线性情况下是等价的,即当是一个严格凸二次函数,是由精确线搜索,决定他们的行为对于总目标函数可能截然不同。通用函数,Zoutendijk [6]证明了FR方法的全局收敛性和精确线搜索。(在这里,在这篇文章中,全局收敛性,我们指的是序列生成的相应的方法将终止在有限步骤或包含子序列,使其收敛于目标函数的驻点从一个给定的初始点)。虽然一个是满意其全局收敛特性,FR方法执行比公关(HS)方法在实际计算。鲍威尔(7]分析了主要的数值FR方法的缺点,即如果生成一小步远离解决方案,后续步骤可能也很短。另一方面,在实际计算中,HS方法类似于公关方法,这两种方法通常被认为是最有效的自共轭梯度方法这两种方法本质上执行重启如果出现坏的方向。但是,鲍威尔(8)建造了一个反例表明,公关方法和HS方法可以无限循环而不接近的解决方案。这个例子表明,这两种方法有一个缺点,他们不是全局收敛的一般功能。因此,在过去的几年里,了很多努力找出新的共轭方法的公式,使他们不仅是全局收敛的一般功能,还具有良好的数值性能。类似的例子也由戴秉国和元(9]。
从上面的公式的结构,我们知道和有共同的分子。他们是全局收敛,如果目标函数李普希兹连续和水平集是有界的。不精确线搜索,Al-Baali [10]证明了FR方法的全局收敛性强下Wolfe-Powell线搜索的限制。基于Al-Baali的结果,刘等人。11]扩展FR方法的全局收敛性。戴和元12]证明了充分下降条件必须持有的方向和,并提出FR方法的全局收敛性和乌尔夫将军行搜索。
和分享共同的分子,他们拥有一个内置的重启功能来避免干扰问题如下:当一步很小,因素在分子上的往往是零。因此,下一个搜索方向本质上是最速下降方向。因此,这些方法比的数值性能方法的性能分子的。在[3波兰人和Ribiere证明如果强烈凸目标函数和线搜索是确切的,公关方法是全局收敛的。通用函数,鲍威尔(7,8]分析了公关方法的收敛特性和建造一个例子表明,公关方法可能周期无限之间的非平稳点。全局收敛性,吉尔伯特和Nocedal [13)提出以下非负限制:
一般来说,与分子的方法具有更好的收敛性与分子的方法。但从数值性能的观点、方法与分子比分子的方法。所以,很多努力已经找到方法有很好的收敛性质和有效的数值性能在过去几十年。在[14),作者提出了一种新的共轭性条件的利用不仅梯度值,而且函数值。基于给定的共轭性条件,提出了一类非线性共轭梯度方法。公关方法优于很多方法在数值实验中,但它并不拥有充分下降条件。因此,一些修改形式的公关方法研究了在15,16),给定的方法具有充分下降条件和全局收敛的一般功能。
2。动机和新配方
的公关方法被认为是一个最有效的非线性共轭梯度方法,很多努力已经取得了对其收敛性能及其修改。在[13),足够的血统的假设,吉尔伯特和Nocedal公关+方法的全局收敛性证明沃尔夫线搜索下。Grippo和Lucidi17构造一个Armijo-type线搜索和证明这条线搜索下,方向生成的公关方法满足充分下降条件。
最近,魏et al。18和黄等。19]给出了修正公式计算如下: 在哪里。
公式的方法不仅具有很好的数值结果也具有充分下降条件下和全局收敛性能强Wolfe-Powell行搜索。的结构我们知道的方法也可以避免干扰,这样当一步很小,往往是1和下一个搜索方向往往是相似的最速下降方向方法。但WYL方法有一些优点,比如强Wolfe-Powell线搜索下,,如果参数在SWP, WYL方法具有充分下降条件推导出WYL方法的全局收敛性。
在[20.,21),Shengwei等人,黄等人长这样的修改方法如下: 上面的公式和可以被视为修改形式的吗和通过使用来代替,分别。在[20.,21),相应的方法被证明是全局收敛的一般功能强大Wolfe-Powell线搜索和Grippo-Lucidi线搜索下。基于相同的方法,一些作者扩展其他讨论和修改22- - - - - -24]。事实上,不是我们点一开始,我们的目的是涉及信息之间的角和。从这个角度来看,有以下形式: 在哪里之间的角和。乘以与,该方法不仅具有相似的收敛性质方法,但也避免类似的干扰方法。
最近,戴和廖25)提出了一种新的基于拟牛顿方法共轭性条件。根据新的共轭性条件,下面的公式给出: 在哪里,为简单起见,我们调用的方法(13)作为DL1方法。这显然是 在[25)的方法、如果精确线搜索DL1方法具有相同的收敛性质与公关方法,这表明DL1方法不收敛的一般功能。全局收敛性,戴和廖取代(13) 公式(15)可以被视为一种修改的,通过添加部分海赛可能包含一些信息(25]。从收敛性分析(25),非负限制和充分下降条件是重要的全局收敛性结果。
出于上述的讨论,在这篇文章中,我们给出以下公式计算参数:
这个公式可以考虑修改吗,即通过添加,可能包含一些黑森信息(25]。它也可以被认为是一种修改的用与。我们调用的方法(2),(3)和(16)作为WYLDL方法并给出相应的算法如下。
算法1 (WYLDL)。
一步1。鉴于,设置,,如果,然后停止;
一步2。计算的强大Wolfe-Powell线搜索;
一步3所示。让,,如果,然后停止;
一步4所示。计算由(16)并生成由(3);
一步5。集,转到步骤2。
3所示。收敛性分析
对共轭梯度方法,在迭代过程中,目标函数的梯度是必需的。我们做出以下基本假设目标函数。
假设2。(我)水平集是有界的,即存在一个常数这样
(2)在一些社区的,是连续可微的,其梯度李普希茨是连续的,也就是说,存在一个常数这样
在上述假设条件下的,存在一个常数这样
精确线搜索。假设是一个下降方向和步长的解决方案是
为精确线搜索,
形式(16)和(21),我们可以得到。在[18),作者证明了如果精确线搜索方法一致凸函数是全局收敛的。
对于共轭梯度方法,充分下降条件对全局收敛性具有重要意义。我们说的充分下降条件如果存在一个常数这样
在非线性优化算法,强烈Wolfe-Powell条件,即
在哪里,往往对搜索。
在[25),戴秉国和廖证明,如果方向满足充分下降条件(22),DL方法是全局收敛的强劲Wolfe-Powell线搜索下通用功能。在本节中,我们将证明方向由算法生成1满足充分下降条件(22)。基于这个结果,算法的全局收敛性1将被建立。
引理3。假设序列由算法生成1,步长满足强劲Wolfe-Powell条件(23)和(24),如果;然后,生成的方向满足充分下降条件(22)。
证明。我们用归纳法证明这个结果。通过使用(3),我们有,结合方程(),我们可以推断出 由强烈的Wolfe-Powell条件(24),它遵循。这意味着 从(25),下面的不平等是适用的: (25)和Wolfe-Powell条件(24)推断出 也就是说, (重复的29日)可以推断出 自 (30.)可以表示为 与限制和,因为不平等(32)意味着
对于公关方法,当发生小的步长时,将趋向于零,下一个搜索方向自动的方法。通过这种方式,公关方法自动避免干扰。这个属性是第一个研究了吉尔伯特和Nocedal [13),叫做属性()。我们要显示的方法拥有这样的属性()。
属性1。()考虑方法的形式(2)和(3)。假设 我们说方法属性(*),如果,存在常数,这样,如果,我们有。
引理4。考虑一个表单(法2)和(3)。如果是由,满足Wolfe-Powell条件(24),那么该方法拥有财产1()。
证明。由引理3,我们知道充分下降条件(22)持有。结合Wolfe-Powell条件(24),我们有 它遵循从(17),(35),那 集 这意味着。通过设置 我们有
对非线性共轭梯度方法,戴et al。4)提出以下总体的结论。
引理5。假设的假设2成立。考虑任何共轭梯度法,是一个下降方向和通过强Wolfe-Powell行搜索。如果 我们有
由引理3,我们知道的方法具有充分下降条件下Wolfe-Powell行搜索。结合引理5,我们可以有以下定理。
定理6。假设的假设2成立。考虑WYLDL方法,其中通过强大的Wolfe-Powell留置权搜索。如果存在一个常数这样 然后和 在哪里。
证明。首先,请注意,;否则,充分下降条件(22)失败。因此,是定义良好的。此外,通过关系(42)和引理5我们有
现在,我们把公式分成两部分如下:
和定义
在哪里。
然后由(3),我们有,
使用身份和(47),我们可以获得
使用条件
、三角不等式和(48),我们得到
另一方面,搜索条件(24)给
方程(22),(24)和(50)暗示
它遵循的定义,(17),(36)和(51),
所以我们有
让表示正整数的集合。为和一个正整数,表示
让表示元素的数量。戴和廖25)指出,为满足共轭梯度方法(我)财产1(*);(2)充分下降条件;(3)定理6;如果(42),然后小的步距不应太多。这个属性描述如下。
引理7。假设的假设2成立。考虑WYLDL方法,其中通过强Wolfe-Powell线搜索的。如果(42)认为,存在这样,对于任何和任何指数,有一个索引这样
证明。它遵循的前题3和4和定理6WYLDL方法具备上述三个条件(25]。所以,根据引理3.5 (25),引理7成立。我们省略了详细这个引理的证明7。
根据上面的引理和定理,我们可以证明下面为WYLDL方法收敛定理。
定理8。假设的假设2成立。考虑WYLDL方法,如果通过强大的Wolfe-Powell线搜索,那么我们就有
证明。我们证明这个定理的矛盾。如果,然后(42)必须持有。定理的条件6和引理7持有。定义,我们有任何指标,,, (57),,(17)给下面的: 让是由引理7和定义不小于最小的整数。由定理6,我们可以找到一个索引这样 用这个和,引理7给出了指数这样 对于任何指数通过Cauchy-Schwartz不平等和(59), 从这些关系(61年)和(60),并在(58),我们得到 因此,这矛盾的定义。完成证明。
4所示。数值实验
在本节中,我们报告这个算法的性能1(WYLDL)一组测试问题。代码写在Fortran 77和双精度运算。所有的测试进行相同的电脑。实验进行的一组73年[非线性无约束问题26]。来自可爱的一些问题(27)图书馆。为每个测试的问题,我们已经完成10数值实验变量的数量。
为了评估WYLDL算法的可靠性,我们还测试了这个方法对DL法和WYL法使用相同的问题。所有这些算法时终止。我们也迫使停止了动作,如果迭代超过1000或功能评估的数量达到了2000。在搜索条件(Wolfe-Powell行23)和(24),参数,。对于DL方法,,也就是与25]。我们也测试WYLDL算法这是最好的选择。
比较数据包含迭代函数和梯度评估,CPU时间。近似地评估WYLDL的性能,WYL和DL方法,我们使用多兰的概要文件和28作为评估工具。
多兰和更多28)给一个新工具来分析算法的效率。他们介绍性能概要文件的概念来评估和比较的性能的解决者在一个测试集。假设存在解决和问题,对于每一个问题和解决,他们的定义
=计算成本(迭代或函数和梯度评估或CPU时间)需要解决的问题通过解算器。
需要比较的基线,他们比较了性能问题通过解算器与任何解决这个问题的最佳性能;也就是说,使用性能比率如下:
假设一个参数对所有。集当且仅当解算器并不能解决问题。然后他们定义 因此为解决者的概率是一个性能比率是在一个因素最好的比例。然后函数是性能比率的分布函数。性能概要是一个不减少的,分段常数函数。也就是说,子集被分析的方法,我们画出分数任何给定的问题的方法是在一个因素最好的。
测试的问题,如果不能成功终止所有三种方法,那么我们摆脱他们。如果一个方法失败了,但也有其他的方法成功地终止,则设置的性能比失败的方法(的最大值是性能比率)。性能概要文件基于迭代函数和梯度评估,cpu时间的三种方法在数据绘制1,2,3,分别。
从图1基于迭代块性能概要文件,什么时候,DL方法执行比WYL WYLDL方法。的增加,当WYLDL和WYL方法比DL的概要文件的方法。这意味着,从迭代的角度,对问题的一个子集,DL方法比WYL和WYLDL方法。但是,对于所有的测试问题,WYLDL方法比DL更健壮的方法。
从图2,情节概要文件基于功能和性能梯度评价,可以看出,DL方法执行比WYL和WYLDL方法。比较图1,这些方法的差异远远小于迭代的概要文件。的一个可能的原因如下:WYLDL和WYL方法,所需的平均时间的函数和梯度评估迭代期间小于DL方法。从这个角度来看,WYLDL或WYL方法所消耗的CPU时间应小于DL方法,由于CPU时间主要依赖于函数和梯度评估。图3验证这一现象。从数据1来3,很容易看到WYL方法的性能和WYLDL方法非常相似。我感谢的可能的原因是,的第二部分,相比非常小。相关的原因之一可能是沃尔夫行搜索。因为本文中使用的线搜索是基于Lemarechal [29日),弗莱彻(30.],或越来越Thuente [31日)战略,这可能使方向导数非常小。
利益冲突
作者宣称没有利益冲突有关的出版。
承认
这项研究得到了广西大学基金会。2013 byb210。