Abstract
Most interval branch and bound methods for nonlinear algebraic systems have to date been based on implicit underlying assumptions of continuity of derivatives. In particular, much of the theory of interval Newton methods is based on this assumption. However, derivative continuity is not necessary to obtain effective bounds on the range of such functions. Furthermore, if the first derivatives just have jump discontinuities, then interval extensions can be obtained that are appropriate for interval Newton methods. Thus, problems such as minimax orl 1-approximations can be solved simply, formulated as unconstrained nonlinear optimization problems. In this paper, interval extensions and computation rules are given for the unary operation |x|, the binary operation max{x, y} and a more general “jump” function χ(s,x,y). These functions are incorporated into an automatic differentiation and code list interpretation environment. Experimental results are given for nonlinear systems involving max and |o| and for minimax andl 1-optimization problems.
Zusammenfassung
Die meisten gebräuchlichen Intervallmethoden für nicht-lineare algebraische Systeme beruhen auf Annahmen über die Stetigkeit der Ableitungen, ebenso große Teile der Theorie der Intervall-Newton-Verfahren. Für effiziente Einschließungen des Wertebereichs ist jedoch die Stetigkeit der Ableitungen nicht notwendig, im Fall von Sprüngen der ersten Ableitungen können sogar für Intervall-Newton-Verfahren geeignete Einschließungen gewonnen werden. Formuliert als unrestringierte nichtlineare Optimierungsprobleme können demnach minimax- oderl 1-Approximationen leicht behandelt werden. In der vorliegenden Arbeit geben wir Intervall-Auswertungen und Rechenregeln für die Funktionen |x|, max{x, y} und eine allgemeine Sprungfunktion χ(s, x, y) an. Diese Funktionen sind in eine Umgebung zur automatischen Differentiation und Codelisten-Interpretation eingearbeitet. Ergebnisse werden vorgestellt für nichtlineare Systeme mit max und |o| und für minimax- undl 1-Optimierungsaufgaben.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alefeld, G., Herzberger, J.: Introduction to interval computations. New York: Academic Press 1983.
Bleher, J. H., Rump, S. M., Kulisch, U., Metzger, M., Ullrich, C., Walter, W.: FORTRAN-SC—A study of a Fortran extension for engineering scientific computation with access to ACRITH. Computing39, 93–110 (1987).
Csendes, T.: Test results of interval methods for global optimization. In: Computer arithmetic, scientific computing and mathematical modelling (Kaucher, E., Markov, S. M., Mayer, G., eds.), pp. 417–424. Basel: J. C. Baltzer AG 1992.
Hammer, R., Hocks, M., Kulisch, U., Ratz, D. Numerical toolbox for verified computing I. New York: Springer 1993.
Hammer, R., Neaga, M., Ratz, D.: PASCAL-XSC, New concepts for scientific computation and numerical data processing. In: Scientific computing with automatic result verification (Adams, E., Kulisch, V., eds.), pp. 15–44. New York: Academic Press 1993.
Hansen, E. R. Global optimization using interval analysis. New York: M. Dekker 1992.
Herzberger, J., ed.: Topics in validated computations. Studies in Computational Mathematics. Amsterdam: Elsevier 1994.
Jansson, C.: A global optimization method using interval arithmetic. In: Computer arithmetic and enclosure methods (Atanassova, L., Herzberger, J., eds.), pp. 259–268. Amsterdam: North-Holland 1992.
Jansson, C.: On self-validating methods for optimization problems. In: Topics in validated computations (Herzberger, J., ed.), pp. 381–439. Amsterdam: North-Holland 1994.
Jansson, C., Knüppel, O.: A global minimization method: The multi-dimensional case. Technical Report 92.1, Informationstechnik, Technische Uni. Hamburg-Harburg 1992.
Jansson, C., Knüppel, O.: Numerical results for a self-validating global optimization method. Technical Report 94.1, Technical University Hamburg-Harburg, February 1994.
Kearfott, R. B.: Empirical evaluation of innovations in interval branch and bound algorithms for nonlinear algebraic systems, 1994. SIAM J. Sci. Comput, to appear.
Kearfott, R. B.: A Fortran 90 environment for research and prototyping of enclosure algorithms for nonlinear equations and global optimization. ACM Trans. Math. Software21, 63–78 (1995).
Kearfott, R. B.: Test results for an interval branch and bound algorithm for equality-constrained optimization. In: State of the art in global optimization: computational methods and applications (Floudas, C., Pardalos, P. M., eds.), pp. 181–200. Dordecht: Kluwer 1995.
Kearfott, R. B.: Treating non-smooth functions as smooth functions in global optimization and nonlinear systems solvers. In: Scientific computing and validated numerics (Alefeld, G., Frommer, A., eds.). Berlin: Akademie Verlag, to appear.
Kearfott, R. B.: Rigorous branch and bound methods. Dordrecht: Kluwer, to appear
Kearfott, R. B., Dawande, M., Du, K.-S., Hu, C.-Y.: Algorithm 737: INTLIB, a portable FORTRAN 77 interval standard function library. ACM Trans. Math. Software20, 447–459 (1994).
Lawo, C.: C-XSC—a programming environment for verified scientific computing and numerical data processing. In: Scientific computing with automatic result verification (Adams, E., Kulisch, V., eds.), pp. 71–86. New York: Academic Press 1993.
Moore, R. E.: Methods and applications of interval analysis. Philadelphia: SIAM 1979.
Neumaier, A.: Interval methods for systems of equations. Cambridge: Cambridge University Press 1990.
Ratschek, H., Rokne, J.: New computer methods for global optimization. New York: Wiley 1988.
Ratz, D. Automatische Ergebnisverifikation bei globalen Optimierungsproblemen. PhD thesis, Universität Karlsruhe 1992.
Ratz, D.: An inclusion algorithm for global optimization in a portable PASCAL-XSC implementation. In: Computer arithmetic and enclosure methods (Atanassova, L., Herzberger, J., eds.), pp. 329–338. Amsterdam: North-Holland 1992.
Rump, S. M. Verification methods for dense and sparse systems of equations. In: Topics in validated computations (Herzberger, J., ed.), pp. 63–135. Amsterdam: Elsevier 1994.
Author information
Authors and Affiliations
Additional information
This work was supported in part by National Science Foundation grant CCR-9203730.
Rights and permissions
About this article
Cite this article
Kearfott, R.B. Interval extensions of non-smooth functions for global optimization and nonlinear systems solvers. Computing 57, 149–162 (1996). https://doi.org/10.1007/BF02276877
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02276877