×

zbMATH — the first resource for mathematics

What can interval analysis do for global optimization? (English) Zbl 0752.65054
This is a survey article on the application of interval analysis to optimization. After some introductory remarks in Section 1, a prototype algorithm is presented for finding an enclosure of all the global minimizers of a given function defined on a box. The algorithm is based on subdivisions of boxes and on an ordered list.
Since interval arithmetic is used later on to enclose ranges of functions, Section 3 gives a short course in this field. Included are some remarks on machine interval arithmetic. Inclusion functions and natural interval extensions are introduced in Section 4.
Section 5 is devoted to box-discarding tests such as the midpoint test, the monotonicity test, a non-convexity test and the application of interval Newton-like methods. As a particular Newton-like operator, the Krawczyk operator is discussed in greater detail in a separate section.
Convergence properties of the prototype algorithm are considered in Section 7, and termination criteria for this algorithm are listed subsequently. Optimization over unbounded domains, nonsmooth optimization and constrained optimization form the contents of the three final sections. A list with numerous references concludes the paper.

MSC:
65K05 Numerical mathematical programming methods
65G30 Interval and finite arithmetic
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
90C30 Nonlinear programming
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] Asaithambi, N. S., Shen, Z., and Moore, R. E. (1982), On Computing the Range of Values, Computing 28, 225-237. · Zbl 0473.65004 · doi:10.1007/BF02241750
[3] Bauch, H., Jahn, K. U., Oelschlägel, D., Süsse, H., and Wiebigke, V. (1987), Intervall-mathematik, Teubner, Leipzig.
[4] Caprani, O. and Madsen, K. (1979), Interval Methods for Global Optimization, Report NI 79-09, Technical University of Denmark. · Zbl 0401.65035
[5] Clarke, F. H. (1983), Optimization and Nonsmooth Analysis, Wiley, New York. · Zbl 0582.49001
[6] Dixon, L. C. W. and Fitzharris, A. M. (1985), Conjugate Gradients: An Interval Analysis, Technical Report Nr. 165. Numerical Optimization Center, Hatfield, Polytechnic, Hatfield.
[7] Dussel, R. (1972), Einschließung des Minimalpunktes einer streng konvexen Funktion auf einem N-Dimensionalen Quader, Dissertation, Universität Karlsruhe. · Zbl 0301.65035
[8] Fang, Yuo-Kang (1982), Interval Test on Unconstrained Global Optimization (in Chinese). Comm. Interval Anal., Math. Fac. of Liaoning Univ. 2, 43-59.
[9] Hansen, E. (1979), Global Optimization Using Interval Analysis?The One-Dimensional Case, J. Optim. Theory Appl. 29, 331-344. · Zbl 0388.65023 · doi:10.1007/BF00933139
[10] Hansen, E. (1980), Global Optimization Using Interval Analysis?The Multi-Dimensional Case, Numer. Math. 34, 247-270. · Zbl 0442.65052 · doi:10.1007/BF01396702
[11] Hansen, E.: Interval Tools for Global Optimization, forthcoming.
[12] Hansen, E. and Sengupta, S. (1983), Summary and Steps of a Global Nonlinear Constrained Optimization Algorithm. Lockheed Missiles & Space Co. Report No. D 889778, Sunnyvale, California.
[13] Hansen, E. and Walster, G. W. (1987), Nonlinear Equations and Optimization, Preprint. · Zbl 0770.65037
[14] Hansen, P., Jaumard, B., and Lu, S.-H. (1991) An Analytical Approach to Global Optimization. Math. Programming, Series B, forthcoming. · Zbl 0747.90091
[15] Horst, R. and Tuy, H. (1990), Global Optimization, Springer-Verlag, Berlin. · Zbl 0704.90057
[16] Ichida, K. and Fujii, Y. (1979), An Interval Arithmetic Method for Global Optimization Computing 23, 85-97. · Zbl 0415.65036 · doi:10.1007/BF02252616
[17] Kahan, W. M. (1968), A More Complete Interval Arithmetic. Lectures Notes at the University of Michigan, Michigan.
[18] Kearfott, R. B. (1987), Abstract Generalized Bisection and a Cost Bound, Mathem. of Computation 49, 187-202. · Zbl 0632.65055 · doi:10.1090/S0025-5718-1987-0890261-9
[19] Krawczyk, R. (1969), Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4, 187-201. · Zbl 0187.10001 · doi:10.1007/BF02234767
[20] Krawczyk, R. and Nickel, K. (1982), Die zentrische Form in der Intervallarithmetik, ihre quadratische Konvergenz und ihre Inklusions Isotonie, Computing 28, 117-137. · Zbl 0466.65026 · doi:10.1007/BF02241818
[21] Kulisch, U. and Miranker, W. L. (1986), The Arithmetic of the Digital Computer: A New Approach, SIAM Review, March 1986, 1-40. · Zbl 0597.65037
[22] Mancini, L. J. (1975), Applications of Interval Arithmetic in Signomial Programming, Ph.D. Thesis. Stanford University.
[23] Mancini, L. J. and McCormick, G. P. (1979), Bounding Global Minima with Interval Arithmetic, Oper. Res. 27, 743-754. · Zbl 0417.90078 · doi:10.1287/opre.27.4.743
[24] Mancini, L. J. and Wilde, D. J. (1978), Interval Arithmetic in Unidimensional Signomial Programming, J. Optim. Theory Appl. 26, 227-289. · Zbl 0369.90116 · doi:10.1007/BF00933408
[25] Mancini, L. J. and Wilde, D. J. (1979), Signomial Dual Kuhn-Tucker Intervals, J. Optim. Theory Appl. 28, 11-27. · Zbl 0422.90071 · doi:10.1007/BF00933598
[26] McCormick, G. P. (1981), Finding the Global Minimum of a Function of one Variable Using the Method of Constant Signed Higher Order Derivatives, in: Nonlinear Program. 4, ed. by O. L.Mangasarian, R. R.Meyer, and S. M.Robinson, Academic Press, New York, 223-243 (1981).
[27] Mohd, I. B. (1986), Global Optimization Using Interval Arithmetic Ph. D. Thesis, Univ. of St. Andrews, St. Andrews, Scotland.
[28] Moore, R. E. (1966), Interval Analysis, Prentice-Hall, Englewood Cliffs. · Zbl 0176.13301
[29] Moore, R. E. (1976), On Computing the Range of a Rational Function of n Variables over a Bounded Region, Computing 16, 1-15. · Zbl 0345.65024 · doi:10.1007/BF02241975
[30] Moore, R. E. (1977), A Test for Existence of Solutions to Nonlinear Systems, SIAM J. Numer. Analy. 14, 611-615. · Zbl 0365.65034 · doi:10.1137/0714040
[31] Moore, R. E. (1979) Methods and Applications of Interval Analysis, SIAM, Philadelphia. · Zbl 0417.65022
[32] Moore, R. E. and Ratschek, H. (1988), Inclusion Functions and Global Optimization II, Math. Programming 41, 341-356. · Zbl 0644.90074 · doi:10.1007/BF01580772
[33] Neumaier, A. (1991), Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, forthcoming. · Zbl 0715.65030
[34] Oelschlaegel, D. and Süsse, H. (1978), Fehlerabschätzung beim Verfahren von Wolfe zur Lösung quadratischer Optimierungsprobleme mit Hilfe der Intervallarithmetik, Math. Operationsforsch. Statist., Ser. Optimization 9, 389-396. · Zbl 0389.65033
[35] Ratschek, H. (1985), Inclusion Functions and Global Optimization, Mathematical Programming 33, 300-317. · Zbl 0579.90082 · doi:10.1007/BF01584379
[36] Ratschek, H. and Rokne, J. (1984), Computer Methods for the Range of Functions, Horwood, Chichester. · Zbl 0584.65019
[37] Ratschek, H. and Rokne, J. (1987), Efficiency of a Global Optimization Algorithm, SIAM J. Numer. Analysis 24, 1191-1201. · Zbl 0636.65060 · doi:10.1137/0724078
[38] Ratschek, H. and Rokne, J. (1988), New Computer Methods for Global Optimization, Horwood, Chichester. · Zbl 0648.65049
[39] Ratschek, H. and Voller, R. L. (1990), Global Optimization over Unbounded Domains, SIAM J. Control Optimization 28, 528-539. · Zbl 0725.90086 · doi:10.1137/0328031
[40] Robinson, S. M. (1973), Computable Error Bounds for Nonlinear Programming, Math. Programming 5, 235-242. · Zbl 0274.90052 · doi:10.1007/BF01580124
[41] Sengupta, S. (1981), Global Nonlinear Constrained Optimization, Dissertation, Department of Pure and Applied Mathematics, Washington State University.
[42] Skelboe, S. (1974), Computation of Rational Interval Functions, BIT 4, 87-95. · Zbl 0274.65015 · doi:10.1007/BF01933121
[43] Stroem, T. (1971), Strict Estimation of the Maximum of a Function of one Variable, BIT 11, 199-211. · Zbl 0225.65071 · doi:10.1007/BF01934369
[44] Süsse, H. (1977), Intervallarithmetische Behandlung von Optimierungsproblemen und damit verbundener numerischer Aufgabenstellungen, Dissertation, Technische Hochschule Leuna-Merseburg.
[45] Süsse, H. (1980), Intervallanalytische Behandlung nichtlinearer Optimierungsaufgaben, Dissertation zur Promotion B. Technische Hochschule ?Carl Schorlemer?, Leuna-Merseburg.
[46] Walster, G. W., Hansen, E. R., and Sengupta, S. (1985), Test Results for a Global Optimization Algorithm, in: Numerical Optimization 1984, ed. by Boggs, P. T., Byrd, R. H., and Schnabel, R. B., Siam, pp. 272-282.
[47] Dussel, R. and Schmitt, B. (1970) Die Berechnung von Schranken für den Wertebereich eines Polynoms in einem Intervall, Computing 6, 35-60. · Zbl 0212.17102 · doi:10.1007/BF02241731
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.