A Fortran 90 environment for research and prototyping of enclosure algorithms for nonlinear equations and global optimization

ABSTRACT

An environment for general research into and prototyping of algorithms for reliable constrained and unconstrained global nonlinear optimization and reliable enclosure of all roots of nonlinear systems of equations, with or without inequality constraints, is being developed. This environment should be portable, easy to learn, use, and maintain, and sufficiently fast for some production work. The motivation, design principles, uses, and capabilities for this environment are outlined. The environment includes an interval data type, a symbolic form of automatic differentiation to obtain an internal representation for functions, a special technique to allow conditional branches with operator overloading and interval computations, and generic routines to give interval and noninterval function and derivative information. Some of these generic routines use a special version of the backward mode of automatic differentiation. The package also includes dynamic data structures for exhaustive search algorithms.

REFERENCES

• 1: ALEFELD, G. AND HERZBERGER, J. 1983. Introduction to Interval Computations. Academic Press, New York.
• 2: J. H. Bleher , S. M. Rump , U. Kulisch , M. Metzger, Fortran-sc. a study of a fortran extension for engineering/scientific computation with access to acrith, Computing, v.39 n.2, p.93-110, April 1, 1987 [doi>10.1007/BF02310100]
• 3: Walter S. Brainerd , Charles Goldberg , Jeanne Adams, Programmer's guide to Fortran 90, Intertext Publications, Inc.,/McGraw-Hill, Inc., New York, NY, 1990
• 4: CHRISTIANSON, B. 1992. Reverse accumulation and accurate rounding error estimates for Taylor series coefficients. Optim. Meth. Softw. 1, 1, 81-94.
• 5: CRAR~, F. 1976. The AUGMENT precompiler. Tech. Rep. 1470, Mathematics Research Center, Univ. of Wisconsin, Madison.
• 6: DIXON, L. C. W., MAANY, Z., AND MOHSENINIA, M. 1990. Automatic differentiation of large sparse systems. J. Econ. Dyn. Control 14,299-311.
• 7: Christodoulos A. Floudas , Panos M. Pardalos, Recent advances in global optimization, Princeton University Press, Princeton, NJ, 1992
• 8: Christodoulos A. Floudas , Panos M. Pardalos, A collection of test problems for constrained global optimization algorithms, Springer-Verlag New York, Inc., New York, NY, 1990
• 9: GmEWANK, A. 1991a. The chain rule revisited in scientific computing. SIAM News 24, 3, 20-21.
• 10: GRIEWANK, h. 1991b. The chain rule revisited in scientific computing. SIAM News 24, 4, 8-24. GmEWANK, A. AND CORLISS, G. F., (EDs.) 1991. Automatic Differentiation of Algorithms: Theory, Implementation, and Application. SIAM, Philadelphia, Pa.
• 11: HAGER, G.D. 1993. Solving large systems of nonlinear constraints with application to data modeling. Interval Comput., 2, 169-200.
• 12: HAGER, G. 1990. Interval-based techniques for sensor data fusion. Prepr. GRASP Lab, Univ. of Pennsylvania, Philadelphia, Pa.
• 13: HANSEN, E.R. 1992. Global Optimization using Interval Analysis. Marcel Dekker, New York. Ira, M. AND KUBOTA, K. 1987. Methods of fast automatic differentiation and applications. Tech. Rep. RMI 87-02, Dept. of Mathematical Engineering and Instrumentation Physics, Univ. of Tokyo, Japan.
• 14: Chen-Huan Jan , R. Baker Kearfott, Expression parsing and rigorous computation of bounds on all solutions to practical nonlinear systems, 1992
• 15: KEARFOTT, R.B. 1992. An interval branch and bound algorithm for bound constrained optimization problems. J. Global Optim. 2, 259-280.
• 16: R. Baker Kearfott, Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems, Computing, v.47 n.2, p.169-191, 1991 [doi>10.1007/BF02253433]
• 17: R. Baker Kearfott, Interval Newton/generalized bisection when there are singularities near roots, Annals of Operations Research, v.25 n.1-4, p.181-196, Nov. 1990 [doi>10.1007/BF02283694]
• 18: R. Baker Kearfott, Preconditioners for the interval Gauss-Seidel method, SIAM Journal on Numerical Analysis, v.27 n.3, p.804-822, June 1990 [doi>10.1137/0727047]
• 19: KEARFOTT, R.B. 1987. Abstract generalized bisection and a cost bound. Math. Comput. 49, 179 (July), 187-202.
• 20: KEARFOTT, R. B. AND DU, K. 1992. The cluster problem in multivariate global optimization. Preprint, Dept. of Mathematics, Univ. of Southwestern Louisiana, Lafayette, La.
• 21: R. Baker Kearfott , Manuel Novoa, III, Algorithm 681: INTBIS, a portable interval Newton/bisection package, ACM Transactions on Mathematical Software (TOMS), v.16 n.2, p.152-157, June 1990 [doi>10.1145/78928.78931]
• 22: KEARFOTT, R. B. AND SHI, X. 1993. A preconditioner selection heuristic for efficient iteration with decomposition of arithmetic expressions for nonlinear systems. Interval Comput., 1, 15-33.
• 23: KEARFOTT, R. B. AND KING. g. 1994. Rigorous computation of surface patch intersection curves. Preprint. Dept. of Mathematics, Univ. of Southwestern Louisiana, Lafayette, La.
• 24: R. B. Kearfott , M. Dawande , K. Du , C. Hu, Algorithm 737: INTLIB---a portable Fortran 77 interval standard-function library, ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.447-459, Dec. 1994 [doi>10.1145/198429.198433]
• 25: KEARFOTr, R. B., DAWANDE, M., DU K.-S., AND HU, C.-Y. 1992. INTLIB: A portable Fortran-77 elementary function library. Interval Comput. 3, 5.
• 26: KEARFOTT, R. B., Hu, C. Y., AND NOVOA, M., III. 1991. A review of preconditioners for the interval Gauss-Seidel method. Interval Comput. 1, 1, 59-85.
• 27: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 28: Richard D. Neidinger, An efficient method for the numerical evaluation of partial derivatives of arbitrary order, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.159-173, June 1992 [doi>10.1145/146847.146924]
• 29: NEUMAIER, A. 1990. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, U.K.
• 30: RALL, L. B. 1987. An introduction to the scientific computing language Pascal-SC. Comput. Math. Appl. 14, 1, 53-59.
• 31: RALL, L. B. 1981. Automatic D~fferentiation: Techniques and Applications. Springer-Verlag, New York.
• 32: Helmut Ratschek , Jon Rokne, New computer methods for global optimization, Halsted Press, New York, NY, 1988
• 33: John M. Snyder, Interval analysis for computer graphics, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.121-130, July 1992
• 34: WALSTER, G. W., HANSEN, E. R., AND SENGIJPTA, S. 1985. Test results for a global optimization algorithm. In Numerical Optimization 1984, P. T. Boggs, R. H. Byrd, and R. B. Schnabel, Eds. SIAM Philadelphia, Pa., 272-287.
• 35: WALTER, W.V. 1993a. FORTRAN-XSC: A portable Fortran 90 module library for accurate and reliable scientific computing. Comput. Suppl. 9, 265-286.
• 36: WALTER, W.V. 1993b. ACRITH-XSC: A Fortran-like language for verified scientific computing. In Scientific Computing with Automatic Result Verification, E. Adams and U. Kulish, Eds., Academic Press, New York.
• 37: R. E. Wengert, A simple automatic derivative evaluation program, Communications of the ACM, v.7 n.8, p.463-464, Aug. 1964 [doi>10.1145/355586.364791]
• 38: J. M. Yohe, Software for Interval Arithmetic: A Reasonably Portable Package, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.50-63, March 1979 [doi>10.1145/355815.355819]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Fortran 90

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Languages

Keywords:
Fortran 90, automatic differentiation, global optimization, nonlinear algebraic systems, symbolic computation