A parallel Bernstein algorithm for global optimization based on the implicit Bernstein form
A parallel Bernstein algorithm for global optimization based on the implicit Bernstein form
复制标题
基于隐式Bernstein形式的并行全局优化Bernstein算法
DOI：
--
复制
发表时间：
2017
影响因子：
2
通讯作者：
P. Nataraj
中科院分区：
文献类型：
--
作者：
P. Dhabe;P. Nataraj
在本文中，我们首先提出了一种基于隐式伯恩斯坦形式（IBF）的多项式全局优化的串行伯恩斯坦算法（Smith in J Glob Optim 43:445–458, 2009）。基于IBF的串行Bernstein算法比传统的Bernstein算法及其变体需要更少的计算量和内存。为了进一步加速基于 IBF 的 Bernstein 算法，我们接下来提出了使用统一计算设备架构的 GPU 计算并行版本。使用并行版本，串行算法的指数时间复杂度降低为线性时间复杂度。我们比较了这两个版本在一组 12 个测试问题上的性能，发现并行版本比串行版本快 26 倍，时间减少 96%。基于这些发现，我们建议在多项式全局优化中使用基于 IBF 的并行版本的 Bernstein 算法。
In this paper, we first present a serial Bernstein algorithm for polynomial global optimization based on the Implicit Bernstein Form (IBF) (Smith in J Glob Optim 43:445–458, 2009). The serial Bernstein algorithm based on IBF needs less computations and memory than the conventional Bernstein algorithm and its variants. To accelerate further the Bernstein algorithm based on the IBF, we next propose a parallel version for GPU computing using Compute Unified Device Architecture. With the parallel version, the exponential time-complexity of the serial algorithm reduces to linear time-complexity. We compare the performance of both the versions on a set of 12 test problems, and find that the parallel version is up to 26 times faster and takes 96% less time than the serial one. Based on these findings, we suggest the use of the parallel version of the Bernstein algorithm based on IBF in polynomial global optimization.