Abstract
Geometric branch-and-bound methods are commonly used solution algorithms for non-convex global optimization problems in small dimensions, say for problems with up to six or ten variables, and the efficiency of these methods depends on some required lower bounds. For example, in interval branch-and-bound methods various well-known lower bounds are derived from interval inclusion functions. The aim of this work is to analyze the quality of interval inclusion functions from the theoretical point of view making use of a recently introduced and general definition of the rate of convergence in geometric branch-and-bound methods. In particular, we compare the natural interval extension, the centered form, and Baumann’s inclusion function. Furthermore, our theoretical findings are justified by detailed numerical studies using the Weber problem on the plane with some negative weights as well as some standard global optimization benchmark problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baumann E.: Optimal centered forms. BIT Numer. Math. 28, 80–87 (1988)
Blanquero R., Carrizosa E.: Continuous location problems and big triangle small triangle: constructing better bounds. J. Global Optim. 45, 389–402 (2009)
Chuba W., Miller W.: Quadratic convergence in interval arithmetic. Part I. BIT Numer. Math. 12, 284–290 (1972)
Csallner A.E., Csendes T.: The convergence speed of interval methods for global optimization. Comput. Math. Appl. 31, 173–178 (1996)
Drezner Z., Suzuki A.: The big triangle small triangle method for the solution of nonconvex facility location problems. Oper. Res. 52, 128–135 (2004)
Fernández J., Pelegrín B., Plastria F., Tóth B.: Solving a Huff-like competitive location and design model for profit maximization in the plane. Eur. J. Oper. Res. 179, 1274–1287 (2007)
Floudas C.A., Pardalos P.M.: Encyclopedia of Optimization. 2nd edn. Springer, New York (2009)
Hansen E.: Global Optimization Using Interval Analysis. 1st edn. Marcel Dekker, New York (1992)
Hansen P., Peeters D., Richard D., Thisse J.F.: The minisum and minimax location problems revisited. Oper. Res. 33, 1251–1265 (1985)
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. 2nd edn. Springer, Berlin (2000)
Krawczyk R., Nickel K.: Die zentrische Form in der Intervallarithmetik, ihre quadratische Konvergenz und ihre Inklusionsisotonie. Computing 28, 117–137 (1982)
Neumaier A.: Interval Methods for Systems of Equations. 1st edn. Cambridge University Press, Cambridge (1990)
Plastria F.: GBSSS: the generalized big square small square method for planar single-facility location. Eur. J. Oper. Res. 62, 163–174 (1992)
Ratschek H., Rokne J.: New Computer Methods for Global Optimization. 1st edn. Ellis Horwood, Chichester, England (1988)
Ratschek H., Voller R.L.: What can interval analysis do for global optimization?. J. Global Optim. 1, 111–130 (1991)
Schöbel A., Scholz D.: The theoretical and empirical rate of convergence for geometric branch-and-bound methods. J. Global Optim. 48, 473–495 (2010)
Schwefel H.P.: Numerical Optimization of Computer Models. 1st edn. Wiley, New York (1981)
Tóth B., Csendes T.: Empirical investigation of the convergence speed of inclusion functions in a global optimization context. Reliab. Comput. 11, 253–273 (2005)
Tóth B., Fernández J., Csendes T.: Empirical convergence speed of inclusion functions for facility location problems. J. Comput. Appl. Math. 199, 384–389 (2007)
Tóth B., Fernández J., Pelegrín B., Plastria F.: Sequential versus simultaneous approach in the location and design of two new facilities using planar Huff-like models. Comput. Oper. Res. 36, 1393–1405 (2009)
Tuy H., Al-Khayyal F., Zhou F.: A D.C. optimization method for single facility location problems. J. Global Optim. 7, 209–227 (1995)
Acknowledgments
The author would like to thank Anita Schöbel for fruitful suggestions for improving the paper. Furthermore, the author gratefully acknowledges the three anonymous referees for their helpful comments.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Scholz, D. Theoretical rate of convergence for interval inclusion functions. J Glob Optim 53, 749–767 (2012). https://doi.org/10.1007/s10898-011-9735-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9735-9