Improving Storage Handling of Interval Methods for Global Optimization ^{∗}

Csallner A. E. ^{†}

Acta Cybernetica 14 (1999) 1-.

Abstract

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 defined in general as follows:

min_{x∈X} f(x)  (1)

where X is a — possibly multidimensional — interval. If we denote the set of real intervals by II and f : IR^{n} → IR is the objective function of the problem, then X ∈ II^{n}. Note, that a great class of real-life bound-constrained global optimization problems are covered by (1), e.g., problems where the parameters are given with tolerances or if the optimizers are supposed to be inside a parameter region [2].

Problem (1) can be solved with verified accuracy with the aid of interval methods (see, e.g., [1, 5, 6, 7, 8]). These methods are based on the well-known branch-and-bound principle. Thus, a search tree is built where the whole search region — the interval X — is the root and the particular levels consist of subintervals which are partitions of their parents in the tree. Those branches that cannot be pruned have to be stored for later treatment. The kind of the storage method used can be of great importance in performance if the increase of the number of intervals to be stored is considerable.

∗This work has been supported by the Grants OTKA T017241, F025743, and FKFP 0739/1997.

†Department of Computer Science, Juhász Gyula Teacher Training College, 6725 Szeged, Boldogasszony sgt. 6, Hungary, e-mail: csallner@jgytf.u-szeged.hu

The following outlined algorithm is a model algorithm for interval subdivision methods for global optimization.

Algorithm 1 Model algorithm for interval subdivision methods for global optimization.

Step 1 Let S be an empty storage unit, the actual box A := X, and the iteration counter k := 1.

Step 2 Subdivide A into finite number s ≥ 2 of subintervals A_{i} satisfying A = ∪A_{i} so that int(A_{i}) ∩ int(A_{j}) = ∅ for all i ≠ j where ’int’ denotes the interior of a set.

Step 3 Let S := S ∪ {A_{i}}.

Step 4 Discard certain elements from S.

Step 5 Choose a new A ∈ S and delete it from S, S := S \ {A}.

Step 6 While termination criteria do not hold let k := k + 1 and go to Step 2.

Steps 3, 4, and 5 are using S, and their running time depends obviously on the storage handling of the algorithm. In the following we shall concentrate on these parts of the algorithm.

2 Worst Cases in Storage Handling of Interval Subdivision Methods

Because the efficiency of a branch-and-bound method depends highly on which branch, i.e., stored element is chosen as next to be treated, two basically different principles can be applied to handle the list. The first is to keep the list ordered and always pick up the first (or last) element in that ordering, while the second is to let the list be unordered and search for the next element in each step a new one is needed. The former saves computational time at picking up the elements, the latter at storing them. The time necessary for storage handling can be calculated in both cases.

We shall assume that Step 4 is not involved in the considered algorithm. In practice, this is the case in most implementations because cleaning up the stored elements is usually done when choosing a new A or before storing the new A_{i} intervals.

If the stored elements are unordered then Step 3 consumes some c_{1}s operations, and Step 5 some c_{2}|S|. If there is an ordering present which provides a constant time operation for finding the new element A in Step 5 then with a most efficient method the newly arisen s subintervals are stored in some c_{3}s log |S| time and the new actual interval A is delivered in constant c_{4} time. We summarize these results in the following lemma.

Lemma 1 The worst case time complexity of storage handling of Algorithm 1 is

c_{1}s + c_{2}|S|  (2)

if S is unordered, and

c_{3}s log |S| + c_{4}  (3)

if S is ordered. The results apply to a single iteration.

The algorithm keeps running for some k_{0} iteration steps, and our goal is now to determine the total time consumption of the storage handling for the whole running time of the algorithm.

2.1 Unordered Storage Handling

If the elements are unordered then we can simply consider the storage unit as a sequential list. The next theorem says that in this case the number of storage operations depends quadratically on the iterations completed.

Theorem 2 If S of Algorithm 1 is unordered and the process of finding a new actual interval A depends on a certain property of the list elements then the time complexity of storage operations up to the k_{0}-th iteration is

T (s, k_{0}) = O(sk_{0}^{2}).  (4)

Proof. From (2) of Lemma 1 it follows that a single iteration step uses c_{1}s + c_{2}|S| operations for appending the newly arisen intervals to the list and to find a new actual interval, where c_{1} and c_{2} are independent constants. The total number of storage operations done till the k_{0}-th iteration is hence

