(449f) Enhancing the Performance of the Abb Algorithm through the Use of Interval and Convexity Tests

As system complexity grows, the deterministic global optimization of engineering problems becomes more relevant than ever before. Solving problems to global optimality with a guarantee is essential in many classes of problems, e.g. phase equilibrium [1], where the global solution is the only physically meaningful state of the real system, and parameter estimation [2]. Deterministic global optimization is also becoming increasingly important in many disciplines, as the difference between finding the global solution or a local one may lead to increased competitiveness. Furthermore, deterministic global optimization methods can provide a guaranteed answer which is otherwise impossible to retrieve in the general case: whether a problem is feasible or not. This information can be invaluable in heavily constrained problems where even finding a feasible starting point is a challenge.

Many approaches have been proposed over the past four decades to solve problems to global optimality in a deterministic manner. One such approach for general engineering problems is the αBB algorithm, developed by Androulakis, Maranas and Floudas [3], with numerous subsequent contributions [4][5][6]. However, while this algorithm can deal with many classes of nonconvexity, it can exhibit slow convergence in some classes of problems, especially as the number of nonlinear variables increases.

We investigate improvements to the performance of the αBB algorithm for general nonlinear non-convex problems using different approaches to underestimation and problem formulation. Our strategies include the use of interval arithmetic during the bounding process, and the use of different approaches to problem formulation in order to generate the lower bounding problem. Problem formulation is well known to impact the performance of spatial branch and bound algorithms [7], therefore the lower bounding problem is reformulated such that any underlying convexity is exploited to produce tighter underestimators. We demonstrate the impact of these approaches across a set of test problems from standard libraries, using a C++ implementation of the αBB algorithm in the open source MINOTAUR [8] framework.

[1] Floudas, C.A., “Deterministic Global Optimization in Design, Control, and Computational Chemistry,” Large Scale Optimization with Applications, 93, pp. 129-184, (1997)

[2] Amaran, S. and Sahinidis, N.V., “Global Optimization of Nonlinear Least-squares Problems by Branch-and- bound and Optimality Constraints,” Top, 20, pp. 154–172 (2012)

[3] Androulakis, I.P. et al., “αBB: A Global Optimization Method for General Con- strained Nonconvex Problems,” Journal of Global Optimization, 7, pp. 337–363 (1995)

[4] Adjiman, C.S. et al., “A global Optimization Method, αBB, for General Twice-Differentiable Constrained NLPs–I. Theoretical Advances,” Computers & Chemical Engineering , 22, pp. 1137–1158 (1998)

[5] Akrotirianakis, I.G. et al., “A New Class of Improved Convex Underestimators for Twice Continuously Differentiable Constrained NLPs,” Journal of Global Optimization, 30, pp. 367–390 (2004)

[6] Skjal, A. et al. “A Generalization of the Classical αBB Convex Underestimation via Diagonal and Nondiagonal Quadratic Terms,” Journal of Optimization Theory and Applications, 154, pp. 462–490 (2012)

[7] Misener, R., and Floudas, C. A., “ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations,” Journal of Global Optimization, 59, pp. 503-526 (2014)

[8] Mahajan, A. et al., “MINOTAUR: Toolkit for Mixed Integer Nonlinear Optimization Problems,” Argonne National Lab, Chicago (2008-2015)