New Interval Analysis Support Functions Using Gradient Information in a Global Minimization Algorithm.
The performance of interval analysis branch-and-bound global optimization algorithms strongly depends on the efficiency of selection, bounding, elimination, division, and termination rules used in their implementation. All the information obtained during the search process has to be taken into account in order to increase algorithm efficiency, mainly when this information can be obtained and elaborated without additional cost (in comparison with traditional approaches). In this paper a new way to calculate interval analysis support functions for multiextremal univariate functions is presented. The new support functions are based on obtaining the same kind of information used in interval analysis global optimization algorithms. The new support functions enable us to develop more powerful bounding, selection, and rejection criteria and, as a consequence, to significantly accelerate the search. Numerical comparisons made on a wide set of multiextremal test functions have shown that on average the new algorithm works almost two times faster than a traditional interval analysis global optimization method.
Introduction
. In this paper the problem of nding the global minimum f  of
a real valued one-dimensional continuously dierentiable function f
and the corresponding set S  of global minimizers is considered, i.e.:
In contrast to one-dimensional local optimization problems which were very well studied
in the past, the univariate global optimization problems are in the area of interest
of many researchers now (see, for example, [1, 6, 10, 9, 11, 14, 16, 15, 17, 21, 28, 30,
32]). Such an interest is explained by existence of a large number of applications where
it is necessary to solve this kind of problems (see [2, 10, 12, 29, 30, 31]). On the other
hand, numerous approaches (see, for example, [5, 11, 13, 18, 19, 22, 23, 26, 31]) enable
to generalize to the multidimensional case methods developed to solve univariate
problems.
In those cases where the objective function f(x) is given by a formula, it is possible
to use an Interval Analysis Branch-and-Bound approach to solve the problem (1.1)
(see [13, 19, 20, 23]). A general global optimization algorithm based on this approach
is shown in Algorithm 1.
The algorithm selects the next interval to be processed (selection rule, line 3),
which can be totally or partially rejected when it is guaranteed that it does not
contain any global minimizer, (elimination rule, line 4). This elimination process is
carried out by using information obtained from the inclusion functions which return
y E-mail: leo@miro.ualm.es
z E-mail: inma@iron.ualm.es
x E-mail: jamartin@davinci.ualm.es
{ Department of Computer Architecture and Electronics, University of Almera, Spain. This work
was supported by the Ministerio de Educacion y Cultura of Spain (CICYT TIC99-0361).
k E-mail: yaro@si.deis.unical.it. ISI-CNR c/o DEIS, Universita della Calabria, 87036 Rende (CS)
Italy, and University of Nizhni Novgorod, Nizhni Novgorod, Russia.
L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV
general interval Branch-and-Bound global optimization algorithm.
Funct IGO(S; f)
1. Set the working list L := fSg and the nal list Q := fg
2. while ( L 6= fg )
3. Select an interval X from L
4. if X cannot be eliminated
5. Divide X generating
the termination criterion
7. Store X i in Q
8. else
9. Store X i in L
10. return Q
an enclosure of the real range of f(x) (and in some cases of f 0 (x) and f 00 (x)) on X
(bounding rule). If the interval cannot be rejected, it is subdivided (division rule, line
5). When the generated subintervals are informative enough, they are stored in the
nal list (termination rule, line 7). Otherwise, they are stored in the working list for
further processing (line 9). The algorithm nishes when there are no intervals to be
processed (line 2) and returns the set of intervals with valuable information (line 10).
An overview on theory and history of these rules can be found, for example, in [13].
Of course, every concrete realization of Algorithm 1 depends on the available
information about the objective function f(x). In this paper it is supposed that
inclusion functions can be evaluated for f(x) and its rst derivative f 0 (x) on X .
Thus, the information about the objective function which can be obtained during the
search is the following:
where
dened by its lower and upper bound.
inclusion function of f(x) at X obtained by
Interval Arithmetic. For the real range of f(x) over X the following inclusion
inclusion of the function f(x) at a point x 2 X .
inclusion function of f 0 (x) over X .
When information (1.2) is available, the rules of a traditional realization of Algorithm
1 can be written more precise. Below we present a Traditional Interval
analysis global minimization Algorithm with Monotonicity test (TIAM) which is used
frequently for solving the problem (1.1) using the information (1.2) (see [13]).
Selection rule: Among all the intervals X i stored in the working list L select an
interval X such that
Bounding rule: The fundamental Theorem of Interval Arithmetic provides a natural
and rigorous way to compute an inclusion function. In the present study
the inclusion function F of the objective function f is available by Extended
Interval Arithmetic (see [7, 13]).
Elimination rule: The common elimination rules are the following:
Midpoint test: An interval X is rejected when F (X) > f~, where f~ is the
best known upper bound of f  . The value of f~ is updated by evaluating
F (m(X)) in selected intervals, where is the midpoint
of the interval X .
Cut-o test: When f~ is improved, all intervals X stored in the working
and nal lists satisfying the condition F (X) > f~ are rejected.
Monotonicity test: If for an interval X the condition
then this means that the interval X does not contain any minimum and,
therefore, can be rejected.
Division rule: Usually two subintervals are generated using m(X) as the subdivision
point (bisection).
Termination rule: A parameter  determines the desired accuracy of the problem
solution. Therefore, intervals X that have a width w(X) less than , i.e.,
are moved to the nal list Q. Other termination
criteria can be found in [23].
As can be seen from the above description, the algorithm evaluates lower bounds
for f(x) over every interval separately, without taking into consideration information
which can be obtained from other intervals. F 0 (X) is used only during the Monotonicity
test and is not connected with the information F (m(X)) and F (X). Only F (X)
is used in order to obtain a lower bound for f(x) over X , all the rest of the search
information is not used for this goal. The only exchange of information between the
intervals is done through f~.
In Lipschitz global optimization there exist algorithms for solving problem (1.1)
evaluating lower bounds by constructing support functions (in fact, F (X) can be
viewed as a special support function { constant { for f(x) over X) for the objective
function too (see, for example, [6, 10, 11, 17, 18, 21, 22, 27, 28, 30, 31]). They work
in a way similar to the TIAM support functions are built and successively
improved in order to obtain a better lower bound for the global minimum. Of course,
these support functions are completely dierent and are built on the basis of dierent
ideas. An interesting aspect of the support function concept in the context of this
paper is the use of the search information. When a support function is built for an
interval [a; b], the information regarding neighbors [c; a] and [b; d] is also used in order
to construct a better support function and to obtain a better lower bound for f  .
In this paper, a new Interval analysis global minimization Algorithm using Gradient
information (IAG) is proposed for solving problem (1.1). It uses the same information
(1.2) as TIAM but, due to a more e-cient usage of the search information,
constructs support functions which are closer to the objective function and enables
to obtain better lower bounds. As it will be shown hereinafter, the new method IAG
has a quite promising performance in comparison with the traditional TIAM.
The rest of the paper is structured as follows. In Section 2 some theoretical results
explaining construction of the support functions and lower bounds are presented.
The algorithm IAG is described in Section 3. Numerical experiments comparing
performance of TIAM and IAG are presented in Section 4. Finally, Section 5 concludes
the paper.
2. New support functions based on interval evaluations of the objective
function and its rst derivative. In order to proceed with the description of
the new algorithm, theoretical results are presented to explain how the new support
functions and the corresponding lower bounds are constructed in IAG. We start with
the following lemma illustrated in Figure 2.1, in a similar way as was done for non-
4 L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV
__
__
__
__
F(c)
f ~
Fig. 2.1. Graphical example of Lemma 2.1 and Theorem 2.2
dierentiable functions in both, Lipschitz optimization (see [9, 11, 18, 21, 22, 28, 30,
31]) and approaches based on evaluation of slopes as presented in [24].
Lemma 2.1. Given a continuously dierentiable function f
a closed interval in R, an interval X  S, an enclosure F (c) of f(c), c 2 X, and an
enclosure then the following bounds hold for f(x); x 2 X:
Proof. It follows from Mean Value Theorem that there exists a point  2 [x; c]
such that
By extending the equation (2.2) to intervals the following inclusion
is obtained. Let us take a generic point x 2 X . In dependence on the mutual
disposition of the points c and x in X , three results can be deduced from (2.3):
Lemma is proved.
This Lemma gives us a possibility to construct a new interval analysis support
function for f(x). It can be seen from Figure 2.1 that it is similar to that ones built
in Lipschitz global optimization (see, for example, [10, 21, 22, 27, 31]). The Lipschitz
support functions are piece-wise linear. The slope of each linear piece is L or L,
where L is the Lipschitz constant. In our approach, for every interval X the slopes
of support functions are equal to F 0 (X) for all x  c and to F 0 (X) for all x  c (see

Figure

2.1).
The following results are the basics for the new support functions and explain
how the new lower bounds for f  are evaluated.
Theorem 2.2. Given closed intervals X;S such that X  S  R and a continuously
dierentiable function f R. Let for a point c 2 X a lower bound lb(c) of
f(c) be determined and an enclosure F 0 (X) of f 0 (X) be obtained. For a given current
upper bound f~ of f  , there exists a set V  X where all the global minimizers of X,
if any, are included.
Proof. For a minimizer point x  2 S  it applies that f(x  )  f~. Combining with
Lemma 2.1 a minimizer x  2 X \ S  has to fulll:
and therefore can only be located in set:
f~
From Theorem 2.2 it can be derived that if f~ < lb(c) then
can be constructed as:
As an example, depicted in Figure 2.1 for the case F 0 (X) > 0
Notice that V can be obtained in a similar way by applying the interval Newton
operator to nd the roots of the function f(x) f~ on X , under the Theorem conditions
[8, 19, 20].
Theorem 2.3. Let us consider a continuously dierentiable function f
where S is a closed interval in R and intervals X; Y such that X  Y  S. If:
6 L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV
f ~
__
G
__
G
__
__
Fig. 2.2. Interval V is the region which can contain global minimizers. The set XnV does not
contain any global minimizer.
1. lower bounds lb(x) and lb(x) of, respectively, f(x) and f(x), have been evaluated

2. a current upper bound f~ of f  is such that
f~  minflb(x); lb(x)g;
3. bounds
Then only the interval
G
can contain global minimizers and a lower bound z(X; lb(x); lb(x); G) of f(x) over the
interval X can be calculated as follows:
(see Figure 2.2).
Proof. By applying Theorem 2.2 with x the interval V 2 from (2.7) is obtained.
The same operation with the point us the interval V 1 from (2.6). Then,
the interval V from (2.8) is obtained as
Let us prove now the formula (2.9). Since X  Y , F
applying the Mean Value Theorem, we have
and
From these two inequalities follows
so
and
which proves the theorem.
Corollary 2.4. If for an interval X the inequality z(X; lb(x); lb(x); G) > f~ is
fullled then it can be derived that X does not contain any global minimizer.
Proof. Proof is evident and so it is omitted.
Let us return now to the problem (1.1). We can use the information (1.2) during
the global search. Thus, by using F (X) together with the function d(x) from (2.10)
we can build a new support function D(x) for f(x) over each interval
The corresponding new lower bound F z(X) for f(x) over the interval X is calculated
in the following way
Essential in the use of the algorithm is that for obtained from set
X according to (2.8) the current value of f~ is a lower bound of f at v and v; i.e.
f~  f(v) and f~  f(v), so are easily available bounds.
3. Description of the new algorithm. On the basis of theoretical results
presented in the previous section we can determine new rules for Algorithm 1 in
order to introduce the new Interval analysis global minimization Algorithm using
Gradient information (IAG) described in Algorithm 2:
Selection rule: Select an interval X such that
where L is the working list ordered by non-decreasing values of F z(X i ) as
the rst ordering criterion and non-increasing order with respect to the age of
the intervals as the second ordering criterion. Therefore, the selected interval
will always be at the head of the working list.
Bounding rule: The lower bound F z(X) from (2.12) is used.
Elimination rule: Four elimination rules are used:
Monotonicity test: If for an interval X the condition
then this means that the interval X does not contain any minimum and,
therefore, can be rejected.
RangeUp test: An interval X is rejected if f~ < F z(X).
Gradient test: The subregion fXnV g, where V is dened by (2.8), is
rejected. Of course, when the whole interval X can be eliminated.
Cut-o test: When f~ is improved, all intervals X stored in the working
and nal lists for which the condition F z(X) > f~ is fullled are rejected.
Note, that this Cut-o test is dierent from the Cut-o test of TIAM
where the condition F (X) > f~ was used.
Division rule: Suppose that an interval X has been obtained as a result of application
of RangeUp and Gradient tests to an interval Y and then stored
in the working list L. If the interval X is chosen for subdivision, the point
m(X) is used as the subdivision point. Note, that in general m(X) 6= m(Y )
and therefore this division rule does not coincide with the division rule of the
TIAM algorithm.
8 L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV
Algorithm 2 Interval analysis global minimization Algorithm using Gradient information
Funct
1.
2. if ( F
3. x~ := s; f~ := F
4. else
5. x~ := s; f~ := F
Test
7. return (f
8.
9. X := GradTest (
10. lb(x) := lb(x) := f^(X) := f~
11. F z(X) := maxfF (X); z(X; lb(x); lb(x); F 0 (S))g Lower bound of f(X)
12. if ( w(X)   )
13. Save fX; f^(X); F z(X)g in Q
14. else
15. Save fX; f^(X); F z(X)g in L
16. while ( L 6= fg )
17. fX; f^(X); F z(X)g := Head(L)
18. comment X :=
19. if (0 2 F 0 (X)) Monotonicity Test
20. if
21. f~ := F (m(X))
22. CutOTest ( f~;
25.
26. for i := 1,2
GradTest
28.
29. if ( w(X fully rejected
test
33. Save fX
34. else
35. Save fX
36. return Q
Every element X i in the working and nal lists, L and Q, respectively, is a structure
with the following data:
Bounds x i and x i of the interval X i .
The value being the value of f~ at the moment of creation of the
The lower bound F z(X i ).
Let us comment Algorithm 2. The IAG algorithm starts by evaluating F (s) and
F (line 2) and initializing x~ and 5). If the monotonicity
SUPPORT FUNCTIONS USING GRADIENT INFORMATION 9
Algorithm 3 Gradient test
Funct GradTest(X; lb(x); lb(x); f~; G)
1. if ( lb(x) > f~ )
2.
3.
4. if ( w(X) > 0 and lb(x) > f~ )
5.
7. return X
__
_
_
__
__
__
__
f ~
_
f ~
__
__
__ __
Fig. 3.1. The upper graph is an example of the initial phase of IAG. Bottom graphs show
an example of how the intervals X1 and X2 are built from X. The bottom left hand graph shows
the case F (m(X)) > f~ and the bottom right hand f~ < minflb(x); lb(x)g. Only shaded areas can
contain f  .
test is satised (line 6), the algorithm nishes and the solution is given by ff~; x~g.
Otherwise, in order to apply the Gradient test, lb(s) and lb(s) are initialized in line 8.
The Gradient test is implemented in the GradTest procedure presented in Algorithm
3 which is applied to S on line 9. The GradTest procedure applies Theorems 2.2 and
2.3 to S, using returns an interval X  S, such that the set
of global minimizers of S are also in X . Lower bounds of f(x) and f(x) (lb(x) and
lb(x), respectively) and f^(X) are set to f~ and F z(X) is computed (lines 10 and 11).
The interval X is stored in the nal list Q (line 13) or in the working list L (line 15),
depending on the value of w(X). Graphically, this initialization stage is shown in the
top graph of Figure 3.1.
L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV
After this initialization stage and while the list L is not empty (line 16), IAG
will select the interval at the head of L (line 17) for further processing. If F 0 (X)
does not satisfy the Monotonicity test (line 19), F (m(X)) is evaluated (line 20). If
F (m(X)) is a better upper bound of f  than f~, f~ is updated to F (m(X)) (line
21) and the Cut-o test is applied to the intervals in the working and nal lists (line
22). Then, the interval X is subdivided into two subintervals X 1 and X 2 (line 23).
These subintervals inherit from X the lower bound of f(x) in one of their bounds (line
24) and the other shared bound is set to F (m(X)) (line 25). For each subinterval
the Gradient test is carried out using the derivative information of X
(line 27) instead of the value of F 0 (X i ) which has not been evaluated 1 . If an interval
2g is not rejected (line 29), F z(X i ) is evaluated using also the value of
Only when the RangeUp test is not satised (line 31), the interval
will be saved in the nal (line 33) or working lists (line 35).
Bottom graphs of Figure 3.1 show how the intervals X 1 and X 2 are built from
X . In case of F (m(X)) > f~ (see lower left hand graph), interval X 1 and X 2 can
be shortened by applying the GradTest procedure. In addition, if f~ < lb(x) and/or
f~ < lb(x) (see lower right hand graph of Figure 3.1), X 1 and/or X 2 can be shortened
again by the GradTest procedure. Notice that in the IAG algorithm, if f~ < lb(x)
then f~ < lb(x), too, and vice versa.
4. Numerical results. The new algorithm IAG has been numerically compared
with the method TIAM on a set of 40 test functions. This set of test functions is
described in Table 4.1 and has been taken from [3, 4, 24]. The search region and
the number of local and global minimizers are shown for all the functions. For both
algorithms the stopping criterion was

Table

4.2 shows numerical comparison between TIAM and IAG. Column NFE
presents the number of Interval Function Evaluations, i.e., the number of F (X) evaluations
plus the number of interval point evaluations F (x). Column NDE shows
the number of Interval Function Evaluations of the derivative F 0 (X). Columns TM
and present NFE +NDE for algorithms TIAM and IAG, respectively. Finally,
column TM=TG provides information of the relative speedup of the IAG algorithm
compared to TIAM algorithm.
The last row of Table 4.2 shows the average values of data at columns TG, TM ,
and TM=TG. It can be seen from Table 4.2 that the ratio TM=TG is always greater
than one, so IAG outperforms TIAM for all the functions. For this set of functions
the speedup TM=TG ranges between [1:22; 6:98] and in average is 1:78. It can also
be seen from Table 4.2 that for those functions where TIAM needs a lot of function
evaluations the largest values of TM=TG were obtained (see functions
which obtained speed up of 4:56 and 6:98, respectively).

Figures

4.1 and 4.2 graphically show how algorithms TIAM and IAG work. The
function presented in Figure 4.1 has only one global minimizer while the
function has two global minimizers. In both gures the left hand
graph refers to algorithm TIAM while right hand graphs depict the performance
of algorithm IAG. For all the graphs the termination criterion was w(X)  0:05.
1 Evaluation of these values will become crucial only for that interval which is chosen later
for subdivision. By using the derivative information of X we avoid additional computations of
which can be useless if the interval will never be chosen for subdivision.

Table
Description of the test functions. Column N shows the number of the function, S the initial
search interval, column M presents the number of local minimizers, and G shows the number of
global minimizers.
Function
26 e sin(3x) [0:2; 7:0] 5 3
28 sin(x) [0; 20] 4 3
29 2(x
Horizontal arrows represent the values of f~ during the execution. Boxes represent
the margins of all the evaluated intervals X and the lower and upper bounds of F (X).
For the IAG algorithm, the new support function d(x) from (2.10) is also shown.
At the top of the graphs, colored boxes represent the set of rejected intervals as
well as intervals which contain a global minimizer. The color of a box species the
criterion responsible for the rejection of that interval (Blue = GradTest procedure,
midpoint and cut-o tests for TIAM and RangeUp
and cut-o tests for IAG, Yellow = Boxes in the nal list Q). From these graphs is
easy to realize how e-cient every rejection criterion is.
L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV

Table
Results of numerical comparison between TIAM and IAG.
9 156 115 41 101 76 25 1.54
28 1.42
28 1.51
14
22 284 209 75 178 132 46 1.6
26 336 268 68 271 214 57 1.24
28 366 292 74 261 206 55 1.40
34 636 460 176 350 259 91 1.82
36 982 711 271 445 331 114 2.21
772.1 282.33 1.78

Figures

4.1 and 4.2 show that for these examples more than 50% of the initial
interval S was rejected due to the GradTest procedure. It is also clearly shown that
TIAM had to evaluate more intervals than IAG. Figure 4.2 shows some intervals
where the best lower bound of f(X) was that obtained by the computation of z(X)
instead of F (X), i.e., that F It should be noticed also that
the TIAM algorithm is unable to take advantage of the information provided by the
evaluation of F (m(X)) when F (m(X)) > f~. In contrast, IAG is able to reduce the
interval even in this case (clearly shown in Figures 4.1 and 4.2).
5. A brief conclusion. In this paper a new way to calculate support functions
for multiextremal univariate functions has been presented. The new support functions
are based on the usual information used in global optimization working with Interval
Analysis: interval evaluations of the objective function at a point, at an interval, and
interval evaluation of the rst derivative of the objective function at an interval, i.e.,
F (x); F (X), and F 0 (X).
Traditional interval analysis global optimization algorithms use this information
Fig. 4.1. Graphical representation for the execution of TIAM (left hand graph) and IAG (right
hand graph) algorithms for function
Fig. 4.2. Graphical representation for the execution of TIAM (left hand graph) and IAG (right
hand graph) algorithms for function
separately: F (x) is used to obtain an upper bound for the global minimum, F (X) is
used to determine a support function { being a constant { for the objective function
nally, F 0 (X) is used in the Monotonicity test for rejecting intervals
which do not contain global minimizers. In contrast, the new method uses the
whole information jointly in order to construct a support function which is closer to
the objective function. The new support function enables to develop more powerful
rejection and bounding criteria and to accelerate the search signicantly. In fact, the
new algorithm works almost two times faster in comparison with a traditional interval
analysis method on a wide set of multiextremal test functions.
The new approach has several possibilities for generalization. First, interval analysis
bounds for F 0 (X) can be substituted by other estimates (for example, slope tools
developed in [25] for non-smooth problems) in order to obtain new support functions.
Second, the new method can be generalized to the multi-dimensional case by diago-
14 L.G. CASADO, I. GARCIA, J.A. MARTINEZ AND YA.D. SERGEYEV
nal approach proposed in [22] or by using adaptively constructed space-lling curves
proposed in [26].

Acknowledgement

. The authors would like to thank E.M.T. Hendrix for his
useful remarks and suggestions.



--R



An algorithm for

State of the Art in Global Optimization.
A global search algorithm using derivatives

Global Optimization Using Interval Analysis
Global optimization of univariate lipschitz functions: 1.

Handbook of Global Optimization
Guaranteed ray intersections with implicit surfaces
Continuous Problems
A method for converting a class of univariate functions into d.
A bridging method for global optimization
An adaptive stochastic global optimization algorithm for one-dimensional functions
Equivalent methods for global optimization
Convergence rates of a global optimization algorithm
Interval analysis
Interval Methods for Systems of Equations
An algorithm for

New computer methods for global optimization
Automatic Slope Computation and its Application in Nonsmooth Global Optimiza- tion




Two methods for solving optimization problems arising in electronic measurement and electrical engineering
Numerical Methods on Multiextremal Problems
Global optimization with non-convex constraints: Sequential and parallel algorithms
An improved univariate global optimization algorithm with improved linear bounding functions
--TR

--CTR
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
interval arithmetic;global optimization;branch-and-bound