Optimization Online


An Enhanced Spatial Branch-and-Bound Method in Global Optimization with Nonconvex Constraints

Peter Kirst (kirst***at***kit.edu)
Oliver Stein (stein***at***kit.edu)
Paul Steuermann (numerik***at***gmx.de)

Abstract: We discuss some difficulties in determining valid upper bounds in spatial branch-and-bound methods for global minimization in the presence of nonconvex constraints. In fact, two examples illustrate that standard techniques for the construction of upper bounds may fail in this setting. Instead, we propose to perturb infeasible iterates along Mangasarian-Fromovitz directions to feasible points whose objective function values serve as upper bounds. These directions may be calculated by the solution of a single linear optimization problem per iteration. Numerical results show that our enhanced algorithm performs well even for optimization problems where the standard branch-and-bound method does not converge to the correct optimal value.

Keywords: Branch-and-bound, convergence, consistency, Mangasarian-Fromovitz constraint qualification

Category 1: Global Optimization

Citation: TOP, to appear.


Entry Submitted: 03/22/2013
Entry Accepted: 04/01/2013
Entry Last Modified: 06/09/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society