The cluster problem revisited

In continuous branch-and-bound algorithms, a very large number of boxes near global minima may be visited prior to termination. This so-called cluster problem (J Glob Optim 5(3):253–265, <CitationRef CitationID="CR4">1994</CitationRef>) is revisited and a new analysis is presented. Previous results are confirmed, which state that at least second-order convergence of the relaxations is required to overcome the exponential dependence on the termination tolerance. Additionally, it is found that there exists a threshold on the convergence order pre-factor which can eliminate the cluster problem completely for second-order relaxations. This result indicates that, even among relaxations with second-order convergence, behavior in branch-and-bound algorithms may be fundamentally different depending on the pre-factor. A conservative estimate of the pre-factor is given for <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\alpha $$</EquationSource> </InlineEquation>BB relaxations. Copyright Springer Science+Business Media New York 2014

MoreLess

Year of publication:	2014
Authors:	Wechsung, Achim ; Schaber, Spencer ; Barton, Paul
Published in:	Journal of Global Optimization. - Springer. - Vol. 58.2014, 3, p. 429-438
Publisher:	Springer
Subject:	Cluster problem \| Global optimization \| Convergence order \| Convex relaxations

More details

Extent:	text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10010994042