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

Wednesday, November 11, 2015: 9:54 AM
Salon F (Salt Lake Marriott Downtown at City Creek)
Rohit Kannan, Dept. of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, MA and Paul I. Barton, Process Systems Engineering Laboratory, Massachusetts Institute of Technology, Cambridge, MA

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 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.

[1] Floudas, C. A. and Gounaris, C. E. (2009). A review of recent advances in global optimization. Journal of Global Optimization45(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 Optimization52(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 Optimization5(3), 253-265.

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

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

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization I
See more of this Group/Topical: Computing and Systems Technology Division