Abstract
We consider branch and bound methods for enclosing all unconstrained global minimizers of a nonconvex nonlinear twice-continuously differentiable objective function. In particular, we consider bounds obtained with interval arithmetic, with the “midpoint test,” but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable cluster of boxes around each minimizer. In a previous paper, we analyzed this problem for univariate objective functions. In this paper, we generalize that analysis to multi-dimensional objective functions. As in the univariate case, the results show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alefeld, Götz, and Herzberger, J. (1983),Introduction to Interval Computations, Academic Press, New York.
Bleher, J. H., Rump, S. M., Kulisch, U., Metzger, M., Ullrich, C., and Walter, W. (1987), Fortran- SC — A study of a Fortran extension for engineering and scientific computation with access to ACRITH,Computing 39, 93–110.
Cornelius, H. and Lohner, R. (1984), Computing the range of values of real functions with accuracy higher than second order,Computing 33, 331–347.
Hansen, E. R. (1980), Global optimization using interval analysis — the multidimensional case,Numer. Math. 34, 247–270.
Kearfott, R. B. and Novoa, M. (1990), INTBIS, A Portable Interval Newton/Bisection Package (Algorithm 681),ACM Trans. Math. Software 16, 152–157.
Kearfott, R. B. and Du K. (1992), The cluster problem in global optimization, the univariate case,Computing Supplement 9, 117–127.
Moore, Ramon E. (1979),Methods and Applications of Interval Analysis, SIAM, Philadelphia.
Neumaier, A. (1990),Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, England.
Ratschek, H. and Rokne, J. (1984),Computer Methods for the Range of Functions Horwood, Chichester, England.
Ratschek, H. and Rokne, J. (1988),New Computer Methods for Global Optimization, Wiley, New York.
Author information
Authors and Affiliations
Additional information
This work was partially funded by National Science Foundation grant # CCR-9203730.
Rights and permissions
About this article
Cite this article
Du, K., Kearfott, R.B. The cluster problem in multivariate global optimization. J Glob Optim 5, 253–265 (1994). https://doi.org/10.1007/BF01096455
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01096455