Quasi Branch and Bound for Smooth Global Optimization
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
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.