| A Taylor model of a smooth function $f$ over a
sufficiently small domain $D$ is a pair $(P,I)$ where $P$ is the Taylor
polynomial of $f$ at a point $d$ in $D$, and $I$ is an interval such that $f$
differs from $P$ by not more than $I$ over $D$. As such, they represent a
hybrid between numerical techniques for the interval and the coefficients of
$P$ and algebraic techniques for the manipulation of polynomials. A calculus
including addition, multiplication and differentiation/integration is
developed to compute Taylor models for code lists, resulting in a method to
compute rigorous enclosures of arbitrary computer functions in terms of Taylor
models. The methods combine the advantages of numeric methods, namely finite
size of representation, speed, and no limitations on the objects on which
operations can be carried out with those of symbolic methods, namely the
ability to treat functions instead of points and making rigorous statements.
We show how the methods can be used for the problem of rigorous global search
based on a branch and bound approach, where Taylor models are used to prune
the search space and resolve constraints to high order. Compared to other
rigorous global optimizers based on intervals and linearizations, the methods
allow the treatment of complicated functions with long code lists and with
large amounts of dependency. Furthermore, the underlying polynomial form
allows the use of other efficient bounding and pruning techniques, including
the linear dominated bounder (LDB) and the quadratic fast bounder (QFB). |