论文部分内容阅读
在求解无约束最优化问题的众多算法中,拟牛顿法是颇受欢迎的一类算法.尤其是用于求解中小规模问题时该类算法具有较好的数值效果.BFGS算法被认为是数值效果最好的拟牛顿法,其收敛理论的研究也取得了很好的成果.在一定的条件下,BFGS算法具有全局收敛性和超线性收敛速度.然而,对于大规模最优化问题来求解,包括BFGS算法在内拟牛顿法具有明显的缺陷.其主要问题之一在于拟牛顿法产生的矩阵不能保持目标函数f(x)的Hessian阵的稀疏性.有许多的例子表明,一旦处理问题很大时,一些对小规模问题非常成功的算法变得毫无吸引力.究其原因,主要是由于在中小型问题一些不太重要的因素在求解大规模问题时,变得代价很高.
随着速度更快及更复杂的计算机的出现,增强了我们的计算处理能力.同时也为我们设计算法带来了新的课题.并行计算机的发展为求解大规模最优化问题提供了一条新途径.对求解中小规模问题中数值效果好的算法并行化以用于大规模问题的求解受到了广泛欢迎.
本文在求解非线性方程组的并行Broyden算法的基础上,提出一种求解无约束最优化问题的并行BFGS算法.算法的基本思想是把原问题分解成若干个具有重叠性质的小规模子问题,对每个子问题采用BFGS算法求解,然后对子问题的解通过一种加权平均的方式进行修正,作为新的迭代点.我们证明,在一定条件下这种并行BFGS算法具有局部收敛性和线性收敛速度.