文摘

实用算法求解大规模box-constrained开发优化问题,进行了分析,并测试。在该算法中,一个识别策略涉及到评估活动设置在每个迭代。不活跃的组件变量决定的最陡下降法起初有限数目的步骤,然后随后共轭梯度法。在一些适当的条件下,我们表明,该算法是收敛的。数值试验和比较从可爱的图书馆通过使用一些box-constrained问题报告。数值比较,说明该方法是有前途的,与著名的method-L-BFGS-B竞争。

1。介绍

我们认为box-constrained优化问题 在哪里是连续可微的,,与。的梯度在是,它的th组件是()或为了简单起见。我们定义的可行域(1),;也就是说, 我们说一个向量是一个静止的点问题(1如果它满足 问题(1)在实际的优化是非常重要的,因为许多实际问题可以转化成这种形式。此外,问题(1)常常被视为一子问题的增广拉格朗日或者罚款方案一般约束优化。因此,数值算法的发展有效地解决(1),尤其是当尺寸很大,在理论和应用都是非常重要的。此外,box-constrained优化问题近几十年来一直得到太多的关注。我们把优秀论文(1为评价很好。

许多算法为解决这种类型的问题是基于有效集策略,例如,(2]。在这个类的方法,一个工作集是用来评估的积极约束集的解决方案是在每个迭代更新。早期有效集方法相当有效的相对低维问题,但通常不被大规模的(3]。主要原因是一个约束可以添加或删除从活动的每一步。然而,这减缓了收敛的速度。基于这一考虑,越来越多的学者从事设计有效集方法旨在使快速变化对/从错误的预测,例如,(3- - - - - -8]。

让。很明显,问题(1)减少以下无约束优化问题: 它可以通过几乎任何现有的有效解决方法如非线性共轭梯度法,有限的内存蓄热方法和谱梯度方法。这些方法适合解决(4),被认为是由于其简单性和低存储需求。

在共轭梯度方法的方案中,Polak-Ribiere-Polyak (PRP)方法通常被认为是最有效的从计算的观点。但其全局收敛性非凸非线性函数仍然是不确定的(9]。为了克服这个缺点,提出了各种技术。特别是,Zhang et al。10]介绍了修改MPRP方法生成的方向是后裔独立的线搜索规则(11]。全局收敛性保证通过Grippo Armijo-like线搜索策略的一个变体和Lucidi12]。此外,人民革命党也被认为是有能力解决box-constrained优化问题(1基于投影梯度方法(13]。然而,我们所知,论文非线性共轭梯度求解box-constrained最小化问题相对较少。

本文从不同的角度,我们进一步研究蒙古人民革命党方法的应用程序在10)为解决box-constrained最小化问题。首先,出于Facchinei等的工作。3),我们估计在每个迭代低维子空间自由,效能的被应用于解决大规模问题时数值更便宜。在每个迭代搜索方向由两部分组成:一些简单定义的组件;其余的是由非线性梯度法。该方法的显著的羽毛是所有不需要梯度投影生成的点是可行的。在一些适当的条件下,我们表明,该方法收敛。我们目前的实验结果比较发达L-BFGS-B方法和著名的算法。

本文组织如下。容易理解的算法,我们简单回顾一下一组主动识别技术,然后国家我们的新算法的步骤2。节3在全球,我们表明,该方法收敛。节4,我们测试算法的性能和做一些数值比较。最后,我们得出一些结论5。在本文的其余部分,象征表示向量的欧几里得范数。

2。动机和算法

在本节中,我们介绍一种新的算法定义的 在哪里是一个搜索方向和是相应的步长。构建我们的算法,在本文中,我们假设以下假设。

假设1。的水平集紧凑。

假设2。在某些街区的的梯度李普希兹连续;也就是说,存在一个常数这样

假设3。保存在严格互补条件;即严格不等式在第一个和最后一个的影响(3)。

在[3),Facchinei等人提出了一个活跃的集牛顿算法求解问题(1)。他们的算法具有一些良好的性质,如快速本地所有迭代的收敛性和可行性。此外,只有较低维的二次规划子问题需要解决在每个迭代。我们现在只记得激活集识别技术(3]。让和非负连续有界函数上定义这样,如果或,然后或,分别。对于任何,定义指标集,和作为 一组是一个估计的有效集点吗。Facchinei et al。3)表明,与假设3,当足够接近,该指数是一个精确的识别。这个属性将使我们能够找到有效集驻点在一个有限数目的步骤。这组主动识别技术(7)有多少额外的动机研究box-constrained优化问题,例如,(14- - - - - -18]。

