摘要： 介绍无约束最优化问题的BFGS算法及其收敛性，提出利用行卷帘格式并行Cholesky分解法、同步并行Wolfe-Powell非线性搜索和并行处理BFGS修正公式来构建BFGS的并行算法，并对该算法的时间复杂性、加速比进行分析。在PC机群数值实验的结果表明，BFGS并行算法提高了无约束最优化问题的求解速度，理论分析与实验结果相一致，并行算法具有线性加速比。
关键词:
无约束最优化,
BFGS并行算法,
Cholesky分解,
加速比
Abstract: Based on analysis of both the Broyden-Fletcher-Goldfarb-Shanno(BFGS) algorithm and its convergence properties of unconstrained optimization problems, this paper presents a parallel algorithms of BFGS by using the row interleaved format parallel decomposition of Cholesky, the synchronous parallel Wolfe-Powell non-linear search and the modified formula of BFGS. The paper also analyszs the time complexity and speedup ratio of the algorithm. Experimental results of PC cluster show that the BFGS parallel algorithm improves solution speed of unconstrained optimization problems. The theoretical analysis and the experimental results of BFGS parallel algorithm are consistency with a linear speedup ratio.
Key words:
unconstrained optimization,
Broyden-Fletcher-Goldfarb-Shanno(BFGS) parallel algorithm,
Cholesky decomposition,
speedup ratio
中图分类号:
李文敬;王汝凉;廖伟志. 无约束最优化问题的BFGS并行算法与实现[J]. 计算机工程, 2009, 35(15): 58-60,6.
LI Wen-jing; WANG Ru-liang; LIAO Wei-zhi. BFGS Parallel Algorithm of Unconstrained Optimization Problems and Its Implementation[J]. Computer Engineering, 2009, 35(15): 58-60,6.