Abstract
In the framework of multistart and local search algorithms that find the global minimum of a real function f(x), \( x \in S\subseteq R^n\), Gaviano et alias proposed a rule for deciding, as soon as a local minimum has been found, whether to perform or not a new local minimization. That rule was designed to minimize the average local computational cost \(eval_1(\cdotp)\) required to move from the current local minimum to a new one. In this paper the expression of the cost \(eval_2(\cdotp)\) of the entire process of getting a global minimum is found and investigated; it is shown that \(eval_2(\cdotp)\) has among its components \(eval_1(\cdotp)\) and can be only monotonically increasing or decreasing; that is, it exhibits the same property of \(eval_1(\cdotp)\). Moreover, a counterexample is given that shows that the optimal values given by \(eval_1(\cdotp)\) and \(eval_2(\cdotp)\) might not agree. Further, computational experiments of a parallel algorithm that uses the above rule are carried out in a MatLab environment.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Boender, C.G.E., Rinnooy Kan, A.H.G.: Bayesian stopping rules for a class of stochastic global optimization methods. Technical Report Report 8319/0, Erasmus University Rotterdam (1985)
Cetin, B.C., Barhen, J., Burdick, J.W.: Terminal repeller unconstrained subenergy tunnelling (trust) for fast global optimization. J. Optim. Theory Appl. 77(1), 97–126 (1993)
Desai, R., Patil, R.: Salo: combining simulated annealing and local optimization for efficient global optimization. In: Proceedings of the 9th Florida AI Research Simposium, FLAIRS-96’, pp. 233–237 (1996)
Eskow, E., Schnabel, R.B.: Mathematical modelling of a parallel global optimization algorithm. Parallel Comput. 12(3), 315–325 (1989)
Floudas, C.A., Pardalos, P.M.: A Collection of Test Problems for Constraint Global Optimization Algorithms. Springer, Berlin Heidelberg (1990)
Gaviano, M., Kvasov, D.E., Lera, D., Sergeyev, Y.D.: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. 29(4), 469–480 (2003)
Gaviano, M., Lera, D.: Test functions with variable attraction regions for global optimization problems. J. Glob. Optim. 13(2), 207–223 (1998)
Gaviano, M., Lera, D., Steri A.M.: A local search method for continuous global optimization. J. Glob. Optim. 48, 73–85 (2010)
Gergel, V.P., Sergeyev, Ya.D.: Sequential and parallel global optimization algorithms using derivatives. Comput. Math. Appl. 37(4/5), 163–180 (1999)
Hedar, A.R., Fukushima, M.: Tabu search directed by direct search methods for non linear global optimization. Eur. J. Oper. Res. 170(2), 329–349 (2006)
Kelley, C.T.: Iterative Methods for Optimization. SIAM, Philadelphia (1999)
Levy, A., Montalvo, A.: The tunneling algorithm for the global minimization of functions. SIAM J. Sci. Statist. Comput. 6, 15–29 (1985)
Lucidi, S., Piccioni, M.: Random tunneling by means of acceptance-rejection sampling for global optimization. J. Optim. Theory Appl. 62(2), 255–277 (1989)
Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons, Chichester (1983)
Oblow, E.M., Spt: a stochastic tunneling algorithm for global optimization. J. Glob. Optim. 20, 195–212 (2001)
Rastrigin, L.A.: Systems of Extreme Control. Nauka, Moscow (1974)
Rudolph, G.: Parallel approaches to stochastic global optimization. In: Joosen, W., Milgrom, E. (eds.) Parallel Computing: from Theory to Sound Practice, pp. 256–267. IOS (1992)
Sergeyev, Ya.D.: Parallel information algorithm with local tuning for solving multidimensional go problems. J. Glob. Optim. 15(2), 157–167 (1999)
Vavasis, S.A.: Complexity issues in global optimization: a survey. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp. 27–41. Kluwer Academic Publishers (1995)
Čiegis, R., Baravykaité, M., Belevičius, R.: Parallel global optimization of foundation schemes in civil engineering. In: Applied Parallel Computing. State of the Art in Scientific Computing, Lecture Notes in Computer Science, vol. 3732/2006, pp. 305–312 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gaviano, M., Lera, D. Properties and numerical testing of a parallel global optimization algorithm. Numer Algor 60, 613–629 (2012). https://doi.org/10.1007/s11075-012-9590-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9590-x