文摘
最近,足够的后裔属性中扮演一个重要的角色在一些迭代方法的全局收敛性分析。在本文中,我们提出一种新的迭代法求解无约束最优化问题。这种方法提供了一个充分下降方向为目标函数。此外,该方法的全局收敛性是建立在一些适当的条件下。我们也报告一些数值结果和比较方法的性能与一些现有的方法。数值结果表明,提出的方法是有效的。
1。介绍
考虑无约束优化问题 在哪里是一个连续可微的函数。为解决(1),经常使用迭代公式如下: 在哪里是当前迭代点,是一个由一些线搜索步长,然后呢是一个搜索方向。不同的搜索方向对应于不同的迭代方法(1- - - - - -4]。在这篇文章中,是一个维列向量,,和被定义为的欧式范数和转置向量,分别。一般来说,如果存在一个正的常数,这样 然后搜索方向拥有足够的财产。这个属性可能是至关重要的迭代方法的全局收敛性(5),和一些数值试验表明,充足的降落方法是有效的(6]。然而,并非所有的迭代方法可以满足充分下降条件(3)在一些不精确线性搜索条件下,如提出的共轭梯度法魏et al。7)或梯度方法(8]。为了使搜索方向满足条件(3每一步,已经完成了大量的工作(9- - - - - -12]。
在[9程),提出了一个修正PRP共轭梯度法的搜索方向是由 在哪里,是一个矩阵和是一个单位矩阵。
在[10),张等人推导出一个简单的充分下降法;搜索方向是由
最近,Zhang et al。11)提出了三任修正PRP共轭梯度法;搜索方向是由 在哪里
我们注意到(4),(5)和(6)可以写成一个线性组合的最速下降方向和原始的投影方向;也就是说, 在哪里是一个原始的方向,是一个标量,任何向量,这样吗成立。事实上,如果,,,然后(8)降低方法(4)。让,,;然后(8)降低方法(5)。当,,,很容易推断出(8)降低方法(6)。从(8),我们可以很容易地获得 因此,一个人对所有。它意味着充分下降条件(3)持有。但该方法(5)并不拥有一个重启功能可以避免干扰现象。此外,该方法(4)和(6)可能并不总是全局收敛下一些不精确线性搜索(13),如标准Armijo-type线搜索提供如下: 在哪里和。
出于(8)和(9),我们的目的是设计一个方向的子空间,在那里是一个参数。这个方向可以写成 在哪里任何向量,这样吗成立。让 很明显,(8)可以被视为一种特殊情况(12),。因此,(12比()将有更广泛的应用8)。如果我们把,,,,在(12),然后给出了一个新的搜索方向如下: 在哪里
在本文中,我们提出一个新的迭代解无约束优化问题的方法;(定义的搜索方向13)和(14)。我们证明满足不需要任何线搜索。这意味着充分下降条件(3)持有。此外,我们证明,该方法是全局收敛下标准Armijo-type线搜索或修改Armijo-type线搜索。从(13)和(14),我们可以看到,该方法有一个重启功能,直接解决干扰问题。事实上,当步骤很小,那么因素呢趋向于零向量。因此,方向由(13)非常接近最速下降方向。
本文的其余部分组织如下。节2,我们提出一种新的算法,并讨论其足够的财产。节3,证明了该方法的全局收敛性修改下Armijo-type线搜索或标准Armijo线搜索。给出了一些数值结果来测试该方法的性能4。最后,我们有一些关于该方法的结论。
2。新算法
在本节中,列出了具体算法的迭代步骤如下。
算法1。考虑以下。步骤1。选择参数,,;给定一个初始点。集和。步骤2。如果,然后停止;否则进入下一步。步骤3。确定步长满足修改Armijo-type线搜索条件: 步骤4。让。第5步。计算搜索方向由(13)和(14)。步骤6。集,转到第2步。
证明。显然,结论为真。
如果,乘以(13),我们有
因此,不平等(16适用于所有。完成证明。
3所示。收敛性分析
以下假设往往需要证明非线性共轭梯度方法的全局收敛性(14,15]。在本节中,我们也使用这些假设在该方法的收敛性分析。
假设3。考虑以下。(我)的水平集是有界的。(2)在一个社区的,函数是连续可微的,其梯度Lipchitz连续;也就是说,存在一个常数,这样
引理4。假设的假设3成立。让和由算法生成的1。如果步长获得的是(15)或(10),那么存在一个常数,这样 和一个也可以
证明。这个引理的结果将证明在以下两种情况。
情况下1。让步长计算(15)。从定理2,我们有;因此。如果,然后我们获得。如果,然后我们知道不满足不等式(15)。所以我们有
通过假设3(2)和中值定理,我们
在哪里。
从(21)和(22),我们有
使用定理2再一次,我们得到
让;那么不平等(19)。
从假设3(我),存在一个常数,这样,。由(15),(19),定理2,我们有
因此,从上面的不平等,我们有
情况下2。让步长计算(10)。类似的证明上面的情况下,我们可以获得
让;那么不平等(19)。从(10),(19),定理2,我们获得
通过上面的不平等,我们可以得到(20.)。完成证明。
定理5。假设的假设3成立。如果算法1产生无限的序列和,然后有
证明。我们获得这个结论(29日)的矛盾。假设(29日)不持有,那么存在一个正的常数,这样,尽管。从假设3(我),我们知道也有正的常数,这样,尽管。自,那么我们就有 上面的不平等意味着 这与(20.)。这就完成了证明。
注6。如果搜索方向被定义为(13),,,足够的后裔财产和全局收敛性也可以证明类似于定理的证明2和5。
4所示。数值结果
在本节中,一些数值结果提供给测试该方法的性能,并提出的方法与现有的方法相比(9- - - - - -11]。为了简单起见,该方法和其他的比较方法是由在命名的,中央(11],SSD [10),和人民革命党9),分别。的测试问题和初始点(16]。表中列出的测试问题1。在我们的实验中,所有的代码都写在MATLAB 7.0和2.00 GB RAM内存运行在PC, 2.10 GHz CPU和windows 7操作系统。
所有算法的步长计算满足修改Armijo-type线搜索(15),,,和停止条件。我们也停止这些算法如果CPU时间是超过500 (s)。
在表2,P, N,倪、NF NG和CPU测试问题的数量,向量的维数,迭代的数量,数量评估函数,梯度评估的数量,分别在秒和CPU的运行时。符号“-”意味着相应的方法不能解决测试问题时,CPU时间超过500秒,和明星表示的数值结果是最好的在所有的比较方法。
在表2,我们比较的性能测试新方法28个不同的问题。根据恒星的分布,一个可以看到在方法执行比中央人民革命党,和SSD方法与14个测试问题,比蒙古人民革命党方法1测试问题,比中央方法6测试问题。然而,也存在7测试问题不明显的象征。其中7测试问题,在方法执行比其他方法有5个测试问题的迭代次数,4测试问题的数量评估函数,5测试问题的梯度评估,和1测试CPU时间的问题。
为了比较这些方法的性能,我们采用性能概要介绍了多兰和更多17]。性能结果如图1- - - - - -4,分别。在[17),多兰和介绍了概念来评估和比较的性能设置解决者在一个测试集。假设解决和问题存在,对于每一个问题和解决,他们的定义
的性能比 假设一个参数对所有是选择,当且仅当解算器并不能解决问题。性能概要文件定义的 因此,为解决者的概率是一个性能比率是在一个因素最好的比例。性能概要解算器是不减少的、分段和连续的从右边。的价值的概率是解决者将赢得剩下的解决者。一般来说,一个高值的解算器或在右上角的图最好或代表最好的解决者。
从数据1- - - - - -4,我们可以明显看到,在方法执行比蒙古人民革命党法和SSD法。虽然中央方法优于在方法在图1,在图2,在图3,在图4在方法优于中央方法在剩余的时间间隔。此外,从数据1- - - - - -4,我们可以看到,在方法可以解决100%的测试问题,虽然中央方法可以解决96%的问题。因此,在方法优于中央方法。通过比较的价值在数据1- - - - - -4,一个人可以有一个结论:在方法竞争给他人;例如,在方法优于其他方法的迭代次数至少45%。一句话,一个人可以有一个结论,提出的方法比中央更好,人民革命党,SSD数值结果的分析方法。
5。结论
在本文中,我们提出了一个新的公式(11),通过不同的参数可以生成不同的搜索方向。根据这个公式,我们提出了一个新的充分下降法求解无约束最优化问题。在每个迭代中,生成的方向只有两个连续点的梯度信息。我们已经表明,这一方法是全局收敛的。给出的数值结果表明,该方法优于其他方法的测试问题。在未来,我们将学习更好的迭代方法根据(11)和执行新的收敛性分析。
利益冲突
作者宣称没有利益冲突有关的出版。
确认
作者要感谢编辑和匿名裁判对他们有价值的意见和建议,大大提高本文。这项工作在一定程度上是由中国国家自然科学基金(11371071)、辽宁省自然科学基金(20102003),辽宁省教育部门的科学研究基金会(L2013426)和渤海大学的研究生创新基金会(201208)。