Quasi Branch and Bound for Smooth Global Optimization
Abstract
Quasi branch and bound is a recently introduced generalization of branch and bound, where lower bounds are replaced by a relaxed notion of quasi-lower bounds, required to be lower bounds only for sub-cubes containing a minimizer. This paper is devoted to studying the possible benefits of this approach, for the problem of minimizing a smooth function over a cube. This is accomplished by suggesting two quasi branch and bound algorithms, qBnB(2) and qBnB(3), that compare favorably with alternative branch and bound algorithms. The first algorithm we propose, qBnB(2), achieves second order convergence based only on a bound on second derivatives, without requiring calculation of derivatives. As such, this algorithm is suitable for derivative free optimization, for which typical algorithms such as Lipschitz optimization only have first order convergence and so suffer from limited accuracy due to the clustering problem. Additionally, qBnB(2) is provably more efficient than the second order Lipschitz gradient algorithm which does require exact calculation of gradients. The second algorithm we propose, qBnB(3), has third order convergence and finite termination. In contrast with BnB algorithms with similar guarantees who typically compute lower bounds via solving relatively time consuming convex optimization problems, calculation of qBnB(3) bounds only requires solving a small number of Newton iterations. Our experiments verify the potential of both these methods in comparison with state of the art branch and bound algorithms.
Type
Department
Description
Provenance
Citation
Permalink
Collections
Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.