Approximate branch-and-bound global optimization using B-spline hypervolumes

摘要

This paper presents a B-spline-based branch-and-bound algorithm for unconstrained global optimization. The key components of the branch-and-bound, a well-known algorithm paradigm for global optimization, are a subdivision scheme and a bound calculation scheme. For these schemes, we first introduce a B-spline hypervolume to approximate an objective function defined in a design space, where the approximation is based on Latin-hypercube sampling points. We then describe a proposed algorithm for finding global solutions approximately within a prescribed tolerance. The algorithm includes two procedures that are performed iteratively until all stopping conditions are satisfied. One involves subdivision into mutually disjoint subspaces and computation of their bound information, both of which are accomplished by using B-spline hypervolumes. The other updates a search tree that represents a hierarchical structure of subdivided subspaces during the solution process. Finally, we examine the computational performance of the proposed algorithm on various test problems that cover most of the difficulties encountered in global optimization. The results show that the proposed algorithm is complete without using heuristics and has good potential for application in large-scale NP-hard optimization.