Extentions of Affine Arithmetic: Application to Unconstrained Global Optimization
Extentions of Affine Arithmetic: Application to Unconstrained Global Optimization
复制标题
DOI：
10.3217/jucs-008-11-0992
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
F. Messine
中科院分区：
文献类型：
--
作者：
F. Messine
结合区间算法的全局优化方法允许确定全局最优值和所有相应优化器的精确包络。这些算法的主要特点之一在于构造一个区间函数，该区间函数在方框(右六面体)上产生所研究函数的范围的封闭。我们在全局优化算法中使用仿射算法，以阐述新的包含函数。实现了这些技术，然后对其进行了讨论。介绍了三种新的仿射形式和二次形式。在一些多项式的例子中，我们证明了这些新工具通常比几个著名的经典包含函数产生更有效的下界(和上界)。本文提出的这三种新方法被集成到各种分支定界算法中。通过使用区间分析和标准仿射算法，减弱了区间分析和标准仿射算法的一些负面影响，从而提高了算法的收敛速度。
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 affine arithmetic.