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

DOI10.1007/s10898-017-0532-yzbMath1397.49042OpenAlexW2620905467MaRDI QIDQ1668796

Paul I. Barton, Rohit Kannan

Publication date: 29 August 2018

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/117047

zbMATH Keywords

global optimizationconstrained optimizationbranch-and-boundconvex relaxationconvergence orderLagrangian duallower bounding schemereduced-space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Numerical methods involving duality (49M29) Numerical methods based on nonlinear programming (49M37) Duality theory (optimization) (49N15) Numerical methods of relaxation type (49M20)

Related Items (4)

Norm-optimal iterative learning control in an integer-valued control domain ⋮ New pseudo polynomial algorithms for a partial resource-constrained project scheduling problem ⋮ Comparison of MINLP formulations for global superstructure optimization ⋮ Tighter McCormick relaxations through subgradient propagation

Uses Software

• CVX
• ANTIGONE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convergence analysis of Taylor models and McCormick-Taylor models
• Differentiable McCormick relaxations
• Convergence analysis of multivariate McCormick relaxations
• Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs
• The theoretical and empirical rate of convergence for geometric branch-and-bound methods
• Convergence rate of McCormick relaxations
• Theoretical rate of convergence for interval inclusion functions
• The cluster problem revisited
• A review of recent advances in global optimization
• Die zentrische Form in der Intervallarithmetik, ihre quadratische Konvergenz und ihre Inklusionsisotonie
• The convergence rate of the sandwich algorithm for approximating convex functions
• Global minimization by reducing the duality gap
• The cluster problem in multivariate global optimization
• A reduced space branch and bound algorithm for global optimization.
• Lagrange duality and partitioning techniques in nonconvex global optimization
• Convex extensions and envelopes of lower semi-continuous functions
• Convex envelopes of monomials of odd degree
• The cluster problem in constrained global optimization
• A polyhedral branch-and-cut approach to global optimization
• Rigorous convex underestimators for general twice-differentiable problems
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
• Multivariate McCormick relaxations
• Lectures on Modern Convex Optimization
• Convex and concave relaxations of implicit functions
• Branching and bounds tighteningtechniques for non-convex MINLP
• Introduction to Interval Analysis
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Convex Analysis
• Dual bounding procedures lead to convergent branch-and-bound algorithms

This page was built for publication: Convergence-order analysis of branch-and-bound algorithms for constrained problems