T (s, k_{0}) = ∑_{k=1}^{k_{0}}(c_{1}s + c_{2}|S|).  (5)

Let us check how Algorithm 1 works. After the first iteration at most s elements are put onto the empty list, and one of them is picked up as the new actual interval in the same iteration. Thus, the number of list elements becomes s − 1. The list grows in every iteration by at most s − 1. Hence, at the end of some k-th iteration in worst case the number of list elements equals

|S| = k(s − 1).  (6)

Now putting (5) and (6) together we have

T (s, k_{0}) = ∑_{k=1}^{k_{0}}(c_{1}s + c_{2}k(s − 1)) = c_{1}sk_{0} + c_{2}(s − 1)\frac{k_{0}^{2} + k_{0}}{2} ,  (7)

delivering (4) of the assertion. □

Note, that the proof does not presume the way of either subdividing or choosing a new actual box. Hence, all methods covered by the model Algorithm 1 obey Theorem 2.

2.2 Ordered Storage Handling

The following result is only sharp if in worst case more than a number of operations linear in the storage unit’s cardinality is needed to keep the elements in the storage unit ordered.

Theorem 3 If S of Algorithm 1 is kept ordered and the selection of the new actual intervals presume considering the elements’ ordering then the time complexity of storage handling up to iteration k_{0} is

T (s, k_{0}) = O(sk_{0}(log s + log k_{0})).  (8)

Proof. (3) of Lemma 1 says that storage handling costs c_{3}s log |S| + c_{4} in each iteration, where c_{3} and c_{4} are independent constants. Hence, summing this to the k_{0}-th iteration we get

T (s, k_{0}) = ∑_{k=1}^{k_{0}}(c_{3}s log |S| + c_{4}).  (9)

On the other hand, from (6) of the proof of Theorem 2 (9) can be extended to

T (s, k_{0}) = ∑_{k=1}^{k_{0}}(c_{3}s log(k(s − 1)) + c_{4}) =  (10)

= c_{3}s ∑_{k=1}^{k_{0}} log k + c_{3}sk_{0} log(s − 1) + c_{4}k_{0}.  (11)

The first term of (11) can be bounded from above using the following inequality:

∑_{k=1}^{k_{0}} log k ≤ ∫_{1}^{k_{0}+1} log x dx = \frac{1}{ln a}[x ln x − x]_{1}^{k_{0}+1} =  (12)

= \frac{1}{ln a}(k_{0} + 1) ln(k_{0} + 1) − \frac{k_{0}}{ln a},  (13)

where a denotes the base of the logarithm function in question. Note, that its value cannot influence the magnitude of the formula.

Substituting (13) into (11) provides the magnitudes that had to be proved. □

If s is considered as a constant then till finishing the k_{0}-th iteration the magnitude of storage handling’s time consumption is k_{0} log k_{0} in worst case, provided that any element can be inserted to the ordered storage unit in logarithmic time.

However, the time consumption’s dependence on s is higher by a log s factor than in the unordered case (see Theorem 2), though this might not mean heavy differences by the usually small values of s.

2.3 Hybrid Storage Handling

A further storage handling method can be used which has not been mentioned here yet. In reality, this is not a new one but a mixture of those from Subsection 2.1 and 2.2. The idea is [4] to keep some p_{0} elements from the storage unit ordered. These elements have to be the first ones regarding to the ordering of the whole. Hence, the new actual interval can always be chosen as the first of the ordered part. When inserting newly arisen intervals, one of them can supply for the ordered part. Otherwise a new element for the ordered part can be searched for in the unordered part. In worst case it can occur that for a substantial number of iterations the ordered part can only be refilled from the unordered part consuming O(|S| − p_{0}) time in each iteration.

Therefore, let us consider the following modification; we shall fix the value of p_{0} and store only the first p (1 ≤ p ≤ p_{0}) elements ordered. The remaining |S| − p elements are stored in a simple list.

Thus, every time a new interval is needed, it can be reached in constant time, since the first element of the ordered part does it. The other direction, namely, storing new elements is a little bit more difficult. For each new element it is checked whether it can be inserted into the ordered part of S. If it is the case, the element is inserted. If p = p_{0} held before the insertion, the last element is moved to the unordered part. If the new element is greater at the present ordering than any from the ordered part — assuming the ordering is increasing — then it is pushed simply onto the unordered part. This procedure can be done in some c_{5} log p_{0} time in worst case. Since there are at most s new elements to be inserted, the total amount of time needed for the storage operations is

