计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (17): 44-47.

• 研究、探讨 • 上一篇    下一篇

无约束最优化问题的BFGS松弛异步并行算法

李文敬,刘之家,蓝贞雄   

  1. 广西师范学院 计算机与信息工程学院,南宁 530023
  • 出版日期:2012-06-11 发布日期:2012-06-20

BFGS relaxation asynchronous parallel algorithm of unconstrained optimization problems

LI Wenjing, LIU Zhijia, LAN Zhenxiong   

  1. College of Computer Science and Information Engineering, Guangxi Teachers Education University, Nanning 530023, China
  • Online:2012-06-11 Published:2012-06-20

摘要: 为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。

关键词: 最优化问题, BFGS公式, 松弛异步, 并行算法, 加速比

Abstract: In order to solve the sequential solution speed slow problem of the large-scale non-linearity optimization problems, for solving unconstrained optimization problems, chaotic relaxation asynchronous iterative parallel algorithm is proposed. BFGS sequential algorithm of unconstrained optimization problems are parallelized in the PC cluster environment. It utilizes CHOLESKY method to decompose coefficient to make the linear equation group of matrix for the symmetry. To solve the solution vector and non-linear search step of Wolfe-Powell by chaotic relaxation asynchronous parallel method, it parallels to the revised formula BFGS. The BFGS relaxation asynchronous parallel algorithm is build. Time complexity and speedup of the algorithm are analyzed. The experimental results of PC cluster show that this algorithm better solves the system load imbalanced problem, improves the speed of problem solving, the algorithm has the linear speedup ratio.

Key words: optimization problems, BFGS formula, relaxation asynchronous, parallel algorithm, speedup ratio