Convergence-order analysis of branch-and-bound algorithms for constrained problems

Simple item page
dc.contributor.authorKannan, Rohiten
dc.contributor.authorBarton, Paul I.en
dc.date.accessioned2025-02-18T13:10:29Zen
dc.date.available2025-02-18T13:10:29Zen
dc.date.issued2017-06-01en
dc.description.abstractThe performance of branch-and-bound algorithms for deterministic global optimization is strongly dependent on the ability to construct tight and rapidly convergent schemes of lower bounds. One metric of the efficiency of a branch-and-bound algorithm is the convergence order of its bounding scheme. This article develops a notion of convergence order for lower bounding schemes for constrained problems, and defines the convergence order of convex relaxation-based and Lagrangian dual-based lower bounding schemes. It is shown that full-space convex relaxation-based lower bounding schemes can achieve first-order convergence under mild assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at Slater points, and at infeasible points when second-order pointwise convergent schemes of relaxations are used. Lagrangian dual-based full-space lower bounding schemes are shown to have at least as high a convergence order as convex relaxation-based full-space lower bounding schemes. Additionally, it is shown that Lagrangian dual-based full-space lower bounding schemes achieve first-order convergence even when the dual problem is not solved to optimality. The convergence order of some widely-applicable reduced-space lower bounding schemes is also analyzed, and it is shown that such schemes can achieve first-order convergence under suitable assumptions. Furthermore, such schemes can achieve second-order convergence at KKT points, at unconstrained points in the reduced-space, and at infeasible points under suitable assumptions when the problem exhibits a specific separable structure. The importance of constraint propagation techniques in boosting the convergence order of reduced-space lower bounding schemes (and helping mitigate clustering in the process) for problems which do not possess such a structure is demonstrated.en
dc.description.versionAccepted versionen
dc.format.extentPages 753-813en
dc.format.extent61 page(s)en
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1007/s10898-017-0532-yen
dc.identifier.eissn1573-2916en
dc.identifier.issn0925-5001en
dc.identifier.issue4en
dc.identifier.orcidKannan, Rohit [0000-0002-7963-7682]en
dc.identifier.urihttps://hdl.handle.net/10919/124620en
dc.identifier.volume71en
dc.language.isoenen
dc.publisherSpringeren
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectGlobal optimizationen
dc.subjectConstrained optimizationen
dc.subjectConvergence orderen
dc.subjectConvex relaxationen
dc.subjectLagrangian dualen
dc.subjectBranch-and-bounden
dc.subjectLower bounding schemeen
dc.subjectReduced-spaceen
dc.titleConvergence-order analysis of branch-and-bound algorithms for constrained problemsen
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:
Convergence-Order Analysis of Branch-and-Bound Algorithms for Constrained Problems.pdf
Size:
1.26 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