c_{5}s log p_{0} + c_{6}  (14)

together with the constant number of operations for picking up the new actual interval. If p_{0} was considered as an independent constant, (14) could lead to the conclusion that for an arbitrary number k_{0} of iterations the time complexity of storage operations is linear in the variable k_{0}. In worst case, however, the ordered part can become empty forcing the new element to be chosen from the unordered part. Theoretically this can occur arbitrary many times. Thus, we should enhance the performance, namely, by doing the following two things:

1. We compensate the missing elements of the ordered part only if the ordered part runs empty, and then it is filled up with p_{0} elements from the unordered part.

2. We do not fix p_{0} directly as a constant, but say that it is always a κ proportion of |S|, where κ is a constant.

We shall call this algorithm the hybrid method. The time complexity of this method is described in Theorem 4.

Theorem 4 Let us implement Algorithm 1 with the storage handling described above as the hybrid method. Then the time complexity of storage handling operations is

T (s, k_{0}) = O(k_{0} log(sk_{0}))  (15)

in worst case.

Proof. Upon the assumptions the elements are stored in two disjunct units, one is ordered, the other is not. If the number of all the elements is |S| then the ordered part consists of at most p_{0} = κ|S| elements, where 0 < κ < 1 hold.

The procedure of storage handling involves two stages. In worst case, the first stage is done through p_{0} iterations, i.e., until the ordered part becomes empty. The next stage consists of a single iteration, where the ordered part is rebuilt.

In the second stage filling up the ordered part is done as follows. First of all, the first p_{0} elements are ordered which needs

t_{1} = c_{5}p_{0} log p_{0}  (16)

time. After this, the remaining |S| − p_{0} elements have to be inserted into the ordered part if possible, each with a log p_{0} time complexity. This can be done with the following time consumption:

t_{2} = c_{6}(|S| − p_{0}) log p_{0}.  (17)

¿From (6) of Theorem 2 we know that in worst case the number of list elements after the k_{0}-th iteration is |S| = k_{0}(s − 1). Let us apply this to (17) and add it to (16):

t = c_{5}p_{0} log p_{0} + c_{6}(k_{0}(s − 1) − p_{0}) log p_{0}.  (18)

It is known that at the iteration in question p_{0} equals κ|S| with a given κ. But citing (6) of the proof of Theorem 2 again we have

p_{0} = κ|S| = κk_{0}(s − 1)  (19)

Let us use this to (18):

t = (c_{5}κ + c_{6}(1 − κ))k_{0}(s − 1) log(κk_{0}(s − 1))  (20)

These t operations only have to be done periodically after each p_{0} iterations, where p_{0} grows monotonously. Applying amortized analysis t can be apportioned among the next p_{0} iterations to get the time complexity of storage handling for a single iteration in average. If for this the actual |S| is used, we get an underestimation due to the increasing value of |S| and hence p_{0}. Thus, for the time complexity the following holds:

k_{0}^{−1}T (s, k_{0}) ≤ \frac{t}{p_{0}} + c_{7} = \frac{t}{κk_{0}(s − 1)} + c_{7},  (21)

where c_{7} is the time consumption of the first stage. Applying this to the form for t calculated in (20) we have

k_{0}^{−1}T (s, k_{0}) ≤ \frac{c_{5}κ + c_{6}(1 − κ)}{κ} log(κk_{0}(s − 1)) + c_{7},  (22)

delivering the magnitude of (15) after k_{0} iterations. □

The result of Theorem 4 is a nice enhancement in storage handling. To reach it we had to make two further assumptions previous to the theorem. None of them can be left away unless damaging the bound of (15). Namely, if the ordered part is supplied continually then in worst case the time complexity becomes the same as in the unordered case (see Theorem 2). On the other hand, if p_{0} is a value independent from |S| then the amortized analysis leaves a term containing k_{0} on first degree in the formula also resulting in a quadratic time complexity in k_{0} similar to (4).

¿From the three investigated methods the dependence on s is far the best with its log s complexity. This magnitude means that in practice — where s > 8 hardly ever occurs — the influence of s is unimportant.

Moreover, for the dependence on the number k_{0} of iterations the following theorem holds.

Theorem 5 For the time complexity dependence on the number k_{0} of iterations the magnitude k_{0} log k_{0} is optimal in worst case.

Proof. It will be proved that if it was not optimal then an algorithm could be given to order n elements in less than O(n log n) time in worst case.

