Skip to main content
Log in

New methods for calculating \(\alpha \)BB-type underestimators

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

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

    Article  Google Scholar 

  2. Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: Global optimization of mixed-integer nonlinear problems. AIChE J. 46(9), 1769–1797 (2000)

    Article  Google Scholar 

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

    Google Scholar 

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

  5. Ayres, F.: Schaum’s Outline of Theory and Problems of Matrices. McGraw-Hill, New York (1962)

    Google Scholar 

  6. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    Book  Google Scholar 

  7. Brauer, A.: Limits for the characteristic roots of a matrix II. Duke Math. J. 14, 21–26 (1947)

    Article  Google Scholar 

  8. Castillo, I., Westerlund, T.: An \(\varepsilon \)-accurate model for optimal unequal-area block layout design. Comput. Oper. Res. 32(3), 429–447 (2005)

    Article  Google Scholar 

  9. Floudas, C.A.: Deterministic Global Optimization. Kluwer, Dordrecht (2000)

    Book  Google Scholar 

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

    Book  Google Scholar 

  11. Gerschgorin, S.: Über die abgrenzung der eigenwerte einer matrix. Izv. Akad. Nauk SSSR, Ser, Fiz. mat. 6, 749–754 (1931)

    Google Scholar 

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

    Article  Google Scholar 

  13. Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, version 1.21 (2011). http://cvxr.com/cvx/

  14. Hansen, E., Walster, G.W.: Global Optimization using Interval Analysis, 2nd edn. Marcel Dekker, New York (2004)

  15. Liu, W.B., Floudas, C.A.: A remark on the GOP algorithm for global optimization. J. Glob. Optim. 3, 519–521 (1993)

    Google Scholar 

  16. Maranas, C.D., Floudas, C.A.: A global optimization approach for Lennard-Jones microclusters. J. Chem. Phys. 97(10), 7667–7678 (1992)

    Article  Google Scholar 

  17. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I–convex underestimating problems. Math. Program. 10, 147–175 (1976)

    Article  Google Scholar 

  18. Neumaier, A.: Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1990)

    Google Scholar 

  19. Rohn, J.: Bounds on eigenvalues of interval matrices. Zeitschrift für Angewandte Mathematik und Mechanik 78, 1049–1050 (1998)

    Article  Google Scholar 

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

    Google Scholar 

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

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  23. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming—Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002)

  24. Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Program. 99, 563–591 (2004)

    Article  Google Scholar 

  25. Varga, R.S.: Geršgorin and His Circles. Springer, Berlin (2004)

    Book  Google Scholar 

  26. Zlobec, S.: Characterization of convexifiable functions. Optimization 55(3), 251–261 (2006)

    Article  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Tapio Westerlund.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-013-0057-y

Keywords

Mathematics Subject Classification (2000)

Navigation