文摘

基于内点法的新的并行变量分布算法SSLE算法求解不等式约束优化问题的约束的条件下block-separable顺序的线性方程系统的技术。每次迭代的算法只需要解决三个线性方程组系数矩阵得到相同的下降方向。此外,在某些情况下,全局收敛性。

1。介绍

考虑下面的不等式约束优化问题: 在哪里,是连续可微的。我们表示 为了解决这个问题(1),有两种类型的方法与超线性收敛:序贯二次规划(SQP)算法类型(见[1- - - - - -4]等)和SSLE(顺序线性方程组)类型算法(见[5- - - - - -9),等等)。一般来说,因为SQP算法需要解决一个或多个二次规划子问题在单一的迭代中,计算工作量很大。

SSLE算法提出了解决这个问题(1迭代),类似于以下线性系统被认为是: 在哪里是拉格朗日函数,是一个估计的黑森的,是当前估计的一个解决方案吗,是搜索方向,是下一个相关Kuhn-Tucker乘子向量的估计。显然,它是解决线性方程组简单比解决QP(二次规划)与不等式约束问题。

此外,并行的变量分布(PVD)算法(10)是一种方法,分配的变量之间的并行处理器。问题是分成许多各自的子问题,每个子问题安排到不同的处理器。每个处理器都有更新的块变量的主要责任,同时允许其余辅助变量限制的方式来改变一些容易可计算的方向。2002年,Sagastizabal和Solodov [11)提出了两个新的变种PVD的约束情况。没有假设凸性的约束,但假设block-separable结构,表明PVD子问题可以解决不正确地通过求解二次规划近似。汉et al。12]提出异步PVT算法求解大规模线性约束凸极小化问题的想法在2009年,基于约束优化问题是相当于一个可微的无约束优化问题,通过引入费舍尔函数。2011年,郑et al。13]给出了并行SSLE算法,PVD子问题被串行顺序不正确地解决线性方程,求解大规模约束优化block-separable结构。没有假设约束的凸性,证明了该算法是全局收敛的马。

在本文中,我们使用朱(8)作为主要的参考SSLE-type PVD方法问题(1)。假设问题(1)有以下block-separable结构:

然后,问题是分布式的并行计算的子问题并行处理器。算法,在每一次迭代,搜索方向是通过解决三个相同的线性方程组系数矩阵,保证每一个迭代是可行的。因此,该算法的计算工作进一步降低。此外,在一些合适的条件下获得其全局收敛性。

本文的其余部分组织如下。节2,一个并行SSLE算法。一些基本的假设下,建立了全局收敛性3。和最后一节给出结论。

2。算法的描述

现在我们国家算法如下。

算法

一步0(初始化)。给定一个起点。选择参数,,,,,,和一个初始对称正定矩阵。集。

一步1(并行)。为每个处理器,让

1.1计算的牛顿方向。解决以下线性方程组:

让是解决方案。如果,停止。

1.2计算的下降方向。解决以下线性方程组: 在哪里。让是解决方案。

1.3计算的主要搜索方向。建立的凸组合和: 在哪里

1.4计算高阶修正的方向。集

解决以下线性方程组: 在哪里 让是解决方案。如果,设置。

一步2(同步)。让

2.1线的搜索。计算,第一个数字序列中的令人满意的

一步3(更新)。获得通过更新正定矩阵使用一些拟牛顿公式。集 和。让。回到步骤1。

3所示。算法的全局收敛性

我们做出以下一般假设和让他们在纸上。(H3.1)为,集和非空的。一组紧凑。(H3.2)的函数,,是连续可微的。(H3.3)对所有向量的集合是线性无关的。(H3.4)存在,,这样,尽管和。

引理1。对于任何,任何正定矩阵,负的向量这样,,矩阵 非奇异的,,,。

证明。我们只需要证明是下面的线性方程组的唯一解: 现在考虑的情况下和分开。
为,如果和,它遵循从(19), 由(19),我们有 然后从假设(H3.3),它显示了。
为,如果它遵循的第一个方程(19), 如果,它遵循从第二个方程(19), 因此,如果结合(22)和(23从第一个方程(),19)和假设(H3.4),我们得到的 这表明和。

引理2。为,(1)如果,然后马的角度(1);(2)如果,然后根据计算(8)是定义良好的

证明。(1)根据马的定义很明显的(1)。
(2)如果,从(6),我们有 因此,从(9),存在一些,这样;也就是说,是定义良好的。此外,从(7),它遵循 因此,从(8),可以清楚地看到这一点 索赔。

引理3。线搜索算法的步骤2中定义良好;也就是说,存在这样,(14)- (16)举行。

证明。首先,(14),因为连续可微的,我们可以看到了吗 从(25),我们有,。然后我们可以获得 因此,对于,存在一些,这样,。
另一方面,从(25),如果,,我们有 因此,对所有, 然后,从(13),我们获得的,这 所以,存在一些,,这样,;也就是说,(15)持有。
第三,(16),因为是连续的,,存在一些,,这样
让;然后得出结论。

根据(H3.1), (H3.2)和(H3.4),我们可能假设存在一个子序列,这样

为了获取算法的全局收敛性,我们假设以下条件。(H3.5)静止的点的数量(1)是有限的。

定理4。算法部分2停在马点(1)在有限的迭代或者生成一个无限的序列马是谁的所有积累点(点1)。

证明。第一个语句很明显,唯一的终点是在步骤1.1。首先,我们证明 在哪里,。
自是单调递减,事实和连续性暗示 为,假设的矛盾。然后,从(17),我们有 因此,它是很容易证明的是以下的唯一解线性系统: 在哪里,。然后我们可以获得 因此, 类似于(8),我们定义,通过模仿引理的证明2,接下去 从(41),(42)和引理的证明3,我们可以得出结论,步长通过步骤2.2中的线性搜索距零界;也就是说, 因此,从(14),(37)和(42),我们得到 这是一个矛盾,显示,。
此外,从(40),我们有 如果,,然后,,很明显马的角度(1)。
不失一般性,我们假设存在一些,这样。如果,那么很容易看到马的角度(1)。假设。因为只有有限许多选择集我们可能会认为,,足够大,,在哪里是一个常数。很明显,。从条件(H3.5),它认为,。因此,它认为 同时,从(15),存在一些这样,, 它是在矛盾(46),这表明马的角度(1)。

4所示。结束语

本文结合并行变量分布的概念,我们提出了一种新的内点SSLE算法求解约束优化问题。提出的算法是一种特殊结构的目标函数或约束的特殊结构。在温和的条件下,理论分析表明,该算法的收敛。

它指出,仍有一些问题值得进一步讨论,如并行算法的研究不等式和等式约束。

利益冲突

作者宣称没有利益冲突。

确认

作者还要感谢匿名裁判仔细阅读和有用的意见和建议,使得本文的一个改良版本。这项研究受到了湖南省级教育主管部门批准的基础(12 a077号12 c0743, 13 c453)湖南大学的人文和科学研究基金,中国科学技术(没有。2012 qn04)。