解大规模部分可分无约束极小化问题的并行分块松弛方法
2015-06-15刘亚云
刘亚云
(重庆师范大学 数学学院,重庆401331)
对于并行优化算法,大致可以分为两类:一类是原问题没有分解为一系列小规模的子问题,而是使用并行搜索方向的并行优化算法[1]或使用并行梯度计算的并行优化算法[2];另一类是针对一般函数或可分函数,把原问题分解为子问题的基础上提出的并行优化算法[3-9].笔者提出的方法主要是依据基于区域分解方法的优化方法,此类方法被应用在计算机技术方面[10-13].通过分解变量来加速含有部分可分函数的极小化,这一思想也在一致优化中体现[14].在一致优化中,全局变量来保证分解的一致性,在笔者提出的方法中,只通过邻接子向量[10-13](“interface”subvectors即两个邻近的子向量的公共部分)来保证分解的一致性.在一致优化中,子函数必须是凸函数,而笔者提出的算法中可以适用于部分可分函数是凸函数或非凸函数的情形.
1 部分可分无约束极小化问题
考虑如下极小化问题

其中Fi(x):Rni→R (i=1,2,...,N ),此时存在正整数ni,使得是连续可微函数.在某种程度上,函数()F x部分可分即:只包含x的多维子向量;Fi,Fji≠()j共有x的某些部分.对于子向量,适合于文献[15]的记法.为了充分理解和解决问题(1),引入以下记号:
·子向量x[i]的邻接指标集:事实上,

·邻接子向量[10-13]:x[ij],x[ji]∈Rmij,(i,j)∈I
其中,x[ij]=x[i]∩x[j]表示x[i]中x[i],x[j]共有部分;x[ji]=x[j]∩x[i]表 示x[j]中x[i],x[j]共有部分.
例1 在文献[16]中,一个著名的部分可分函数Rosenbrock测试函数:

则函数F1(x)和F2(x)共有x2,即对邻接子向量x[12],x[21]有x[12]=x[21]=x2,阻碍了函数F (x)完全可分.向量x的子向量是x[1]= (x1,x2)T∈R2,x[2]= (x2,x3)T∈R2.
2 并行分块松弛方法(PBR)
笔者提出的新的并行分块松弛方法是依据有约束的极小化问题而得出的并行方法.首先,引入合适的辅助未知变量使无约束极小化问题转化为含有全部可分函数的线性约束极小化问题;……
