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

摘要

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