使用激活集估计技术(7),我们推断出我们现在的详细算法中使用的搜索方向。为了简单起见,让,,,让在相应的向量元素的数量矩阵的列,在那里是列的单位矩阵。此外,我们表示,分别th组成部分和通过和。

让,在这 现在,我们限制我们的注意力和索引定义组件。让 在哪里 在这,,。很明显,因此。不难看到,搜索方向的定义保证了足够的血统财产;这是 搜索方向的定义9)是由张设计等。10在完整的空间。这里,是说的稍微不同的情况下,但很容易确认它仍然是有效的在我们的背景。

为了保证所有迭代的可行性和血统的目标函数在每个迭代中,我们定义了积极的标量通过 注意,当持有和严格互补条件,然后总是定义良好的,除非驻点。结合(8)和(9),紧凑的形式可以写成

备注4。观察到的变量的搜索方向(9)包含梯度和方向信息在当前或之前的步骤,而不变量的设置可能会随着迭代的进行改变。特别是,集和可能不是相同的。在这种情况下,我们设置,也就是说,一个负梯度方向。否则,我们使用共轭梯度公式更新搜索方向的自由空间。

备注5。考虑当前迭代时的情况还没有一个最佳点,可能是足够小。在这种情况下,为了实用的目的,它可能是有效的限制有界从0。

详细列出我们的算法,我们首先显示方向的一些有用的属性。下面的结果表明,无论何时为目标函数,它是一个下降方向在当前点。房地产是非常重要的我们的算法。

引理6。如果获得了(13),它满足 和,等号成立当且仅当。

证明。通过搜索方向的定义,我们有 上面的关系可以很容易地获得方向的定义在(13)。注意,严格互补条件成立,这显示当且仅当。

作为一个直接后果的定义的搜索方向,我们有以下的事实。

引理7。让由(13)和假设;然后,

以上引理证明这样 由于搜索方向计算,步长应该决定为了获得下一次迭代(5)。在本文中,我们考虑一个回溯线搜索过程,减少的序列试,直到最小的吗找到满足 在哪里,。然后接受相应的步长。

现在我们已经准备好正式国家整体算法求解box-constrained优化问题(1)如下。

8 (SDPRP)算法。算法的步骤如下。
步骤0给定的起点。,常量,和。集。
步骤1确定。,,根据(7)。
步骤2,如果,设置。否则,设置 确定由(13)。
步骤3,如果,然后停止。
步骤4找到最小的整数(说)满意(18)。让。
步骤5组。。
步骤6,让,转到步骤1。

备注9。现在假设活动集已确定在有限数量的步骤;然后,我们有对所有和对所有。如果线搜索过程,我们都知道不满足(18)。也就是说,
中值定理,有一个这样 在哪里李普希茨是常数。它遵循从[10引理3.1],存在一个正的常数这样。用上面的不平等(20.),我们有 由此可以得出这样的结论:当线搜索步骤是定义良好的,所以整个算法。

3所示。收敛性分析

在本节中,我们表明,算法8。在全球范围内收敛。下面的引理给出了一个充分必要条件,算法的全局收敛性8。

引理10。让是一个序列的迭代生成的算法8,让是一个搜索方向定义为(13)。然后是一个平稳点(1)当且仅当。

证明。让。如果,那么我们就有 自和,正确的不平等。如果类似的,我们将证明这一点。如果,我们可以从(11),。现在假设是一个平稳点(1);它从(3)和(7), 然后它遵循从(9)和(11),,和。因此。

引理11。让是一个序列的迭代生成的算法8,让是一个搜索方向定义为(13)。假设有子序列和作为。然后是一个静止的点问题(1)。

证明。因为不同类型的数量,,是有限的和假设1- - - - - -3,假设3确保存在这样对所有(3), 自显然,我们有 此外,这一事实和意味着 的证明一旦我们得到注意,(11),作为。

类似的前题的证明10和11也可以发现在3]。本节结束,现在我们准备建立算法的全局收敛性8。

定理12。假设的假设1- - - - - -3持有。然后序列由算法生成8至少有一个极限值,这个序列的极限点是驻点的问题(1)。

证明。它很容易遵循从引理7序列点生成的算法8是包含在紧集。因此,通过假设1至少存在一个极限点的序列。
如果序列最后一点是有限的那么,由引理10,是一个静止的点问题(1)。所以我们认为序列是无限的。
关于第一部分引理的证明11,,,是常数从一些迭代索引吗;也就是说,
很容易看到 作为。现在,还有待证明(),。根据全局收敛性定理在10),我们有 的定义在(9),它相当于 它遵循从(29日)和(31日),由引理,这显示了我们索赔11。证明已经完成。

4所示。数值实验

