The cluster problem in constrained global optimization

Simple item page
dc.contributor.authorKannan, Rohiten
dc.contributor.authorBarton, Paul I.en
dc.date.accessioned2025-02-18T13:09:50Zen
dc.date.available2025-02-18T13:09:50Zen
dc.date.issued2017-05-11en
dc.description.abstractDeterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions.en
dc.description.versionAccepted versionen
dc.format.extentPages 629-676en
dc.format.extent48 page(s)en
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1007/s10898-017-0531-zen
dc.identifier.eissn1573-2916en
dc.identifier.issn0925-5001en
dc.identifier.issue3en
dc.identifier.orcidKannan, Rohit [0000-0002-7963-7682]en
dc.identifier.urihttps://hdl.handle.net/10919/124619en
dc.identifier.volume69en
dc.language.isoenen
dc.publisherSpringeren
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectCluster problemen
dc.subjectGlobal optimizationen
dc.subjectConstrained optimizationen
dc.subjectBranch-and-bounden
dc.subjectConvergence orderen
dc.subjectConvex relaxationen
dc.subjectLower bounding schemeen
dc.titleThe cluster problem in constrained global optimizationen
dc.title.serialJournal of Global Optimizationen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
dc.type.otherArticleen
dc.type.otherJournalen
pubs.organisational-groupVirginia Techen
pubs.organisational-groupVirginia Tech/Engineeringen
pubs.organisational-groupVirginia Tech/Engineering/Industrial and Systems Engineeringen
pubs.organisational-groupVirginia Tech/All T&R Facultyen
pubs.organisational-groupVirginia Tech/Engineering/COE T&R Facultyen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
The Cluster Problem in Constrained Global Optimization.pdf
Size:
1.39 MB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.5 KB
Format:
Plain Text
Description:
Download

Collections

All Faculty Deposits
Scholarly Works, Industrial and Systems Engineering