Abstract
Most branch-and-bound algorithms in global optimization depend on convex underestimators to calculate lower bounds of a minimization objective function. The \(\alpha \)BB methodology produces such underestimators for sufficiently smooth functions by analyzing interval Hessian approximations. Several methods to rigorously determine the \(\alpha \)BB parameters have been proposed, varying in tightness and computational complexity. We present new polynomial-time methods and compare their properties to existing approaches. The new methods are based on classical eigenvalue bounds from linear algebra and a more recent result on interval matrices. We show how parameters can be optimized with respect to the average underestimation error, in addition to the maximum error commonly used in \(\alpha \)BB methods. Numerical comparisons are made, based on test functions and a set of randomly generated interval Hessians. The paper shows the relative strengths of the methods, and proves exact results where one method dominates another.
Similar content being viewed by others
References
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, \(\alpha \)BB, for general twice-differentiable constrained NLPs–II. Implementation and computational results. Comput. Chem. Eng. 22(9), 1159–1179 (1998)
Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: Global optimization of mixed-integer nonlinear problems. AIChE J. 46(9), 1769–1797 (2000)
Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, \(\alpha \)BB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137– 1158 (1998)
Akrotirianakis, I.G., Meyer, C.A., Floudas, C.A.: The role of the off-diagonal elements of the hessian matrix in the construction of tight convex underestimators for nonconvex functions. In: Foundations of, Computer-Aided Design (FOCAPD’04) (2004)
Ayres, F.: Schaum’s Outline of Theory and Problems of Matrices. McGraw-Hill, New York (1962)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Brauer, A.: Limits for the characteristic roots of a matrix II. Duke Math. J. 14, 21–26 (1947)
Castillo, I., Westerlund, T.: An \(\varepsilon \)-accurate model for optimal unequal-area block layout design. Comput. Oper. Res. 32(3), 429–447 (2005)
Floudas, C.A.: Deterministic Global Optimization. Kluwer, Dordrecht (2000)
Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gümüs, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization. Kluwer, Dordrecht (1999)
Gerschgorin, S.: Über die abgrenzung der eigenwerte einer matrix. Izv. Akad. Nauk SSSR, Ser, Fiz. mat. 6, 749–754 (1931)
Gounaris, C.E., Floudas, C.A.: Tight convex underestimators for \({\fancyscript {C}}^2\)-continuous problems: II. Multivariate functions. J. Glob. Optim. 42(1), 69–89 (2008)
Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, version 1.21 (2011). http://cvxr.com/cvx/
Hansen, E., Walster, G.W.: Global Optimization using Interval Analysis, 2nd edn. Marcel Dekker, New York (2004)
Liu, W.B., Floudas, C.A.: A remark on the GOP algorithm for global optimization. J. Glob. Optim. 3, 519–521 (1993)
Maranas, C.D., Floudas, C.A.: A global optimization approach for Lennard-Jones microclusters. J. Chem. Phys. 97(10), 7667–7678 (1992)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I–convex underestimating problems. Math. Program. 10, 147–175 (1976)
Neumaier, A.: Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1990)
Rohn, J.: Bounds on eigenvalues of interval matrices. Zeitschrift für Angewandte Mathematik und Mechanik 78, 1049–1050 (1998)
Skjäl, A., Westerlund, T., Misener, R., Floudas, C.A.: A generalization of the classical \(\alpha \)BB convex underestimation via diagonal and non-diagonal quadratic terms. J. Optim. Theory Appl. 154(2), 462– 490 (2012)
Smith, E., Pantelides, C.: Global optimization of general process models. In: Grossmann, I.E. (ed.) Global Optimization in Engineering Design, pp. 355–386. Kluwer, Dordrecht (1996)
Smith, E., Pantelides, C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23, 457–478 (1999)
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming—Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002)
Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Program. 99, 563–591 (2004)
Varga, R.S.: Geršgorin and His Circles. Springer, Berlin (2004)
Zlobec, S.: Characterization of convexifiable functions. Optimization 55(3), 251–261 (2006)
Acknowledgments
The authors gratefully acknowledge financial support from the Center of Excellence in Optimization and Systems Engineering at Åbo Akademi University. A.S. acknowledges a grant from the Walter Ahlström Foundation.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Skjäl, A., Westerlund, T. New methods for calculating \(\alpha \)BB-type underestimators. J Glob Optim 58, 411–427 (2014). https://doi.org/10.1007/s10898-013-0057-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-013-0057-y