Improving storage handling of interval methods for global optimization
András Erik Csallner · 1999
Global nonlinear optimization problems can be solved by interval subdivision methods with guaranteed reliability. These algorithms are based on the branch-and-bound principle and use special storage utilities for the paths not pruned from the search tree yet. In this paper the possibilities for the kinds of applied storage units are discussed. If no ordering is kept in the storage unit then the dependence of the number of operations demanded by the storage on the iterations completed is quadratic in worst case. On the other hand, ordering the elements as it is necessary for choosing new elements from the storage unit for backtracking, the worst case for the number of storage operations done to the k-th iteration has the magnitude k log k. The hybrid method defined in this paper satisfies the same complexity properties. It is also proved that the k log k magnitude is optimal. 1 Global Optimization and Interval Methods --- Introduction The global optimization problem can be...