Performance of convex underestimators in a branch-and-bound framework
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2014, Springer-Verlag Berlin Heidelberg. The efficient determination of tight lower bounds in a branch-and-bound algorithm is crucial for the global optimization of models spanning numerous applications and fields. The global optimization method -branch-and-bound (BB, Adjiman et al. in Comput Chem Eng 22(9):11591179, 1998b, Comput Chem Eng 22(9):11371158, 1998a; Adjiman and Floudas in J Global Optim 9(1):2340, 1996; Androulakis et al. J Global Optim 7(4):337363, 1995; Floudas in Deterministic Global Optimization: Theory, Methods and Applications, vol. 37. Springer, Berlin, 2000; Maranas and Floudas in J Chem Phys 97(10):76677678, 1992, J Chem Phys 100(2):12471261, 1994a, J Global Optim 4(2):135170, 1994), guarantees a global optimum with -convergence for any C2-continuous function within a finite number of iterations via fathoming nodes of a branch-and-bound tree. We explored the performance of the BB method and a number of competing methods designed to provide tight, convex underestimators, including the piecewise (Meyer and Floudas in J Global Optim 32(2):221258, 2005), generalized (Akrotirianakis and Floudas in J Global Optim 30(4):367390, 2004a, J Global Optim 29(3):249264, 2004b), and nondiagonal (Skjl et al. in J Optim Theory Appl 154(2):462490, 2012) BB methods, the Brauer and Rohn+E (Skjl et al. in J Global Optim 58(3):411427, 2014) BB methods, and the moment method (Lasserre and Thanh in J Global Optim 56(1):125, 2013). Using a test suite of 40 multivariate, box-constrained, nonconvex functions, the methods were compared based on the tightness of generated underestimators and the efficiency of convergence of a branch-and-bound global optimization algorithm.
