zbMATH — the first resource for mathematics

Extensions of affine arithmetic: application to unconstrained global optimization. (English) Zbl 1274.65184
Summary: Global optimization methods in connection with interval arithmetic permit to determine an accurate enclosure of the global optimum, and of all the corresponding optimizers. One of the main features of these algorithms consists in the construction of an interval function which produces an enclosure of the range of the studied function over a box (right parallelepiped). We use here affine arithmetic in global optimization algorithms, in order to elaborate new inclusion functions. These techniques are implemented and then discussed. Three new affine and quadratic forms are introduced. On some polynomial examples, we show that these new tools often yield more efficient lower bounds (and upper bounds) compared to several well-known classical inclusion functions. The three new methods, presented in this paper, are integrated into various branch and bound algorithms. This leads to improve the convergence of these algorithms by attenuating some negative effects due to the use of interval analysis and standard affne arithmetic.

65K10 Numerical optimization and variational techniques
65G30 Interval and finite arithmetic
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: Link