Subdivision Direction Selection in Interval Methods for Global Optimization.
The role of the interval subdivision-selection rule is investigated in branch-and-bound algorithms for global optimization. The class of rules that allows convergence for the model algorithm is characterized, and it is shown that the four rules investigated satisfy the conditions of convergence. A numerical study with a wide spectrum of test problems indicates that there are substantial differences between the rules in terms of the required CPU time, the number of function and derivative evaluations, and space complexity, and two rules can provide substantial improvements in efficiency.
Introduction
. Interval subdivision methods for global optimization [7, 21]
aim at providing reliable solutions to global optimization problems
min
(1)
where the objective function f : continuously differentiable, and X '
IR n is an n-dimensional interval. In many cases, only the globally optimal solutions
are acceptable [4, 22], and the local minima are less important. No special problem
structure is required: only inclusion functions of the objective function and its gradient
are utilised [1]. Denote the set of compact intervals by II := f[a; b] j a  b; a; b 2 IRg
and the set of n-dimensional intervals (also called simply intervals or boxes) by II n .
We call a function F : II n ! II to be an inclusion function of f :
for each interval Y in X . In other words, f(X) ' F (X),
where f(X) is the range of f(x) on X . The inclusion function of the gradient of f(x)
is denoted by F 0 (X).
There are several ways to build an inclusion function for a given optimization
problem (e.g. by using the Lipschitz constant). Interval arithmetic [1, 6, 7, 21] is
a convenient tool for constructing the inclusion functions, and one can get those for
almost all functions that can be calculated by a finite algorithm (i.e. not only for given
expressions).
It is assumed in the following that the inclusion functions have the isotonicity
property, i.e. X ' Y implies F (X) ' F (Y ), and that for all the inclusion functions
(2)
holds, where w(X) is the width of the interval X
and
The generality of the problem class and the modest requirement of the existence
of the inclusion functions stress the importance of each improvement in the efficiency
y Department of Applied Informatics, J'ozsef Attila University, Szeged, '
Arp'ad t'er 2., Hungary (E-
mail: csendes@inf.u-szeged.hu). The work has been supported by the Grants CIPA3510CT926141 of
the COST Project of the EC, OTKA 2879/1991, and MKM 414/1994.
z Institut fur Angewandte Mathematik, Universitat Karlsruhe, Kaiserstrae 12, D-76128 Karlsruhe,
Germany (E-mail: ae07@rz.uni-karlsruhe.de).
of the interval global optimization methods. After studying the effects of some accelerating
tools [5], the present paper investigates the role of the selection of the interval
subdivision direction.
2. Model algorithm and subdivision direction selection rules. First we
give a simple model algorithm that has the most important common features of the
interval subdivision methods for global optimization (cf. [2, 3, 5, 6, 7, 16, 21, 22]).
local search procedure is included. The Newton-like steps are also not built in,
since these would need the inclusion of the Hessian. On the other hand, the cut-off
and monotonicity tests are applied, because their usage does not require additional
information on the problem. It would not make sense to skip these tests. Although
cross-effects of the direction selection rules and the skipped steps are possible, the
investigation of their numerical implication is subject of an other study.
The model algorithm is as follows:
(X). Initialize the list and the
cut-off level z = maxF (X).
Choose a coordinate direction k 2 ng.
Bisect Y in direction k:
Step 4 Remove (Y; y) from the list L.
Step 5 Cut-off test: discard the pair
Step 6 Monotonicity test: discard the remaining pair
any j 2 2.
Step 7 Add the remaining pair(s) to the list L. If the list becomes empty, then
STOP.
Step 8 Denote the pair with the smallest second element by (Y; y).
Step 9 If the width of F (Y ) is less than ", then print F (Y ) and Y , STOP.
Go to Step 1.
The interval Y , that is first set in Step 0, and then updated in Step 8, is called the
leading box, and the leading box of the iteration number s is denoted by Y s . Notice
that the cut-off test does not have any effect on the convergence of the algorithm, it
may just decrease the space complexity [5], the maximal length of list L.
The interval subdivision direction selection rule in Step 1 is the target of our
present study. In the following, we describe shortly the four rules discussed. All the
rules select a direction by using a merit function:
ae
ng and
oe
where D(i) is determined by the given rule.
Rule A. First the interval width oriented rule was applied [16, 21, 24], this
chooses the coordinate direction with
This rule was justified by the idea that if the original interval is subdivided in a uniform
way, then the width of the actual subintervals goes the quickest to zero. It has also been
used for generating subdivision direction in other optimization procedures (e.g. [11]).
924 T. Csendes and D. Ratz
The algorithm with Rule A is convergent both with and without the monotonicity test
(e.g. in [5] and in [21]). This rule allows a relatively simple analysis of the convergence
speed (as in [21], Chapter 3, Theorem 6). The usual definition of Rule A does not
specify one single coordinate direction if the maximum is achieved many times in (3).
That is why we take the smallest one. For the sake of brevity, we call this interval
subdivision direction selection rule in the sequel as Rule A.
Rule B. Hansen described an other rule (initiated by G. W. Walster) [7]. The
direct aim of this heuristic direction selection rule is to find the component for which
is the largest (where m(X i is the midpoint of the interval
The factor W i that should reflect how much f varies as x i varies over X i is then
approximated by w(F 0
The latter is not an upper bound for W i (cf. [7]
page 131 and Example 2 in Section 3 of the present paper), yet it can be useful as a
merit function.
The Rule B selects the coordinate direction, for which (3) holds with
It should be noted that the model algorithm represents only one way how Rule B was
applied in [7]. The subdivision was, e.g., carried out also for many directions in a
single iteration step.
Rule C. The next rule of our investigation was defined by Ratz [23]. The underlying
idea was to minimize the width of the inclusion:
Obviously, that component is to be chosen for which w(F 0
is the
largest. Thus, Rule C can also be formulated with (3) and
The important difference between (5) and (6) is that in Rule C the width of the
multiplied intervals is maximized and not the multiplied widths of the respective
intervals (and these are in general not equal). After a short calculation, the right-hand
side of (6) can be written as maxfj minF 0
This corresponds to the "maximum smear" (used as a direction selection merit function
solving systems of nonlinear equations [13]) for the case f :
It is easy to see that the Rules B and C give the same merit function value if
and only if either min F 0
It is worth mentioning, that
i (X)jg is the best possible estimation of the Lipschitz constant
of the (one-dimensional) function f(x) with fixed variables x
Subdivision direction selection in interval methods for global optimization 925
Fig. 1. Remaining subintervals after 100 iteration steps of the model algorithm with
the direction selection rules A, B, C, and D for the Six-Hump-Camel-Back problem.
for the current box X on the basis of the available inclusion function
information. This formulation shows how the model algorithm with the direction selection
rule C can be related to Lipschitzian partition methods for global optimization
[19, 20].
Rule D. The fourth rule is derivative-free like Rule A, and reflects the machine
representation of the inclusion function F (X) (see [6]). It is again defined by (3) and
by
otherwise:
This rule (called Rule D) may decrease the excess width w(F of the
inclusion function that is caused in part by the floating point computer representation
926 T. Csendes and D. Ratz

35Fig. 2. Remaining subintervals after 10 iteration steps of the model algorithm with
the direction selection rules A, B, C, and D for the EX1 problem.
of real numbers. Consider the case when the component widths are of similar order,
and the absolute value of one component is dominant. The subdivision of the latter
component may result in a worse inclusion, since the raster points of the representable
numbers are sparser in this direction.
Typical distributions of subintervals are shown in Figure 1 for the discussed direction
selection rules A, B, C, and D, respectively. The Six-Hump-Camel-Back standard
global optimization test problem [4, 21, 23] was solved with the model algorithm
(initial box [\Gamma2:0; 2:0] 2 ). The figures show the situations after 100 iterations. The
numbers of subintervals are 38, 31, 32 and 42, respectively. These figures reflect the
space complexity of the related procedures to a certain extent. The direction selection
rule A tends to form square-like boxes, while Rule D produces elongated intervals
as the magnitudes of the coordinates differ. Rules B and C generate similar sets of
Subdivision direction selection in interval methods for global optimization 927
subintervals reflecting the utilised derivative information, too. The sets of subintervals
closely fit the respective level sets, and the differences are mainly due to the overestimating
inclusion functions. Since the global minimizer points are in the remaining
subintervals, the uncertainty in the place of the global minimum has been deceased
substantially. Figure 1 shows little about the efficiency of the involved algorithms -
it will be addressed in a later section.
A test problem, called EX1 has been constructed to show the differences caused by
the different direction selection rules: the simple function
is to be minimized on the initial box of [0:0; 2:0] \Theta [10:0; 12:0].
The sine terms were added to inhibit a fast convergence due to the monotonicity
property. Figure 2 provides the sets of subintervals after just 10 iterations with the
respective model algorithms. The subboxes denoted by * are those selected for the
next subdivision, and the figures in the subintervals indicate their age: the intervals
with 1 are the oldest among the remaining boxes. Rule A again tends to form square-
like boxes, while the others produce elongated subintervals. The direction preferred
by Rule D is different from that chosen often by Rules B and C. Notice that the model
algorithm with Rule A was unable to delete a subinterval from the initial box, while
the greatest volume decreases were due to Rules B and C.
3. Convergence and the direction selection rules. For the next theoretical
study, we define the sequence of intervals that can be produced by the model
algorithm, and we specify a property of the direction selection rules that can ensure
convergence for our algorithm. With the exception of Rule A [21], no similar convergence
investigation has been published.
Assume that the direction selection rules decide using exclusively the information
provided by X , F (X) and F 0 (X) for the interval X to be subdivided. This assumption
is valid for Rules A to D. The strategy to utilize all information collected in earlier
iteration steps may increase the space complexity substantially.
Definition 3.1. We call an infinite sequence of intervals (Y s
s=0 an infinite
subdivision sequence of Y , if Y for each nonnegative integer s the box
Y s+1 is given as Y s+1
is the direction selected by the
given rule with Y s , F (Y s ) and F 0 (Y s ).
It is easy to see that if X is not discarded by the monotonicity test and
the set of leading boxes (Y s
s=0 contains at least one infinite subdivision sequence.
The set (Y s
s=0 contains only infinite subdivision sequences and finite sequences of
subintervals that end with a box Y for which
ng.
The latter finite sequences do not affect the convergence of the procedure.
Definition 3.2. We call a direction selection rule balanced, if for all intervals X,
for all isotone inclusion functions F (X) and F 0 (X) having property (2), and for each
infinite subdivision sequence of X that is a subsequence of the leading boxes (Y s
the sequence of directions generated by the given rule contains each k of the possible
directions an infinite number of times.
The name of this property reflects the fact that even though such rules do not
necessarily deliver the directions in a uniform way, yet for each direction the distance
between two appearances is a finite number of iteration steps.
Denote the set of accumulation points of the sequence (Y s
s=0 by A, the global
minimum of f(x) on X by f   , and the set of global minimizer points of f(x) on X by
928 T. Csendes and D. Ratz
. Recall that the inclusion functions F (X) and F 0 (X) are assumed to be isotone
and the property (2) holds for them. Set the stopping criterion parameter " to zero
for the sake of the convergence investigation.
The monotonicity test may discard subintervals containing global minimizer points
if they are on the boundary of X . Since the main point in the present study is
to investigate the impact of the direction selection rules on the convergence of the
model algorithm, we assume that there exists a stationary point x   2 X for which
and that w(X) ? 0 (since otherwise the solution requires no search and
thus no subdivision).
Theorem 3.1. The model algorithm converges in the sense that lim s!1 w(Y s
if and only if the interval subdivision direction selection rule is balanced.
Proof. 1. Assume that the direction selection rule has the required property,
and the model algorithm produces the infinite sequence of intervals (Y s
s=0 for a
global optimization problem given by X , F and F 0 . The sequence (Y s
s=0 has to
contain at least one subsequence (Y s l
l=0 which is an infinite subdivision sequence of
Y . By construction, (Y s
s=0 contains a union of certain infinite subdivision sequences,
and some additional boxes that belong to subdivision sequences that were terminated
by the monotonicity test. The latter boxes do not affect the value of lim s!1 w(Y s ).
Now the property of balancedness holds for each infinite subdivision sequence (Y s l
incorporated in (Y s
s=0 , and it implies lim l!1 w(Y s l Hence, we have proven
that lim s!1 w(Y s
2. Assume now that there exists an infinite subdivision sequence for the actual
direction selection rule such that an i 2 ng with w(X appears only a
finite number of times in the generated sequence of directions. For such an i obviously
Theorem 3.2. Assume that the interval subdivision direction selection rule is
balanced. Then the model algorithm converges to global minimizer points in the sense
that lim s!1 F (Y s
Proof. Having a stationary point x   2 X with f(x
holds for each subinterval Z containing it. Such subintervals cannot be
deleted by the monotonicity test. Consequently, x   is in the union of the boxes in the
list L in each iteration. As (Y s
s=0 is then an infinite sequence of intervals inside X ,
the set of accumulation points A cannot be empty. The inclusion property of F (X)
and the definition of the leading box imply that f   2 F (Y s ) for each iteration number
Now lim s!1 w(Y s according to Theorem 3.1. This equation and the property
(2) imply lim s!1 w(F (Y s
thus also A ' X   .
One direction of the assertions of Theorem 3.1 and Theorem 3.2 is a generalization
of some convergence results in [21] for the model algorithm with the studied class of
direction selection rules.
The opposite direction of the statements in Theorem 3.2 is not always true: A 6= ;
e.g. holds also if the direction selection rule is not balanced. Notice also that f   2
using any special property of the direction selection rule.
Theorem 3.3. Assume that the model algorithm converges for a given problem
(1) to global minimizer points in the sense that lim s!1 F (Y s thus A ' X   .
Then either the algorithm proceeds on the problem like an algorithm with a balanced
direction selection rule, or there exists a box "
X,
Subdivision direction selection in interval methods for global optimization 929
and w( "
ng for all coordinate directions that are selected only a
finite number of times.
Proof. Assume that there exists no "
X with the property defined in Theorem
3.3. Then w(F (Y
which there exists an x 2 Y such that
implies lim s!1 w(Y s and with Theorem 3.1 we obtain that each direction
ng for which w(X i selected an infinite number of times.
The main result of Theorem 3.3 is that with the exception of problems for which a
X as defined above exists, the direction selection rule must be balanced to ensure
convergence to global minimizer points.
Corollary 3.4. The subdivision direction selection Rules A and D are balanced,
and thus the model algorithm converges to global minimizer points with each of these
rules.
Proof. Assume for Rules A and D that a global optimization problem is given by
s=0 be an infinite subdivision sequence of this problem, and let
ng be a coordinate direction for which w(X
Consider first the model algorithm with the direction selection Rule A. Then D(i)
is positive according to (4), and i is chosen as the next subdivision direction after
steps at the latest (b:c denotes the largest
integer that is not greater than the argument). This expression gives 1 if w(Y s
i ) is the
largest, and it is finite for all compact intervals (with w(Y s
Having i selected
as a subdivision direction after a finite number of iteration steps, i must appear an
infinite number of times for each infinite subdivision sequence.
Consider now the model algorithm with Rule D, and assume again that a coordinate
direction i with w(X chosen only a finite number of times. Then D(i) is
constant and positive (cf. (7)) after a finite number of steps. Consider only that part
of the sequence (Y s
s=1 , for which D(i) is constant and positive. Let j be another
index that is selected an infinite number of times. Although D(j) is not necessarily
monotonously decreasing, 1. Then there exists an s 0 with
this is a contradiction.
Corollary 3.5. Either the subdivision direction selection Rules B and C choose
each direction i 2 ng for which w(X i an infinite number of times, and
thus the model algorithm converges to global minimizer points with each of these rules,
or the algorithm converges to a subinterval of X with a positive width that contains
only global minimizer points.
Proof. Assume again for Rules B and C that a global optimization problem is given
by X , F and F 0 . Let (Y s
s=0 be an infinite subdivision sequence of this problem, and
ng be a coordinate direction for which w(X
Consider the model algorithm with the direction selection Rule B. Now
means that w(F 0
discarded by the
monotonicity test, or F 0
so that f(x) is independent of x i . In the latter case,
no subdivision is required with respect to i. Hence we can assume D(i) ? 0 without
loss of generality. Assume that i is selected only a finite number of times. Then w(Y s
remains constant and positive after a finite number of steps. Let j be another index
that is chosen an infinite number of times. Then w(F 0
and with w(Y s
Thus the global minimum f   must
be attained at each point of a result interval lim 1
since an interval Y s
with
would have been discarded by the monotonicity test. Thus either the
T. Csendes and D. Ratz
algorithm converges to a subinterval of X that contains only global minimizer points,
or each direction is selected an infinite number of times.
Now consider the model algorithm with the subdivision direction selection Rule
C, and assume that j is such a coordinate direction that is selected an infinite number
of times. Then Y s
converges to zero during the iteration. Having F 0
bounded and isotone, ng for
which the merit function D(i) is nonnegative in the beginning. Then
either the direction i is selected infinitely many times,
or lim 1
because of w(Y s
each s. In the latter case each point of
the interval lim 1
is a global minimizer point.
Example 1. We want to find global minimizer points of problem (1) with
2 on the interval We use the range functions as inclusion functions,
so
. Using the direction
selection Rule C with the model algorithm,
w([0:0; 2:0][\Gamma0:5;
. Thus the second coordinate is selected for sub-
division, and the next leading box is Y
and 0:25. The procedure converges to the interval Y
without a single subdivision in the first coordinate. According to the comment after
the definition of Rule C, the merit function values and the selected directions are the
same with Rule B, i.e. the same result interval is obtained by the inclusion of Rule B.
Example 2. Our algorithm with Rule B may become non-convergent if we remove
the monotonicity test. Consider e.g. the function
2 . With F 0
Rule B chooses always direction 2. In
this case lim s!1 min F (Y s ) 6= lim s!1 maxF (Y s ), where Y s is again the leading box
Y in the iteration number s. Although the probability to have this phenomenon in
real-life problems is small, yet it is worth to note this behavior that differs from those
of the other rules.
The aimed problem class is obviously too wide to allow meaningful theoretical
comparisons between the studied subdivision rules. The next section shows results of
extensive numerical testing.
4. Numerical experiences. The numerical tests were carried out on an IBM
RISC 6000-580 workstation, coded in Fortran-90 with an implemented interval arithmetic
package handling the outside rounding necessary for the inclusion functions. The
authors thank R. B. Kearfott and W. V. Walter for their kind help in providing the
interval arithmetic package [12] and the necessary modules. The inclusion functions
were produced by the natural interval extension that fulfils the assumptions made in
Section 1: the isotonicity and property (2). In this straightforward way, to transform
a subroutine calculating a real function to the interval version, one simply has to write
a new statement to include the interval module, change the data types from real to
interval, and rename some function calls. This procedure is much simpler, quicker and
less error prone than the earlier one in FORTRAN-77, when all the operations were
transformed to function calls on new data structures. More sophisticated inclusion
functions (like in [10] or [21]) would result in better efficiency figures at the cost of
additional calculations or preliminary reformulations on the involved functions.
The inclusions for the gradients were calculated componentwise, and in this way
some of the component calculations could be skipped if the monotonicity test showed
Subdivision direction selection in interval methods for global optimization 931
that the objective function was monotonous in a variable. On the other hand, we
could not make use of the possible joint computations for many gradient components.
The code for the gradients was calculated symbolically, that is neither automatic nor
numerical differentiation was used. The effects of using alternative ways of the gradient
inclusion are the subject of a future study.
The stopping criterion parameter " was set to 0.01 in each test. The list L was
implemented as a simple array. The list was not fully ordered, the program just kept
track of the three first list members. This implementation can be efficient for short
lists, while problems of large memory complexity require data structures like the AVL-
trees or other search trees [9, 11]. The implementation of the list can affect the required
CPU time, but not the number of objective function and derivative evaluations. The
memory complexity is invariant regarding the data structure in terms of the maximal
number of items to be saved, but the size of the data structure can be decreased using
the available information [11].
The numerical tests involved the set of standard global optimization problems
(definitions in [25], further numerical results in [4, 5, 10, 23]) and the set of test
problems studied in Hansen's book (descriptions in [7], additional test results in [10,
23]). In some cases, where slight alterations were found in the problem definitions
(in the expression or in the search region), the first published versions were chosen.
The test program and the related input files can be found at ftp.jate.u-szeged.hu per
anonymous ftp in the directory /pub/math/optimization/article. Since the original
Schwefel 3.7 problem was very easy to solve, we multiplied the original objective
function by 10 4 . This change can be interpreted as solving the original problem with
These problems were completed by three new ones. The first one, called EX1 was
defined in Section 2. EX2 is a simplified real life parameter estimation problem [8, 18]:
where the f i -s are
6. The initial interval is [0:0; 1:0] 2 \Theta [1:1; 1:3] \Theta [0:0; 1:0] 2 .
EX3 is a hard global optimization problem for stochastic algorithms [4]:
otherwise. The initial box for EX3
is [\Gamma2:0; 2:0] 4 .
4.1. Numerical test results. All the test problems were solved. The problem
names in the Tables reflect the first definitions, Si stands for Shekel-i, Hi for Hartman-
i, GP for Goldstein-Price, SHCB for Six Hump Camel Back, RCOS for Branin RCOS,
RB for Rosenbrock, THCB for Three Hump Camel Back, Li for Levi No. i, and SCij
for Schwefel No. i.j.

Tables

1 to 4 contain the efficiency measures provided solving the test problems.
The second column contains the dimension of the problem, and the efficiency measures
obtained for Rules B, C and D are also expressed as percentages of the respective figure
for Rule A. In the last lines, that computational effort is shown which is necessary to
solve the whole set of test problems, or to solve the subset of 6 problems with significant
complexity (denoted by /sig. The latter subset (problems H6, GP, L3, L5 SC12 and
required about 99% of the computational burden. The percentages in these lines
show how much effort is needed with the actual rule compared to the value by Rule A.
932 T. Csendes and D. Ratz
This is the anticipated ratio of improvement (if smaller than 100%) solving a large set
of problems similar to the studied one. The average of the percentages (AoP) reflects
the relative computational burden one can expect on a single problem if the given rule
is used instead of Rule A according to the statistical information provided by the set
of test problems.

Table

1 contains the CPU time values required for the test problems with the four
direction selection rules. The standard time unit (STU, 1000 evaluations of the non-
interval Shekel-5 function) was on the used workstation 0.0036 Sec. The large CPU
times measured in STU are in part due to the interval implementation (cf. [14]) and
the overhead of the list manipulation. The CPU values are in general proportional
to the number of objective function (NFE) and derivative evaluations (NDE). The
exceptions are the cases with high memory complexity.
According to the CPU times, Rules B and C are better choices than Rules A and
D. On the basis of the numerical study made, we can expect 7% and 6% improvements,
respectively, in the computation time if we use Rule B or C instead of Rule A, while
Rule D causes about a ninefold increase. Completing a large set of problems similar
to the test problems, Rule B needs 90% less, Rule C 91% less, and Rule D about
eleven times more CPU time. For the subset of hard test problems, similar tendencies
can be seen with larger differences on individual problems. The few bigger CPU time
values for the new rules in Table 1 are basically due to the larger number of objective
function and derivative evaluations.

Table

2 shows the number of objective function evaluations necessary to solve
the test problems. In practical applications, this measure together with the number
of derivative evaluations is more important than the required CPU time, because
the computation of the involved functions are usually longer than those of the test
problems (see e.g. [15, 22]). According to the test results, 7% improvement can be
expected if Rules B or C are applied instead of Rule A, and Rule D causes 102% higher
number of function evaluations. The sum of the numbers of function evaluations (and
also that of the derivatives) must be interpreted with care, because the complexities
of the test problems are different. When a similar set of problems is to be solved, the
anticipated improvements are as high as 72% for Rule B and 74% for Rule C, while
Rule D means about five times more function evaluations. In the case of the subset
of hard test problems, the changes are \Gamma30%, \Gamma31% and +644% for a single problem,
and \Gamma72%, \Gamma74% and +426% for a similar set of problems.

Table

3 gives the number of partial derivative evaluations. As mentioned earlier,
the inclusions of the gradients were calculated componentwise, i.e. NFE multiplied by
the dimension of the problem is an upper bound on the NDE. There is a remarkable
stability in the NDE/(n NFE) values: they are between 80 and 99%, and the most
of them even lie between 85 and 95%. The only exception is the problem Schwefel
Nr. 1.2, for which this ratio is between 55 and 63%, with much larger differences
with the used direction selection rules as usual. The monotonicity test deletes those
subintervals on which the objective function proves to be monotonous, thus the ratio
of such subintervals compared to the total number of generated subintervals cannot
be high. This can be an explanation for the relative stability of the NDE/(n NFE)
values, since the number of derivative evaluations can then be less than n for the
deleted subintervals.
According to the test results, 7% improvement can be expected again if Rules B
or C are applied instead of Rule A. Rule D causes 98% more derivative evaluations.
Subdivision direction selection in interval methods for global optimization 933
When a similar set of problems is to be solved, the anticipated improvements are
as high as 75% for Rule B and 77% for Rule C, while Rule D means about three
times more derivative evaluations. In the case of the subset of hard test problems,
the respective changes are \Gamma28%, \Gamma30% and +619% for a single problem, and \Gamma75%,
\Gamma77% and +221% for a similar set of problems.

Table

4 provides the minimal list lengths necessary to solve the test problems
with the given direction selection rules. The joint space complexity of the whole set
of test problems is characterized by the maximal value for a rule. Since the results are
identical for the subset of hard problems, this line is skipped for them.
According to the test results, a list of length 68 714 is enough to solve the set of test
problems with Rule A, while the list lengths for the other rules were 13 898, 12 855
and 486 382, respectively. These mean \Gamma80%, \Gamma81% and +608% differences. The
average list length required was 2 062 with Rule A, 640 with Rule B (\Gamma69%), 616 with
Rule C (\Gamma70%), and 15 645 with Rule D (+659%). The average of the percentages
were respectively. The differences in performance on the hard
problems were similar: the average list length was 13 278 with Rule A, 4 038 with Rule
(765%). The average of
the percentages for the hard problems were 93%, 95% and 954%, respectively.
Two dominant behaviors can be recognized mainly in Tables 2 and 3, but also in
a smaller extent in Tables 1 and 4. For about half of the test problems, the differences
caused by the changing the subdivision direction selection rules are moderate. In
a smaller subset of test problems, Rule B, and especially Rule C provide a much
more efficient solution than Rule A, while Rule D is the worst in this sense. The
effects described in the previous paragraphs are even stronger for this second subset
of problems. The remaining test problems (about 10%) show various other patterns.
4.2. Statistical evaluation. We used the nonparametric Wilcoxon signed rank
test to study the effects of the algorithmic changes to the efficiency measures CPU
time, number of objective function and derivative evaluations and space complexity.
The normality test failed for each group of data (columns A, B, C and D of the Tables
The changes in the required CPU time that occurred with the substitution of Rule
A by Rules B, C and D, respectively, are greater than would be expected by chance;
there are statistically significant changes 0:012). The
differences between other pairs (e.g. Rule B vs. Rule C) are not significant. That is,
just the substitutions of Rule A cause significant changes in the CPU times.
Regarding the number of objective function evaluations, only the change due to
the padding Rule B by Rule C is not significant all the others are
significant. The same substitutions provide significant differences in the number of
derivative evaluations, and the P value for the nonsignificant case (for Rules B and
C) is 0.587. In other words, the transition inside the pair Rule B and Rule C causes
no significant difference in the NFE and NDE values, while each transition between
the other pairs provides a significant change. No subdivision rule substitution caused
a significant difference in the memory complexity.
The same statistical study was repeated for the smaller data set of the harder
problems. The only cases where statistically significant differences could be found
were the ones between Rules B and D; and between Rules C and
D in terms of the number of objective function evaluations.
934 T. Csendes and D. Ratz
5. Summary and conclusions. Compared to stochastic methods, the interval
methods for global optimization are able to provide guarantied reliability solutions -
at the cost of sometimes substantially higher computational and space complexity. The
present study aimed to investigate the possibilities to improve the efficiency while keeping
the reliability. A property of the interval subdivision rules (balanced) was defined
that ensures convergence for the studied model algorithm: both lim s!1 w(Y s
and lim s!1 F (Y s We showed that the opposite direction is also true with
some trivial exceptions. It was proved that Rules A and D are balanced, and thus
the related interval global optimization algorithms are convergent in both senses. For
some problems Rules B and C do not fulfil the requirements of balancedness, yet the
algorithms converge also in such cases to the global minimum, and the result sets are
positive width intervals the points of which are all global minimizers.
Summarizing the numerical experiences, we can conclude that Rules B, C, and
in certain cases also Rule D may be successful alternatives to Rule A. According
to our test results, Rule C is definitely the best choice as a direction selection rule,
closely followed by Rule B. The poor overall performance achieved with Rule D is
in part due to the fact that there are no huge differences in the magnitudes of the
variables in the set of test problems: neither in the initial intervals, nor in the global
minimizer point coordinates. With early recognition of the problem type, one can
save substantial amount of computational effort by using one of the latter rules. For
some problems, the application of a new rule can result in dramatic improvements in
the efficiency measures - or they can even make it possible to solve a problem due to
decreased memory complexity. Some important features of the discussed algorithmic
improvements must be highlighted again: they do not require additional information
on the problems, and they provide those improvements on a very wide problem class.



--R

Introduction to Interval Computations
On the convergence of two branch-and-bound algorithms for nonconvex programming problems
Combining real and interval methods for global optimization
Nonlinear parameter estimation by global optimization - efficiency and reliability
The impact of accelerating tools on the interval subdivision algorithm for global optimization
Numerical Toolbox for Verified Computing I.
Global optimization using interval analysis
Modeling of low-frequency pulmonary impedance in dogs
A New LP-Bound in Multivariate Lipschitz Optimiza- tion: Application to Unconstrained and Linearly Constrained Problems and to Systems of Inequalities
A global minimization method: the multi-dimensional case
Lipschitzian Optimization without the Lipschitz Constant
A FORTRAN-90 Environment for Research and Prototyping of Enclosure Algorithms for Constrained and Unconstrained Nonlinear Equations

An interval step control for continuation methods
Methodologies for tolerance intervals
Interval Analysis
Interval Methods for Systems of Equations
A. Adamicza and
Extended univariate algorithms for n-dimensional global optimization

New Computer Methods for Global Optimization

Automatische Ergebnisverifikation bei globalen Optimierungsproblemen.
Computation of Rational Interval Functions

--TR

--CTR
Allgower , Melissa Erdmann , Kurt Georg, On the complexity of exclusion algorithms for optimization, Journal of Complexity, v.18 n.2, p.573-588, June 2002
L. G. Casado , J. A. Martnez , I. Garca, Experiments with a new selection criterion in a fast interval optimization algorithm, Journal of Global Optimization, v.19 n.3, p.247-264, March 2001
Boglrka Tth , Leocadio G. Casado, Multi-dimensional pruning from the Baumann point in an Interval Global Optimization Algorithm, Journal of Global Optimization, v.38 n.2, p.215-236, June      2007
Ibraheem Alolyan, A new exclusion test for finding the global minimum, Journal of Computational and Applied Mathematics, v.200 n.2, p.491-502, March, 2007
Tibor Csendes, New Subinterval Selection Criteria for Interval Global Optimization, Journal of Global Optimization, v.19 n.3, p.307-327, March 2001
P. S. V. Nataray , K. Kotecha, An Algorithm for Global Optimization using the TaylorBernstein Form as Inclusion Function, Journal of Global Optimization, v.24 n.4, p.417-436, December 2002
P. S. Nataraj , K. Kotecha, An Improved Interval Global Optimization Algorithm Using Higher-order Inclusion Function Forms, Journal of Global Optimization, v.32 n.1, p.35-63, May       2005
U. M. Garcia-Palomares , F. J. Gonzalez-Castao , J. C. Burguillo-Rial, A Combined Global & Local Search (CGLS) Approach to Global Optimization, Journal of Global Optimization, v.34 n.3, p.409-426, March     2006
Waltraud Huyer , Arnold Neumaier, Global Optimization by Multilevel Coordinate Search, Journal of Global Optimization, v.14 n.4, p.331-355, June 1999
Mihly Csaba Markt , Tibor Csendes , Andrs Erik Csallner, Multisection in Interval Branch-and-Bound Methods for Global Optimization II. Numerical Tests, Journal of Global Optimization, v.16 n.3, p.219-228, March 2000
Jos Fernndez , Blas Pelegrn, Using Interval Analysis for Solving Planar Single-Facility Location Problems: New Discarding Tests, Journal of Global Optimization, v.19 n.1, p.61-81, January 2001
Tams Vink , Jean-Louis Lagouanelle , Tibor Csendes, A New Inclusion Function for Optimization: Kite&mdashlThe One Dimensional Case, Journal of Global Optimization, v.30 n.4, p.435-456, December  2004
Ingo Eble , Markus Neher, ACETAF: A software package for computing validated bounds for Taylor coefficients of analytic functions, ACM Transactions on Mathematical Software (TOMS), v.29 n.3, p.263-286, September
Chandra Sekhar Pedamallu , Linet zdamar , Tibor Csendes, Symbolic Interval Inference Approach for Subdivision Direction Selection in Interval Partitioning Algorithms, Journal of Global Optimization, v.37 n.2, p.177-194, February  2007
Stefan Ratschan, Search Heuristics for Box Decomposition Methods, Journal of Global Optimization, v.24 n.1, p.35-49, September 2002
Andrs Erik Csallner , Tibor Csendes , Mihly Csaba Markt, Multisection in Interval Branch-and-Bound Methods for Global Optimization  I. Theoretical Results, Journal of Global Optimization, v.16 n.4, p.371-392, April 2000
Stefan Ratschan, Efficient solving of quantified inequality constraints over the real numbers, ACM Transactions on Computational Logic (TOCL), v.7 n.4, p.723-748, October 2006
interval arithmetic;interval subdivision;global optimization