Extentions of Affine Arithmetic: Application to Unconstrained Global Optimization

Frédéric Messine (Université de Pau et des Pays de l'Adour UFR-Sciences et Techniques, Département d'Informatique, France)

Abstract: 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.

Keywords: affine arithmetic, branch and bound algorithm, global optimization, inclusion functions, interval arithmetic

Categories: G.1.0, G.1.6