460541 The Cluster Problem in Constrained Global Optimization

Wednesday, November 16, 2016: 10:24 AM
Monterey I (Hotel Nikko San Francisco)
Rohit Kannan, Dept. of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, MA and Paul I. Barton, Process Systems Engineering Laboratory, Massachusetts Institute of Technology, Cambridge, MA

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.

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization I
See more of this Group/Topical: Computing and Systems Technology Division