Introduction

GlobSol contains two main computational procedures:

find_roots (run_roots_delete):

A program to compute solutions to nonlinear systems of equations.

find_global_min (opttest):

A program to solve constrained global optimization problems.

The programs find_roots and find_global_min have separate but somewhat similar high-level structures, and share many lower-level subroutines in GlobSol. Other subroutines, while different for find_global_min and find_roots, are theoretically similar.

The underlying theory and techniques for these two computations are introduced here. The general rootfinding problem, along with general considerations relevant to GlobSol, appear in §2. A corresponding statement and GlobSol considerations for constrained global optimization appear in §3.

The overall algorithm in GlobSol for either root-finding or global optimization is a branch and bound algorithm based on interval arithmetic. The abstract structure for such branch and bound algorithms is introduced in §4.

GlobSol is based on verified computations, in which the computation carries the weight of a mathematical proof. That is, rigorous, tight bounds on all solutions are found, provided the computation completes within the available time and memory resources. In GlobSol, such verification is based on interval arithmetic. An extremely brief introduction to interval arithmetic appears in §5; For additional information, see http://interval.louisiana.edu/preprints/survey.ps (Postscript, approx. 200KB) or http://interval.louisiana.edu/preprints/survey.dvi (TeX DVI, approx. 75KB) for a preprint of: Interval Computations: Introduction, Uses, and Resources, Euromath Bulletin 2 (1), pp. 95-112 (1996),

Actual verification proceeds with interval Newton methods, that are introduced in §6.

Finally, a technique we have called substitution iteration, related to constraint propagation techniques, is optionally employed, in somewhat different ways, in find_roots and in find_global_min. The technique is introduced in §11.

For constrained optimization problems, interval Newton methods use the Fritz-John system, described in §7. Also, for constrained problems, it is important to verify that a feasible point exists within given small regions. This is introduced in §8.

Special techniques GlobSol uses for processing bound constraints, as well as advice on setting up bound-constrained problems, appear in §9.