A Parallel Algorithm for Global Optimization Problems in a Distribuited Computing Environment

Marco Gaviano, Daniela Lera, Elisabetta Mereu

Department of Mathematics and Informatics, University of Cagliari, Cagliari, Italy.

DOI: 10.4236/am.2012.330194                

Abstract

The problem of finding a global minimum of a real function on a set S Rn occurs in many real world problems. Since its computational complexity is exponential, its solution can be a very expensive computational task. In this paper, we introduce a parallel algorithm that exploits the latest computers in the market equipped with more than one processor, and used in clusters of computers. The algorithm belongs to the improvement of local minima algorithm family, and carries on local minimum searches iteratively but trying not to find an already found local optimizer. Numerical experiments have been carried out on two computers equipped with four and six processors; fourteen configurations of the computing resources have been investigated. To evaluate the algorithm performances the speedup and the efficiency are reported for each configuration.

Keywords

Random Search; Global Optimization; Parallel Computing

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. G. Strongin and Y. D. Sergeyev, “Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms,” Kluver Academic Press, Dordrecht, 2000.
[2]	R. Horst and P. M. Pardalos, “Handbook of Global Optimization,” Kluver Academic Press, Dordrecht, 1995.
[3]	R. Horst, P. M. Pardalos and N. V. Thoay, “Introduction to Global Optimization,” Kluver Academic Press, Dordrecht, 1995.
[4]	C. A. Floudas and P. M. Pardalos, “State of the Art in Global Optimization,” Kluwer Academic Publishers, Dordrecht, 1996.
[5]	J. D. Pintér, “Global Optimization in Action,” Kluwer Academic Publishers, Dordrecht, 1996.
[6]	H. Tuy, “Convex Analysis and Global Optimization,” Kluwer Academic Publishers, Dordrecht, 1998.
[7]	P. M. Pardalos and H. E. Romeijn, “Handbook of Global Optimization Volume 2,” Kluwer Academic Publishers, Dordrecht, 2002.
[8]	P. M. Pardalos and T. F. Coleman, “Lectures on Global Optimization,” Fields Communications Series, Vol. 55, American Mathematical Society, 2009, pp. 1-16.
[9]	V. P. Gergel and Y. D. Sergeyev, “Sequential and Parallel Global Optimization Algorithms Using Derivatives,” Computer & Mathematics with Applications, Vol. 37, No. 4-5, 1999, pp. 163-180. doi:10.1016/S0898-1221(99)00067-X
[10]	Y. D. Sergeyev, “Parallel Information Algorithm with Local Tuning for Solving Multidimensional GO Problems,” Journal of Global Optimization, Vol. 15, No. 2, 1999, pp. 157-167. doi:10.1023/A:1008372702319
[11]	E. Eskow and R. B. Schnabel, “Mathematical Modelling of a Parallel Global Optimization Algorithm,” Parallel Computing, Vol. 12, No. 3, 1989, pp. 315-325. doi:10.1016/0167-8191(89)90089-6
[12]	R. Ciegis, M. Baravykaite and R. Belevicius, “Parallel Global Optimization of Foundation Schemes in Civil Engineering,” Applied Parallel Computing. State of the Art in Scientific Computing, Lecture Notes in Computer Science, Vol. 3732, 2006, pp. 305-312.
[13]	G. Rudolph, “Parallel Approaches to Stochastic Global Optimization,” In: W. Joosen and E. Milgrom, Eds., Parallel Computing: From Theory to Sound Practice, IOS, IOS Press, Amsterdam, 1992, pp. 256-267.
[14]	C. G. E. Boender and A. H. G. Rinooy Kan, “Bayesian Stopping Rules for a Class of Stochastic Global Optimization Methods,” Erasmus University Rotterdam, Report 8319/0, 1985.
[15]	A. S. Nemirovsky and D. B. Yudin, “Problem Complexity and Method Efficiency in Optimization,” John Wiley and Sons, Chichester, 1983.
[16]	S. A. Vavasis, “ Complexity issues in global optimization: a survey,” In: R. Horst and P. M. Pardalos, Eds., Handbook of Global Optimization, Kluwer Academic Publishers, Dordrecht, 1995, pp. 27-41.
[17]	M. Gaviano, D. Lera and A. M. Steri, “A Local Search Method for Continuous Global Optimization,” SIAM Journal on Scientific Computing, Vol. 6, No. 1, 1985, pp. 15-29.
[18]	A. Levy and A. Montalvo, “The Tunneling Method for Global Optimization,” Journal of Global Optimization, Vol.48, 2010, pp. 73-85.
[19]	C. A. Floudas and P. M. Pardalos, “A Collection of Test Problems for Constraint Global Optimization Algorithms,” Springer-Verlag, Berlin Heidelberg, 1990. doi:10.1007/3-540-53032-0
[20]	L. A. Rastrigin, “Systems of Extreme Control,” Nauka, Moscow, 1974.
[21]	M. Gaviano and D. Lera, “Test Functions with Variable Attraction Regions for Global Optimization Problems,” Journal of Global Optimization, Vol. 13, No. 2, 1998, pp. 207-223. doi:10.1023/A:1008225728209
[22]	M. Gaviano, D. E. Kvasov, D. Lera and Y. D. Sergeyev, “Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization,” ACM, Transaction on Mathematical Software, Vol.29, No. 4, 2003, pp. 469-480. doi:10.1145/962437.962444
[23]	C. T. Kelley, “Iterative Methods for Optimization,” SIAM, Philadelphia, 1999. doi:10.1137/1.9781611970920