Let the n data to be ordered be denoted by a_{1}, a_{2}, …, a_{n}. We can determine the max := max_{i=1,...,n} a_{i} value in linear time, and let a be greater regarding to the ordering than max. Then the algorithm is the following. We take a list handling method for interval subdivision methods which has a smaller time complexity than k_{0} log k_{0} provided the algorithm is stopped after k_{0} iterations. Now we place the data into the storage unit and begin to select elements from it as the ordering desires it. Instead of each element removed at least two further instances of the value a is put into the storage unit. After n iterations the original data are taken from the storage unit in the right order in less than n log n time which is a contradiction. □

Corollary 6 The ordered and hybrid list handling methods for interval branchand-bound algorithms are both optimal.

2.4 List Handling of Hansen Methods

In the previous three subsections it has been assumed that the sequence of storing and recalling elements of the storage unit have not necessarily the same order. However, E.R. Hansen’s subdivision method [5, 8] selects the oldest element waiting in the storage unit — which is a simple FIFO list in this case — in Step 5 of Algorithm 1, thus, the time complexity for a single iteration is constant. The time complexity after k_{0} iterations is linear in the variable k_{0}. The reason for using the algorithm of Hansen yet quite rarely is that its convergence speed is in best case the same (see [3]) as of all efficiently converging interval subdivision methods in worst case.

3 Best Cases and Concluding Remarks

It is obvious that no storage handling can perform better than linearly depending on the number of iterations since there must be a few storage handling acts in every iteration. A straight consequence of this fact and of the properties discussed in Subsection 2.4 is that the Hansen methods achieve this linear dependence.

Upon the worst cases the unordered and mixed storage handling methods are the worst with their quadratic dependence. For the unordered handling this is the best case, as well, because looking up all list elements for choosing the new actual box cannot be avoided, at all. For the mixed handling it can occur that a newly arisen subinterval can always immediately be inserted into the ordered part consuming constant time in k_{0}. Thus, the best case behavior shows linear dependence.

The same thoughts lead to the statements about the ordered and hybrid handling methods. These methods both have linear time complexity in best case concerning the number of iterations made.

The optimal storage handling time complexity is k_{0} log k_{0} — where k_{0} denotes the iteration of termination — for interval branch-and-bound methods if the order of the sequence of resulting elements is not necessarily the same as that of the recalled elements.

This optimal complexity is obtained for the ordered storage types and the hybrid method.

If the algorithm itself provides the ordering of new elements then the worst case is the same as the best case, i.e., linear regarding to the iterations completed (Hansen algorithm).

The best and worst cases for the rest of the methods are summarized below:

Method Best Case Worst Case
Unordered  k_{0}^{2}  k_{0}^{2}
Ordered  k_{0}  k_{0} log k_{0}
Mixed  k_{0}  k_{0}^{2}
Hybrid  k_{0}  k_{0} log k_{0}

Note, that the worst case of the ordered storage handling is only true if a best implementation, i.e., a balanced search tree is used. Otherwise the worst case can also grow to k_{0}^{2} as for the unordered case.

Average cases cannot be treated simply deriving them from the best and worst cases, respectively, since the interval branch-and-bound methods can be applied to every programmable function and thus their influence to the storage’s behavior cannot be predicted in general. Numerical tests are in progress but they are not at hand at the present.

References

[1] Alefeld G. and Herzberger J. (1983), Introduction to Interval Computations, Academic Press, New York.

[2] Csallner A.E. (1993), Global Optimization in Separation Network Synthesis, Hungarian Journal of Industrial Chemistry, 21, pp. 303–308.

[3] Csallner A.E. and Csendes T. (1995), Convergence Speed of Interval Methods for Global Optimization and the Joint Effects of Algorithmic Modifications, IMACS/ GAMM SCAN-95 Conference, p. 33, Wuppertal, Germany, September 26-29, 1995.

[4] Csendes T. and Pintér J. (1993), The Impact of Accelerating Tools on the Interval Subdivision Algorithm for Global Optimization, European Journal on Operational Research, 65, pp. 314–320.

[5] Hansen E.R. (1992), Global Optimization Using Interval Analysis, Marcel Dekker, New York.

[6] Kearfott R.B. (1996), Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht.

[7] Moore, R.E. (1966), Interval Analysis, Prentice Hall, Englewood Cliffs NJ.

[8] Ratschek H. and Rokne J. (1993), Interval Methods, In: Handbook of Global Optimization, Horst R. and Pardalos P.M. (eds.), Kluwer, Dordrecht, pp. 751–