×

Global optimization to prescribed accuracy. (English) Zbl 0725.65062

The author presents his view on the role of interval arithmetic and on the use of multiple precision in the field of global optimization. After an introductory section on order relations and on interval arithmetic, round-off errors are discussed in connection with fixed-precision floating-point arithmetic. Results obtained in this arithmetic are compared with those using interval tools combined with an outward rounding. The role of computing the ranges of functions and of computing with sets is emphasized.
A central section addresses the problem of formulating an appropriate stopping criterion. It is illustrated by examples using the interval Newton method. Remarks on user-controlled arbitrary precision interval arithmetic are added where this precision can be varied during the computation, if necessary. The paper ends with some essentials of interval methods for global optimization and with some directions for future research.

MSC:

65K05 Numerical mathematical programming methods
65G30 Interval and finite arithmetic
65H10 Numerical computation of solutions to systems of equations
90C30 Nonlinear programming

Software:

Pascal-SC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Garloff et al., Interval Mathematics — A Bibliography; J. Garloff et al., Interval Mathematics — A Bibliography
[2] Aberth, O., Precise Numerical Analysis (1988), William C. Brown, (with variable-precision software on IBM-PC disks) · Zbl 0665.65001
[3] (Alefeld, G.; Grigorieff, R. D., Fundamentals of Numerical Computation (Computer-oriented Numerical Analysis), Computing Supplementum (1980), Springer) · Zbl 0423.00017
[4] Alefeld, G.; Herzberger, J., Introduction to Interval Computations (1983), Academic Press
[5] Bohlender, G.; Ullrich, C.; von Gudenberg, J. Wolff; Rall, L. B., Pascal-SC. A Computer Language for Scientific Computation (1987), Academic Press · Zbl 0626.68004
[6] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall · Zbl 0579.65058
[7] (Hansen, E. R., BIT, 21 (1981)), 203-211
[8] Kaucher, E. W.; Miranker, W. L., Self-validating Numerics for Function Space Problems (1984), Academic Press · Zbl 0548.65028
[9] Kulisch, U. W.; Miranker, W. L., Computer Arithmetic in Theory and Practice (1981), Academic Press · Zbl 0597.65037
[10] Kulisch, U. W.; Miranker, W. L., A New Approach to Scientific Computation (1983), Academic Press · Zbl 0597.65037
[11] (Kulisch, U. W.; Stetter, H. J., Scientific Computation with Automatic Result Verification (1988), Springer) · Zbl 0646.00013
[12] Moore, R. E., Interval Arithmetic and Automatic Error Analysis in Digital Computing, Applied Math. and Stat. Lab Report No. 25 (1962)
[13] Moore, R. E., Interval Analysis (1966), Prentice-Hall · Zbl 0176.13301
[14] Moore, R. E., Mathematical Elements of Scientific Computing (1975), Holt, Rinehart and Winston · Zbl 0376.65001
[15] Moore, R. E., Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics (1979) · Zbl 0417.65022
[16] Moore, R. E., Computational Functional Analysis (1985), Ellis Horwood and John Wiley · Zbl 0574.46001
[17] (Moore, R. E., Reliability in Computing. The Role of Interval Methods in Scientific Computing (1988), Academic Press) · Zbl 0638.00033
[18] (Nickel, K., Interval Mathematics, Lecture Notes in Computer Science, No. 29 (1975), Springer)
[19] (Nickel, K., Interval Mathematics 1980 (1980), Academic Press) · Zbl 0527.00029
[20] (Nickel, K., Interval Mathematics 1985, Lect. Notes in C.S. (1985), Springer), No. 212
[21] Rall, L. B., (Automatic Differentiation, Lecture Notes in Computer Science, No. 120 (1981), Springer) · Zbl 0473.68025
[22] (Rall, L. B., Error in Digital Computation, Vols. I and II (1965), Wiley) · Zbl 0148.00203
[23] Ratschek, H.; Rokne, J., Computer Methods for the Range of Functions (1984), Ellis Horwood and John Wiley · Zbl 0584.65019
[24] Ratschek, H.; Rokne, J., New Computer Methods for Global Optimization (1988), Ellis Horwood and John Wiley · Zbl 0648.65049
[25] E.A. Galperin, The Cubic Algorithm for Optimization and Control; E.A. Galperin, The Cubic Algorithm for Optimization and Control · Zbl 0781.90080
[26] E.R. Hansen, Interval Methods for Global Optimization; E.R. Hansen, Interval Methods for Global Optimization
[27] Y.F. Chang, The Automatic Taylor Series Method of Analysis; Y.F. Chang, The Automatic Taylor Series Method of Analysis
[28] Galperin, E. A., The cubic algorithm, J. Math. Anal. and Appl., 112, 635-640 (1985) · Zbl 0588.65042
[29] Galperin, E. A., Two alternatives for the cubic algorithm, J. Math. Anal. and Appl., 126, 229-237 (1987) · Zbl 0631.90056
[30] F. Krückeberg, Arbitrary accuracy with variable precision arithmetic, in [20].; F. Krückeberg, Arbitrary accuracy with variable precision arithmetic, in [20].
[31] Moore, R. E.; Ratschek, H., Inclusion functions and global optimization II, Math. Prog, 41, 341-356 (1988) · Zbl 0644.90074
[32] Moore, R. E., Set-valued extensions of integral inequalities, Journal of Integral Equations, 5, 187-198 (1988) · Zbl 0516.45022
[33] Walster, G. W.; Hansen, E. R.; Sengupta, S., Test results for a global optimization algorithm, (Boggs-Byrd-Schnabel, Numerical Optimization (1985), SIAM: SIAM Philadelphia), 272-287 · Zbl 0574.65062
[34] Ely, J., Prospects for using variable precision interval software in C++ for solving some contemporary scientific problems, (Ph. D. Dissertation (1990), Ohio State University)
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.