文摘
共轭梯度(CG)方法用于寻找最优解大规模无约束优化问题。基于其算法简单、低内存的要求,并获得的速度解决方案,该方法广泛应用于许多领域,如工程、计算机科学、医学科学。在这篇文章中,我们修改CG方法达到全局收敛性的各种行搜索。此外,它通过充分下降条件没有任何行搜索。弱Wolfe-Powell线搜索下的数值计算表明,新方法的效率优于其他传统的方法。
1。介绍
非线性CG方法是一个有用的工具来找到最小值函数的无约束最优化问题。让我们考虑以下形式 在哪里是连续可微的,其梯度用吗。的方法来找到一个序列点从初始点给出了迭代公式: 在哪里当前迭代点吗由一些线搜索获得的步长。搜索方向被定义为 在哪里和被称为共轭梯度系数。
强烈Wolfe-Powell (SWP)搜索是最受欢迎的不精确线搜索,这是根据函数的减少和降低搜索区域找到步长。此外,它迫使步长被关闭驻点或局部最小值的函数,所以它是非常有用的方法来找到步长。 在哪里。事实上,SWP修改线搜索从弱Wolfe-Powell (WWP),所以我们发现步长满足(4), 然而,WWP线搜索可能接受远离固定步长或局部最小值的函数。戴(1)提出了两个Armijo类型搜索行:第一个匹配的全局收敛性使用方法(2)和(3)。通过这条线搜索,FR的全局收敛性,建立了非负PRP和CD方法。匹配原始PRP方法的全局收敛性,他设计的另一个线搜索建议如下。
给定一个常数,和确定最小的整数,如果它定义了,那么向量和由(2)和(3)满足(4), 在哪里和是两个常数。
最受欢迎的公式如下:Hestenes-Stiefel (HS) [2),Fletcher-Reeves (FR) [3),Polak-Ribiere-Polyak (PRP) [4),共轭血统(CD) [5),Liu-Storey (LS) [6),Dai-Yuan (DY) [7),魏et al。(WYL) [8),海格和张(赫兹)9]。 在哪里,与和是一个常数。
FR方法的全局收敛性和精确线搜索通过Zoutendijk [10],Al-Baali [11]证明了FR方法是全局收敛沃尔夫强条件下当的,后来刘et al。12)扩展的结果。其行为在数值计算是不可预测的。在一些情况下,这是像PRP方法有效。然而,一般来说,它是非常缓慢。此外,DY和CD有相同的性能FR方法精确线搜索下具有较强的全局收敛性。下凸目标函数的全局收敛性的PRP方法精确线搜索被波兰人的证明,并在1969年Ribiere [4]。后,鲍威尔发出反例表明存在非凸函数,而全球PRP方法不收敛,虽然精确线搜索使用。鲍威尔表示,实现PRP方法的全局收敛性的重要性,它不应该是负的。吉尔伯特和Nocedal [13]证明了负的PRP Wolfe-Powel线搜索方法是全局收敛的。HS方法和LS方法有相同的性能与PRP精确线搜索。因此,PRP方法是最有效的方法时,相比其他共轭梯度方法。更多信息,读者可以看到下面的引用(14- - - - - -19]。
2006年,魏et al。8]给出了新的积极的CG方法,似乎原来PRP方法研究了精确线搜索和不精确线搜索,出现了许多修改,如以下(20.- - - - - -23),分别。
一个小修改,张21)提出以下CG方法: 以同样的方式,构造以下CG使用的分母: 此外,由使用的分子: 在哪里和。
下降条件在CG方法由中扮演重要的规则 如果我们延长(12以下表格, 然后搜索方向满足充分下降条件。
在本文中,我们将提出新的公式和算法部分2。此外,我们将建立我们的方法的全局收敛性和几个节线搜索3。数值结果与结论将在部分4和5,分别。
2。修改后的公式
在本节中,提出了扩展到是哪一个和方法;也就是说, 在哪里意味着欧几里得范数。
算法1。
一步1(初始化)。鉴于,设置。
一步2。计算基于(14)。
一步3。计算基于(3)。如果,然后停止。
一步4。计算基于一些线搜索;我们使用在数字部分WWP线搜索和。
一步5。更新新的基于点(2)。
一步6。收敛测试和停止条件:如果和然后停止;否则,去第一步。
3所示。全局收敛性分析方法
以下假设是需要用于下面的定理。
假设2。(我)在水平集是有界的从下面吗,在那里是一个起点。
(2)在一些社区的,是连续可微的,其梯度是李普希兹连续;也就是说,对于任何,存在一个常数这样。
引理3。我们的假设2持有。考虑任何方法形式(2),(3),满足WWP线搜索(4)和(6),搜索方向的后裔。然后,以下条件成立: 用(13)(15),它遵循
3.1。收敛的充分下降条件属性SWP行搜索
定理4。让序列和生成的方法(2),(3)和(14);然后(13),。
证明。我们用数学归纳法证明。从(3),我们知道这是举行。假设这是真的,直到;也就是说, 然后 现在乘(3): 在哪里。取并完成证明。
3.2。全局收敛性WWP线搜索下
吉尔伯特和Nocedal [13]目前找到的全局收敛性的一个重要定理负的PRP方法的一部分;这是总结的定理5。此外,(13)提供了一个不错的属性称为属性扮演着强大的角色在CG方法的研究。
财产 。考虑一个表单(法1)和(2),假设;我们说的方法拥有财产如果存在常数和,所有,我们得到,如果,然后
定理5(见[13])。考虑到任何CG方法的形式(2)和(3)持有达到下列条件:(我) (2)充分下降条件(13)(3)Zoutendijk条件(IV)财产(V)假设2然后迭代是全局收敛的。
证明。自由于满足财产,也实现了属性;更多的我们建议读者读引理3.6 [24]。完成证明。
推论7。让序列由算法生成的1。如果假设2适用,那么任何线搜索满足Zoutendijk条件;我们有。
3.3。全局收敛性属性Armijo线搜索类型
定理8。假设的假设2是真的。考虑形式的方法(2)和(3),,获得的是(4)和(7)。然后我们有。
证明。利用引理2.8 (1),我们实现 使用(2)和(7),然后 从(2),(4),(7)和(20.),我们有 从假设2和(21),我们得到 从(3), 使用(23),(13),(14)和(24),然后 在哪里。取极限和使用(22),然后我们有。完成证明。
4所示。数值结果和讨论
分析新方法的效率,我们选择的一些测试函数表1从可爱25],安德烈·[26],和Adorio Diliman [24]。我们与其他CG方法进行了比较,包括NPRP和DPRP方法使用弱Wolfe-Powell行搜索。的宽容是选择所有调查的速度迭代算法对最优方法。梯度值作为停止准则。在这里,考虑停止标准。由于参数NPRP和DPRP测试是基于弱Wolfe-Powell线搜索,修改后的参数测试是基于弱沃尔夫线搜索的值和。此外,的值和是为分别和DPRP参数。
我们使用Matlab 7.9子例程程序,CPU处理器英特尔(R)的核心(TM), i3 CPU,沃尔夫和2 GB的DDR2内存强大行搜索。性能结果如图1和2分别使用性能概要介绍了多兰和更多27]。介绍了这种性能测量比较一组解决在一组的问题。假设解决和中存在的问题和分别测量被定义为计算时间(例如,数量的迭代或CPU时间)需要解决吗来解决问题。
创建一个基线比较,解算器的性能题比例是任何解决的最佳性能使用比例的问题: 我们的参数对所有选择,进一步假设当且仅当解算器并不能解决问题。当我们想获得一个整体解算器的性能评估,我们定义了测量: 因此,为解决者的概率是性能比是在一个因素最好的比例。如果我们定义的函数的累积分布函数的性能比,性能测量为解决不减少的和分段连续函数是正确的。的价值的概率是解算器达到最佳性能的解决者。一般来说,一个高值的解算器,这将出现在右上角的人物,是可取的。
很明显,参数是强大的竞争与NPRP参数和在某些情况下略好图表数据1,2,3,4包括迭代的数量、CPU时间,梯度评估,和功能评价。另一方面,很明显,在所有的性能参数优于DPRP参数配置文件。
5。结论
在本文中,我们提出了一种新的从NPRP修正共轭梯度方法的扩展方法。我们的计算结果表明,新系数可比比其他传统的CG方法。该方法收敛与几个线搜索全球下降方向。然而,在未来,我们将专注于速度使用混合方法。此外,我们将尝试比较几个线搜索与现代CG方法。
相互竞争的利益
作者宣称没有利益冲突有关的出版。