(456g) The Cluster Problem in Constrained Global Optimization

A key issue in continuous global optimization is the so-called cluster problem where a large number of boxes may be visited in the vicinity of a global optimizer [1â??3]. While it is well-known that at least second-order Hausdorff convergence of the scheme of relaxations is usually required to eliminate the cluster problem for unconstrained optimization, a similar result for constrained optimization was unknown prior to this work. This work analyzes the cluster problem for constrained optimization based on a recently proposed definition of convergence order of bounding schemes for constrained problems. Conditions under which first-order and second-order convergent bounding schemes are sufficient to mitigate the cluster problem are provided, based on suitable assumptions.

[1] K. Du and R. B. Kearfott, â??The cluster problem in multivariate global optimization,â? Journal of Global Optimization, vol. 5, no. 3, pp. 253â??265, 1994.
[2] A. Neumaier, â??Complete search in continuous global optimization and constraint satisfaction,â? Acta Numerica, vol. 13, pp. 271â??369, 2004.
[3] A. Wechsung, S. D. Schaber, and P. I. Barton, â??The cluster problem revisited,â? Journal of Global Optimization, vol. 58, no. 3, pp. 429â??438, 2014.