Rigorous Global Search using Taylor Models
AbstractA 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).
M. Berz, K. Makino,
Symbolic Numeric Computation 2009, (2009) 11-19
DownloadClick on the icon to download the corresponding file.
Download Adobe PDF version (6607448 Bytes).
Go Back to the reprint server.
Go Back to the home page.
This page is maintained by Kyoko Makino. Please contact her if there are any problems with it.