×

zbMATH — the first resource for mathematics

On the selection of subdivision directions in interval branch-and-bound methods for global optimization. (English) Zbl 0841.90116
Summary: 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.

MSC:
90C30 Nonlinear programming
65G30 Interval and finite arithmetic
Software:
INTBIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alefeld G. and Herzberger J. (1983),Introduction to Interval Computations, Academic Press, New York. · Zbl 0552.65041
[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. · Zbl 0453.65046
[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. · Zbl 0829.65081
[4] Csendes, T. (1988),Nonlinear Parameter Estimation by Global Optimization ?Efficiency and Reliability, Acta Cybemetica,8, 361-370. · Zbl 0654.90074
[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. · Zbl 0768.90068
[6] Csendes, T. and Ratz, D. (1995),Subdivision Direction Selection in Interval Methods for Global Optimization, submitted for publication. · Zbl 0841.90116
[7] Hammer, R., Hocks, M., Kulisch, U., and Ratz, D. (1993),Numerical Toolbox for Verified Computing I, Springer-Verlag, Berlin. · Zbl 0796.65001
[8] Hansen, E. (1992),Global Optimization Using Interval Analysis, Marcel Dekker, New York. · Zbl 0762.90069
[9] Jansson, C. and Knüppel, O. (1992),A Global Minimization Method: the Multi-Dimensional Case, Report 92.1, Technische Universitüt Hamburg-Harburg. · Zbl 0802.65078
[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. · Zbl 0796.49032
[11] Kearfott, R. B. and Novoa, M. (1990),INTBIS, a Portable Interval Newton/Bisection Package, ACM T. on Mathematical Software,16, 152-157. · Zbl 0900.65152
[12] Klatte, R., Kulisch, U., Neaga, M., Ratz, D., and Ullrich, Ch. (1992),PASCAL-XSC-Language Reference with Examples, Springer-Verlag, New York. · Zbl 0875.68228
[13] Kristinsdottir, B. P., Zabinsky, Z. B., Csendes, T., and Tuttle, M. E. (1993),Methodologies for Tolerance Intervals, Interval Computations,3, 133-147. · Zbl 0829.65083
[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. · Zbl 0473.65037
[15] Moore, R. E. (1966),Interval Analysis, Prentice Hall, Engelwood Cliffs. · Zbl 0176.13301
[16] Neumaier, A. (1990),Interval Methods for Systems of Equations, Cambridge University Press, Cambridge. · Zbl 0715.65030
[17] Pintér, J. (1986),Extended Univariate Algorithms for n-dimensional Global Optimization, Computing36, 91-103. · Zbl 0572.65047
[18] Pintér, J. (1992),Convergence Qualification of Adaptive Partition Algorithms in Global Optimization, Mathematical Programming56, 343-360. · Zbl 0762.90071
[19] Ratschek, H. and Rokne, J. (1988),New Computer Methods for Global Optimization, Ellis Horwood, Chichester. · Zbl 0648.65049
[20] Ratschek, H. and Rokne, J. (1993),Experiments Using Interval Analysis for Solving a Circuit Design Problem, J. Global Optimization3, 501-518. · Zbl 0793.90077
[21] Ratz, D. (1992),Automatische Ergebnisverifikation bei globalen Optimierungsproblemen, Dissertation, Universitüt Karlsruhe. · Zbl 0831.65068
[22] Schwefel, H. (1991),Numerical Optimization of Computer Models, Wiley, New York.
[23] Skelboe, S. (1974),Computation of Rational Interval Functions, BIT4, 87-95. · Zbl 0274.65015
[24] Törn, A. and ?ilinskas, A. (1989),Global Optimization, Lecture Notes in Computer Science, No. 350, Springer-Verlag, Berlin.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.