Abstract
In a recent paper the authors introduced an infinite class of global optimization algorithms based upon random sampling from the feasible region and local searches started from selected sample points, based upon an acceptance/rejection criterion. All of the algorithms of that class possess strong theoretical properties.
Here we analyze a member of that family, which, although being significantly simpler to implement and more efficient than the well known Multi-Level Single-Linkage algorithm, enjoys the same theoretical properties. It is shown here that, with very high probability, our method is able to discover from which points Multi-Level Single-Linkage will decide to start local search.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Locatelli, M. and Schoen, F.: 1995, ‘Random Linkage: a family of acceptance/rejection algorithms for global optimisation’, Technical Report 156-96, DSI, University of Milano, submitted for publication, available through the www page of the 2nd author.
Lucidi, S. and Piccioni, M.: 1989, ‘Random Tunneling by Means of Acceptance-Rejection Sampling for Global Optimization’. Journal of Optimization Theory and Applications 62, pp. 255–276
Rinnooy Kan, A.H.G. and Timmer, G.T.: 1987, ‘Stochastic Global Optimization Methods. Part I: Clustering Methods’, Mathematical Programming 39, pp. 27–56
Rinnooy Kan, A.H.G. and Timmer, G.T.: 1987, ‘Stochastic Global Optimization Methods. Part II: Multi Level Methods’, Mathematical Programming 39, pp. 57–78
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Locatelli, M., Schoen, F. Simple linkage: Analysis of a threshold-accepting global optimization method. J Glob Optim 9, 95–111 (1996). https://doi.org/10.1007/BF00121752
Issue Date:
DOI: https://doi.org/10.1007/BF00121752