An Enhanced Spatial Branch-and-Bound Method in Global Optimization with Nonconvex Constraints
Peter Kirst (kirstkit.edu)
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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|