(449e) Convergence-Order Analysis of Branch-and-Bound Algorithms for Constrained Problems
Global optimization has found widespread applications in chemical engineering . 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 . 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 C2, 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.
 Floudas, C. A. and Gounaris, C. E. (2009). A review of recent advances in global optimization. Journal of Global Optimization, 45(1), 3-38.
 Horst, R. and Tuy, H. (1996). Global optimization: Deterministic approaches. Springer Science & Business Media.
 Bompadre, A. and Mitsos, A. (2012). Convergence rate of McCormick relaxations. Journal of Global Optimization, 52(1), 1-28.
 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.
 Du, K. and Kearfott, R. B. (1994). The cluster problem in multivariate global optimization. Journal of Global Optimization, 5(3), 253-265.
 Wechsung, A., Schaber, S. D., and Barton, P. I. (2014). The cluster problem revisited. Journal of Global Optimization, 58(3), 429-438.
 Goldsztejn, A., Domes, F., and Chevalier, B. (2014). First order rejection tests for multiple-objective optimization. Journal of Global Optimization, 58(4), 653-672.