On stopping criteria in verified nonlinear systems or optimization algorithms

ABSTRACT

Traditionally, iterative methods for nonlinear systems use heuristic domain and range stopping criteria to determine when accuracy tolerances have been met. However, such heuristics can cause stopping at points far from actual solutions, and can be unreliable due to the effects of round-off error or inaccuracies in data. In verified computations, rigorous determination of when a set of bounds has met a tolerance can be done analogously to the traditional approximate setting. Nonetheless, the range tolerance possibly cannot be met. If the criteria are used to determine when to stop subdivision of n-dimensional bounds into subregions, then failure of a range tolerance results in excessive, unnecessary subdivision, and could make the algorithm impractical. On the other hand, interval techniques can detect when inaccuracies or round-off will not permit residual bounds to be narrowed. These techniques can be incorporated into range thickness stopping criteria that complement the range stopping criteria. In this note, the issue is first introduced and illustrated with a simple example. The thickness stopping criterion is then formally introduced and analyzed. Third, inclusion of the criterion within a general verified global optimization algorithm is studied. An industrial example is presented. Finally, consequences and implications are discussed.

REFERENCES

• 1: ALEFELD,G.AND HERZBERGER, J. 1983. Introduction to Interval Computation. Academic Press, Inc., New York, NY.
• 2: CORLISS, G. F. 1998. Globsol entry page. http://www.mscs.mu.edu/~globsol/
• 3: HANSEN, E. R. 1992. Global Optimization Using Interval Analysis. Marcel Dekker, Inc., New York, NY.
• 4: R. Baker Kearfott, Algorithm 763: INTERVAL_ARITHMETIC: a Fortran 90 module for an interval data type, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.385-392, Dec. 1996 [doi>10.1145/235815.235816]
• 5: KEARFOTT, R. B. 1996b. Rigorous Global Search: Continuous Problems. Kluwer Academic, Dordrecht, Netherlands.
• 6: 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]
• 7: 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
• 8: NEUMAIER, A. 1990. Interval Methods for Systems of Equations. Cambridge University Press, New York, NY.
• 9: RATZ,D.AND CSENDES, T. 1995. On the selection of subdivision directions in interval branch-and-bound methods for global optimization. J. Global Optim. 7, 183-207.
• 10: ROCCO,C.M.,MILLER,A.J.,AND KEARFOTT, R. B. 1999. Uncertainty analysis of indirect-grouping maintenance strategy using an interval arithmetic approach. Preprint. Universidad Central de Venezuela, Miam, FL. Available via: POBA INTERNATIONAL No. 100, P.O. Box 02-5255, Universidad Central de Venezuela, Miami, FL 33102.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Interval arithmetic
      G.1.5 Roots of Nonlinear Equations
          Subjects: Error analysis; Iterative methods; Systems of equations
      G.1.6 Optimization
          Subjects: Constrained optimization; Global optimization

General Terms:
Algorithms, Performance, Reliability, Verification

Keywords:
GlobSol, stopping criteria, verified computations