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

BFGS relaxation asynchronous parallel algorithm of unconstrained optimization problems

作　　者：李文敬[1] 刘之家[1] 蓝贞雄[1] 

机构地区：[1]广西师范学院计算机与信息工程学院,南宁530023

出　　处：《计算机工程与应用》2012年第17期44-47,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61163012;No.60864001);2009年度广西教育厅科研项目(No.200911MS144)

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]