Skip to main content
SpringerLink
Log in

On the selection of subdivision directions in interval branch-and-bound methods for global optimization

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

Abstract

This paper investigates the influence of the interval subdivision selection rule on the convergence of interval branch-and-bound algorithms for global optimization. For the class of rules that allows convergence, we study the effects of the rules on a model algorithm with special list ordering. Four different rules are investigated in theory and in practice. A wide spectrum of test problems is used for numerical tests indicating that there are substantial differences between the rules with respect to the required CPU time, the number of function and derivative evaluations, and the necessary storage space. Two rules can provide considerable improvements in efficiency for our model algorithm.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alefeld G. and Herzberger J. (1983),Introduction to Interval Computations, Academic Press, New York.

    Google Scholar 

  2. Benson, H. P. (1982),On the Convergence of two Branch-and-Bound Algorithms for Nonconvex Programming Problems, J. Optim. Theory and Appl.,36, 129–134.

    Google Scholar 

  3. Caprani, O., Godthaab, B., and Madsen, K. (1993),Use of a Real-Valued Local Minimum in Parallel Interval Global Optimization, Interval Computations,3, 71–82.

    Google Scholar 

  4. Csendes, T. (1988),Nonlinear Parameter Estimation by Global Optimization —Efficiency and Reliability, Acta Cybemetica,8, 361–370.

    Google Scholar 

  5. Csendes, T. and Pintér, J. (1993),The Impact of Accelerating Tools on the Interval Subdivision Algorithm for Global Optimization, European J. of Operational Research,65, 314–320.

    Google Scholar 

  6. Csendes, T. and Ratz, D. (1995),Subdivision Direction Selection in Interval Methods for Global Optimization, submitted for publication.

  7. Hammer, R., Hocks, M., Kulisch, U., and Ratz, D. (1993),Numerical Toolbox for Verified Computing I, Springer-Verlag, Berlin.

    Google Scholar 

  8. Hansen, E. (1992),Global Optimization Using Interval Analysis, Marcel Dekker, New York.

    Google Scholar 

  9. Jansson, C. and Knüppel, O. (1992),A Global Minimization Method: the Multi-Dimensional Case, Report 92.1, Technische Universitüt Hamburg-Harburg.

  10. Jones, D. R., C. D. Perttunen and B. E. Stuckman (1994),Lipschitzian Optimization without the Lipschitz Constant, J. of Optim. Theory and Appl.,79, 157–181.

    Google Scholar 

  11. Kearfott, R. B. and Novoa, M. (1990),INTBIS, a Portable Interval Newton/Bisection Package, ACM T. on Mathematical Software,16, 152–157.

    Google Scholar 

  12. Klatte, R., Kulisch, U., Neaga, M., Ratz, D., and Ullrich, Ch. (1992),PASCAL-XSC-Language Reference with Examples, Springer-Verlag, New York.

    Google Scholar 

  13. Kristinsdottir, B. P., Zabinsky, Z. B., Csendes, T., and Tuttle, M. E. (1993),Methodologies for Tolerance Intervals, Interval Computations,3, 133–147.

    Google Scholar 

  14. Levy, A. V., Montalvo, A., Gomez, S., and Calderon, A. (1981),Topics in Global Optimization, Lecture Notes in Mathematics, No. 909, Springer-Verlag, Berlin.

    Google Scholar 

  15. Moore, R. E. (1966),Interval Analysis, Prentice Hall, Engelwood Cliffs.

    Google Scholar 

  16. Neumaier, A. (1990),Interval Methods for Systems of Equations, Cambridge University Press, Cambridge.

    Google Scholar 

  17. Pintér, J. (1986),Extended Univariate Algorithms for n-dimensional Global Optimization, Computing36, 91–103.

    Google Scholar 

  18. Pintér, J. (1992),Convergence Qualification of Adaptive Partition Algorithms in Global Optimization, Mathematical Programming56, 343–360.

    Google Scholar 

  19. Ratschek, H. and Rokne, J. (1988),New Computer Methods for Global Optimization, Ellis Horwood, Chichester.

    Google Scholar 

  20. Ratschek, H. and Rokne, J. (1993),Experiments Using Interval Analysis for Solving a Circuit Design Problem, J. Global Optimization3, 501–518.

    Google Scholar 

  21. Ratz, D. (1992),Automatische Ergebnisverifikation bei globalen Optimierungsproblemen, Dissertation, Universitüt Karlsruhe.

  22. Schwefel, H. (1991),Numerical Optimization of Computer Models, Wiley, New York.

    Google Scholar 

  23. Skelboe, S. (1974),Computation of Rational Interval Functions, BIT4, 87–95.

    Google Scholar 

  24. Törn, A. and Žilinskas, A. (1989),Global Optimization, Lecture Notes in Computer Science, No. 350, Springer-Verlag, Berlin.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Angewandte Mathematik, Universitüt Karlsruhe, D-76128, Karlsruhe, Germany

    Dietmar Ratz

  2. Department of Applied Informatics, József Attila University, Árpád tér 2, H-6720, Szeged, Hungary

    Tibor Csendes

Authors
  1. Dietmar Ratz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tibor Csendes
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The work has been supported by the Grants OTKA 2879/1991, and MKM 414/1994.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ratz, D., Csendes, T. On the selection of subdivision directions in interval branch-and-bound methods for global optimization. J Glob Optim 7, 183–207 (1995). https://doi.org/10.1007/BF01097060

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01097060

Key words

Search

Navigation