A new interval approach to global optimization

L. V. Kolev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 39 (1999) no. 5, pp. 759-769

Résumé

Interval methods are iterative methods capable of solving the general nonlinear programming problem globally, providing infallible bounds both on the optimum (optima) and the corresponding solution coordinates. However, their computational complexity grows rapidly with the dimension of the problem and the size of the search domain. In this paper, a new interval approach to solving the global optimization problem is suggested, which permits the development of interval optimization methods of improved efficiency. It is based on the following ideas. First, every nonlinear function $f_i(x)$ involved in the solution scheme chosen is transformed into:semiseparable form (sum of terms). Each term of this form is either a function $f_{ij}(x_j)$ of a single variable or a product $x_kx_i$ of two variables. These terms are then enclosed by corresponding linear interval functions. Thus, at each iteration of the computation process, a specific linear interval system is obtained where only the rightnand side involves intervals while the known interval methods are based on a linear system with interval coefficients. The former system is much easier to solve which accounts for the considerable numerical efficiency of the new approach.