A parallel Bernstein algorithm for global optimization based on the implicit Bernstein form

被引：3

作者：

Dhabe P.S. ^{[1
]}

Nataraj P.S.V. ^{[1
]}

机构：

[1] Systems and Control Engineering Group, Indian Institute of Technology Bombay, Mumbai

来源：

International Journal of System Assurance Engineering and Management | 2017年 / 8卷 / Suppl 2期

关键词：

Bernstein polynomials; GPU computing; Parallel computing; Polynomial global optimization;

D O I：

10.1007/s13198-017-0639-z

中图分类号：

学科分类号：

摘要：

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. © 2017, The Society for Reliability Engineering, Quality and Operations Management (SREQOM), India and The Division of Operation and Maintenance, Lulea University of Technology, Sweden.

引用

页码：1654 / 1671

页数：17

共 29 条

[1]

Cesar Munoz A.N., Formalization of a representation of Bernstein polynomials and applications to global optimization, Autom Reason, 51, 2, pp. 151-196, (2013)

[2]

Dhabe P.S., Parallelization of Bernstein algorithms. Ph. D. annual progress report, systems and control engineering, Indian Institute of Technology, Bombay, India, (2014)

[3]

Farber R., CUDA application design and development, (2011)

[4]

Garloff J., The Bernstein algorithm, Interval Comput, 2, pp. 164-168, (1993)

[5]

Garloff J., The Bernstein expansion and its applications, J Am Rom Acad, 25, (2003)

[6]

Optimizing parallel reduction in CUDA

[7]

Himmelblau D.M., Yetes R.V., Applied nonlinear programming, (1972)

[8]

Kirk D.B., Mei Hwu W., Programming massively parallel processors: a hands on approach, (2010)

[9]

Lorentz G.G., Bernstein polynomials, (1988)

[10]

Nataraj P.S.V., Arounassalame M., A new subdivision algorithm for the Bernstein polynomial approach to global optimization, Int J Autom Comput, 4, 4, pp. 342-352, (2007)

← 1 2 3 →