Reprint Server

Verified Global Optimization with Taylor Model-based Range Bounders

Abstract

Taylor models provide enclosures of functional dependencies by a polynomial and an interval remainder bound that scales with a high power of the domain width, allowing a far-reaching suppression of the dependency problem. For the application to range bounding, one observes that the resulting polynomials are more well-behaved than the original function; in fact, merely naively evaluating them in interval arithmetic leads to a quadratic range bounder that is frequently noticeably superior to other second order methods.

However, the particular polynomial form allows the use of other techniques. We review the linear dominated bounder (LDB) and the quadratic fast bounder (QFB). LDB often allows an optimally tight bounding of the polynomial part if the function is monotonic. Perhaps more importantly, in case this is not possible, it also allows for a reduction of the domain simultaneously in all variables. Near interior minimizers, where the quadratic part of the local Taylor model is positive definite, QFB minimizes the quadratic contribution to the lower bound of the function, avoiding the infamous cluster effect for verified global optimization tasks.

Some examples of the performance of the bounders for unconstrained verified global optimization problems are given. We begin with various common toy problems of the community, where the efficiency of the Taylor model based bounders is demonstrated compared to interval based range bounders, i.e. the mere interval arithmetic and the centered form. We also show a rather challenging Lennard-Jones problem, where the above interval based range bounders have no success, thus we compare the performance of our Taylor model based verified global optimization package COSY-GO with one of the leading verified global optimization codes, GlobSol.

K. Makino, M. Berz, Transactions on Computers 11,4 (2005) 1611-1618

Download

Click on the icon to download the corresponding file.

Download Adobe PDF version (525975 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.