Skip to main content
SpringerLink
Log in

Multisection in Interval Branch-and-Bound Methods for Global Optimization – I. Theoretical Results

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

Abstract

We have investigated variants of interval branch-and-bound algorithms for global optimization where the bisection step was substituted by the subdivision of the current, actual interval into many subintervals in a single iteration step. The convergence properties of the multisplitting methods, an important class of multisection procedures are investigated in detail. We also studied theoretically the convergence improvements caused by multisection on algorithms which involve the accelerating tests (like e.g. the monotonicity test). The results are published in two papers, the second one contains the numerical test result.

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. Berner, S. (1995), Ein paralleles Verfahren zur verifizierten globalen Optimierung. Dissertation, Universität Wuppertal.

  3. Berner, S. (1966), New results on verified global optimization, Computing 57: 323–343.

    Google Scholar 

  4. Casado, L.G., García, I. and Csendes, T., Adaptive Multisection in Interval Methods for Global Optimization, submitted for publication (available at http: / /www.inf.u-szeged.hu/~csendes/publ.html).

  5. Casado, L.G., García, I. and Csendes, T., A Heuristic Rejection Criterion in Interval Global Optimization Algorithms, submitted for publication (available at http: / /www.inf.u-szeged.hu/~csendes/publ.html).

  6. Csallner, A.E. (1993), Global optimization in separation network synthesis, Hungarian J. Industrial Chemistry 21: 303–308.

    Google Scholar 

  7. Csallner, A.E. and Csendes, T. (1996), On the convergence speed of interval methods for global optimization, Computers, Mathematics and Applications 31: 173–178.

    Google Scholar 

  8. Csendes, T. and Pintér, J. (1993), The impact of accelerating tools on the interval subdivision algorithm for global otimization, European J. of Operational Research 65: 314–320.

    Google Scholar 

  9. Csendes, T. and Ratz, D. (1997), Subdivision direction selection in interval methods for global optimization, SIAM J. Numerical Analysis 34: 922–938.

    Google Scholar 

  10. Hansen, E. (1992), Global optimization using interval analysis. Marcel Dekker, New York.

    Google Scholar 

  11. Hansen, P., Jaumard, B. and Xiong, J. (1994), Cord-Slope Form of Taylor's Expansion in Univariate Global Optimization, J. Optimization Theory and Applications 80: 441–464.

    Google Scholar 

  12. Ichida, K. and Fujii, Y. (1979), An interval arithmetic method for global otimization. Computing 23: 85–97.

    Google Scholar 

  13. Kearfott, R.B. (1996), Test results for an interval branch and bound algorithm for equalityconstrained optimization. In: Floudas, C.A. and Pardalos, P.M. (eds.), State of the Art in Global Optimization. Kluwer, Dordrecht, 181–199.

    Google Scholar 

  14. Kearfott, R.B. (1996), Rigorous global search: continuous problems. Kluwer, Dordrecht.

    Google Scholar 

  15. Krawczyk, R. and Neumaier, A. (1985), Interval Slopes for Rational Functions and Associated Centered Forms, SIAM J. Numerical Analysis 22: 604–616.

    Google Scholar 

  16. Markót, M.Cs., Csendes, T. and Csallner, A.E., Multisection in Interval Branch-and-Bound Methods for Global Optimization II. Numerical Tests. Submitted for publication (available at http://www.inf.u-szeged.hu/~csendes/publ.html).

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

    Google Scholar 

  18. Ratschek, H. and Rokne, J. (1993), Interval Methods, In: Horst R. and Pardalos P.M. (eds.), Handbook of Global Optimiation, Kluwer, Dordrecht, 751–828.

    Google Scholar 

  19. Ratz, D. (1992), Automatische Ergebnisverifikation bei globalen Optimierungsproblemen. Dissertation, Univesität Karlsruhe.

  20. Ratz, D. and Csendes, T. (1995), On the selection of subdivision directions in interval branch-and-bound methods for global optimization, J. Global Optimization 7, 183–207.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Juhász Gyula Teachers Training College, Boldogasszony sgt. 4, Szeged, Hungary

    András Erik Csallner

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

    Tibor Csendes

  3. Institute of Informatics, József Attila University, Árpád tér 2, Szeged, Hungary

    Mihály Csaba markót

Authors
  1. András Erik Csallner
    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

  3. Mihály Csaba markót
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Csallner, A.E., Csendes, T. & Csaba markót, M. Multisection in Interval Branch-and-Bound Methods for Global Optimization – I. Theoretical Results. Journal of Global Optimization 16, 371–392 (2000). https://doi.org/10.1023/A:1008354711345

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008354711345

Search

Navigation