Convergence-Order Analysis of Branch-and-Bound Algorithms for Constrained Problems

Global optimization has found widespread applications in chemical engineering [1]. Deterministic global optimization techniques attempt to determine an approximate optimal solution within a specified tolerance and terminate with a certificate of its optimality in finite time [2]. The performance of branch-and-bound algorithms for deterministic global optimization is strongly dependent on the ability to construct tight and rapidly convergent convex relaxations of nonconvex functions.

Recently, Bompadre and coworkers [3, 4] analyzed the convergence order of convex relaxations based on McCormick, Taylor, and McCormick-Taylor models. They showed that if a function is in C², the scheme of relaxations corresponding to its convex and concave envelopes is at least second-order pointwise convergent which, in turn, implies Hausdorff convergence of at least second-order. Establishing that a scheme of relaxations is at least second-order Hausdorff convergent is important from many viewpoints, notably in mitigating the so-called cluster problem in unconstrained problems [5-7]. A similar analysis of clustering and convergence order for constrained optimization algorithms is lacking.

In this work, we investigate the convergence order of branch-and-bound algorithms in global optimization by extending the convergence analysis of Bompadre and coworkers to constrained problems. Specifically, we propose a definition of the convergence order for constrained optimization problems, and analyze the convergence order of commonly used branch-and-bound schemes.

[1] Floudas, C. A. and Gounaris, C. E. (2009). A review of recent advances in global optimization. Journal of Global Optimization, 45(1), 3-38.

[2] Horst, R. and Tuy, H. (1996). Global optimization: Deterministic approaches. Springer Science & Business Media.

[3] Bompadre, A. and Mitsos, A. (2012). Convergence rate of McCormick relaxations. Journal of Global Optimization, 52(1), 1-28.

[4] Bompadre, A., Mitsos, A., and Chachuat, B. (2013). Convergence analysis of Taylor models and McCormick-Taylor models. Journal of Global Optimization, 57(1), 75-114.

[5] Du, K. and Kearfott, R. B. (1994). The cluster problem in multivariate global optimization. Journal of Global Optimization, 5(3), 253-265.

[6] Wechsung, A., Schaber, S. D., and Barton, P. I. (2014). The cluster problem revisited. Journal of Global Optimization, 58(3), 429-438.

[7] Goldsztejn, A., Domes, F., and Chevalier, B. (2014). First order rejection tests for multiple-objective optimization. Journal of Global Optimization, 58(4), 653-672.