现在,让我们报告我们的一些数值结果达到足够的后裔Polak-Ribiere-Polyak Algorithm-SDPRP。该算法在双精度运算由Fortran77实现代码。所有的实验都运行在PC与CPU英特尔奔腾双重E2140 1.6 GHz, 512字节的SDRAM内存,Red Hat Linux 9.03操作系统。我们的实验进行一组可爱的非线性box-constrained问题[19]库,可用二阶导数。因为我们感兴趣的大问题,我们完善这个选择只考虑问题的数量至少是变量。总之,我们解决了问题。目标函数的类型和角色被测试表中列出的问题1。

在实验中,很容易与其他代码,我们使用投影梯度误差测量的质量,而不是解决方案;也就是说,我们力迭代时停止 在哪里目标函数的投影梯度和吗表示一个向量的最大绝对分量。显然,停止标准(32)是等价的在我们的方法。我们也停止SDPRP当的执行迭代或函数没有实现融合评估完成。我们选择初始参数,,,。此外,我们还与不同的参数测试我们建议的方法和看到是最好的选择。为了评估SDPRP的性能,然后我们众所周知的方法L-BFGS-B(可以在测试http://www.ece.northwestern.edu/ ~ nocedal / lbfgsb.html)[20.,21)进行比较。

运行时代码L-BFGS-B,默认值是用于所有参数。L-BFGS-B,除了(32),该算法还有一个内置的基于参数停止测试factr。它旨在终止运行,当目标函数的变化是足够小。默认值factr温和的准确性。此外,它有时会发生线搜索不能取得任何进展,或Nfg的价值达到了前缀号码(= 10000);在这些情况下,运行也终止。

算法的数值结果SDPRP和L-BFGS-B列在表2和3,分别。我们使用水平线把选中的问题分成两个表据表类1。列在表中2和3有以下含义:问题:问题的名称;昏暗的:问题的维度;Iter:迭代次数;Nf:数量的功能评估;吴:梯度的计算;时间:CPU时间以秒为单位;阵线:最后的函数值;Pgnorm1:最终梯度投影的最大模。

符号“-”表示可爱系统变得nonrespondent当计算相应的问题。L-BFGS-B,我们记录的数量函数和梯度评估Nfg因为L-BFGS-B总是评价函数和梯度在同一时间。

一些一般性的观察的结果表2和3以下。从表的最后一列3我们看到,问题,L-BFGS-B终止异常不能够满足终止条件(32)。SDPRP未能达到一个平稳点基于停止标准(32)只问题:BDEXP,EXPQUAD,SOND1LS,QR3DLS,BIGGS1,BQPGAUSS,CHENHARK,JNLBRNGB,NCVXBQP1,ODNAMUR,NCVXBQP2,GRIDGENA。至少,这是一个有趣的事实L-BFGS-B获得尽可能好的函数值SDPRP一些问题但投影梯度不满足屈服条件。这个原因不清楚指出,朱镕基等人在21]。在分析两种方法的性能成功的问题至少有一个方法,我们观察到,在这些问题上,L-BFGS-B需要较少的迭代,不如SDPRP功能评估。sterical数据表的两种算法进行了总结4,“Scueed“是成功和的数量”失败“是失败的数量为两种算法的测试问题。

一切在一起,初步数值比较表明,我们提出的方法是有效的和L-BFGS-B与著名的竞争方法。此外,我们得出结论,该方法提供了一种有效的方法解决大规模box-constrained问题。

5。结论

在本文中,我们开发了一个子空间非线性共轭梯度法求解box-constrained优化问题。对于大多数测试的优化问题(42的54),算法成功地终止的解决方案。然而,在大多数情况下,函数的数量评估似乎很大。这种方法的一个常见羽毛是所有生成的点是可行的,而不需要像往常一样梯度投影方法在这个计划。因此,这可能是为什么函数评价数字高于投影梯度或信赖域方法。然而,我们也相信SDPRP box-constrained问题是一个有效的方法。在我们看来,至少有三个问题,可能导致改进。第一点,应考虑可能的选择有效集的参数识别技术和使用参数的值并不是唯一的选择。应该进一步研究的另一个重要的一点是采用梯度投影技术。第三个假设是强劲; how can we modify this algorithm so as to avoid the strict complementary assumption? Additionally, it is worthwhile to investigate that some existing conjugate gradient methods, such as [12,22),是否可以嵌入一组活动框架来解决box-constrained问题。为此,尽管该方法没有得到显著的发展预期,我们认为这个提议的增强方法仍是明显的。因此,我们认为,该算法是一种有效的方法和可能性的问题,它可能有自己的力量。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者感谢副主编和两个匿名裁判的建设性建议,大大提高了纸。这位作者的作品是由天然河南省科学基金会赠款GGJS2011030和132300410168。