Interval methods for global optimization using the boxing method. (English) Zbl 1391.65126
Krämer, Walter (ed.) et al., Scientific computing, validated numerics, interval methods, Karlsruhe, Germany, September 19–22, 2000. New York, NY: Springer (ISBN 978-0-306-46706-6/hbk; 978-1-4757-6484-0/ebook). 205-213 (2001).
Summary: The global optimization problem with simple bounds which is the scope of this work can be defined in general as \(\min_{x\in X}f(x)\) where \(X\) is a – possibly multidimensional – interval. The original problem can be solved with verified accuracy with the aid of interval subdivision methods. These algorithms are based on the well-known branch-and-bound principle. The methods pruning the search tree of these algorithms are the so-called accelerating devices. One of the most effective of these is the interval Newton step, however, its time complexity is relatively high as compared with other accelerating devices. Therefor it should only be deployed if there are no other possibilities to effectively bound the search tree. Methods like the boxing method can decrease the number of the applied Newton steps. The present paper discusses some of these methods and shows the numerical effects of their implementation.
For the entire collection see [Zbl 1392.65008].
For the entire collection see [Zbl 1392.65008].
Keywords:
boxing method; interval Newton method; accelerating device; interval subdivision method; global optimizationReferences:
| [1] | [1]G. Alefeld and J. Herzberger. \(Introduction to Interval Computations\), Academic Press, New York, 1983. · Zbl 0552.65041 |
| [2] | [2]S. Berner, \(Ein paralleles Verfahren zur verifizierten globalen Optimierung\), PhD Thesis, Shaker, Aachen, 1995. · Zbl 1058.90519 |
| [3] | [3]T. Csendes, D. Ratz, \(Subdivision Direction Selection in Interval Methods for Global Optimization\), SIAM Journal on Numerical Analysis, 34 (1997), pp. 922-938. · Zbl 0873.65063 · doi:10.1137/S0036142995281528 |
| [4] | [4]R. Hammer, M. Hocks, U. Kulisch, and D. Ratz, \(Numerical Toolbox for Verified Computing I\)., Springer, Berlin, 1993. · Zbl 0796.65001 |
| [5] | [5]R. Hammer, M. Hocks, U. Kulisch, and D. Ratz, \(C++ Toolbox for Verified Computing I\)., Springer, Berlin, 1995. · Zbl 0828.68041 |
| [6] | [6]E. Hansen, \(Global Optimization Using Interval Analysis\), Marcel Dekker, New York, 1992. · Zbl 0762.90069 |
| [7] | [7]R. B. Kearfott, \(Rigorous Global Search: Continuous Problems\), Kluwer, Dordrecht, 1996. · Zbl 0876.90082 · doi:10.1007/978-1-4757-2495-0 |
| [8] | [8]R. Klatte, U. Kulisch, M. Neaga, D. Ratz, and Ch. Ullrich, \(PASCAL-XSC — Language Reference with Examples\), Springer, New York, 1992. · Zbl 0875.68228 |
| [9] | [9]R. Klatte, U. Kulisch, C. Lawo, M. Rauch, and A. Wiethoff, \(C-XSC\), A \(C++ Class Library for Extended Scientific Computing\), Springer, New York, 1993. · Zbl 0814.68035 |
| [10] | [10]J. J. Mort, B. S. Garbow, and K. E. Hillstrom, \(Testing Unconstrained Optimization Software\),ACM Transactions on Mathematical Software, 7 (1981), No.1. |
| [11] | [11]A. Neumaier, \(Interval Methods for Systems of Equations\), Cambridge University Press, Cambridge, 1990. · Zbl 0715.65030 |
| [12] | [12]H. Ratschek and J. Rokne, \(New Computer Methods for Global Optimization\), Ellis Horwood, Chichester, 1988. · Zbl 0648.65049 |
| [13] | [13]D. Ratz and T. Csendes, \(On the selection of subdivision directions in interval branch-andbound methods for global optimization\), J. Global Optimization, 7 (1995), pp. 183-207. · Zbl 0841.90116 · doi:10.1007/BF01097060 |
| [14] | [14]A. Törn, A. 2ilinskas, \(Global Optimization\), Lecture Notes in Computer Science 350, Springer, Berlin, 1989. · Zbl 0752.90075 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
