\documentclass[11pt,a4]{article}
%
\usepackage{endnotes}
\usepackage{natbib}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{color}
\usepackage{indentfirst}
%

\usepackage{a4wide,portland,lscape}
\newcommand{\ds}{\displaystyle}
\parindent 1em
%% COMMENT FOR DOUBLE SPACE LINE
\renewcommand{\baselinestretch}{2}

%
\begin{document}
\definecolor{dgreen}{rgb}{0,0.5,0}
\definecolor{weblink}{rgb}{0.3,0.0,0.9}
\title{Stopping Rules for Box-Constrained \\ 
       Stochastic Global Optimization }
\author{I. E. Lagaris\thanks{Corresponding author. Email: lagaris@cs.uoi.gr} 
\ and I. G. Tsoulos \\
Department of Computer Science,  University of Ioannina \\
P.O.Box 1186, Ioannina  45110 -- GREECE}
\date{}
\maketitle
\begin{abstract}
We present three new stopping rules for {\it Multistart} based methods.
The first uses a device that enables the determination of the 
coverage of the bounded search domain.
The second is based on the comparison of asymptotic expectation values 
of observable quantities to the actually measured ones.
The third offers a probabilistic estimate for  the number of local minima inside
the search domain.
We report comparative results of the application of these rules on a host
of test problems in the framework of two stochastic global optimization methods.
\end{abstract}
{\bf Keywords: }{\it Stochastic Global optimization, Multistart, Stopping rules.}

%
%\newpage
\section{Introduction}
The task of locating all the local minima of a continuous function inside 
a box-bounded domain, is frequently required in several scientific as well as 
practical problems. We will not dwell further on this, instead we refer to
the article by \citet{Panos}. 
The problem we are interested in, may be described as:
\begin{eqnarray}
%%REVIEWER1: p.2
\hbox{Given an objective function }f(x),\ x\in S \subset R^n, \hbox{ find all its local minimizers } 
x^{*}_i\in S.
%\nonumber
%\hbox{Find all }  x^*_i \in S \subset R^n \hbox{ that satisfy:\ \ \ \  }\\
% x^*_i =\arg \min_{x \in S_i} f(x), \hbox{\ \ } S_i = S\cap\{x,|x-x_i^*| < \epsilon\}
\label{FAM}
\end{eqnarray}
$ S $ will be considered herein to be a rectangular hyperbox in $ N $ dimensions.
We limit our consideration to problems with a finite number of local minima. This is a convenient hypothesis as far as the
implementation is concerned. We are interested in stochastic methods based
on {\it Multistart}, a brief review of which follows. 
\subsubsection*{The Multistart Algorithm} 
\newcounter{step}
\begin{list}
{Step--\thestep:}{\usecounter{step} \addtocounter{step}{-1}}
\item
 Set $i = 0$ and $ X^* = \emptyset$
\item  
Sample $x$ at random from $S$
\item  
Apply a deterministic local search procedure ($\mbox{LS}$)  starting at $x$ and concluding
at a local minimum $x^*$.
\item Check if a new minimum is discovered \\
If $x^* \notin X^*$ then \\
\hbox{\ \ \ \ }  increment: $i \leftarrow i+1 $\\
\hbox{\ \ \ \ }    set: $x_i^* = x^*$ \\
\hbox{\ \ \ \ }   add: $ X^* \leftarrow X^*\cup \{x^*_i\} $\\
Endif 
\item
If a stopping rule applies, STOP
\item
Go to Step-1
\end{list}
%
%
Good stopping rules are important and should combine reliability and economy.
A reliable rule is one that stops only when all minima have been
collected with certainty. An economical rule is one that does not 
spend a huge number of local searches to detect that all minima
have been found. 
%
The {\bf ``region of attraction''} or the {\bf ``basin''} of a local minimum 
associated with a deterministic local search procedure $\mbox{LS}$ is defined as:
\begin{equation}
A_i \equiv \{x: x\in S, \mbox{LS}(x)=x^*_i\}
\end{equation}
where $\mbox{LS}(x)$ is the minimizer returned when the local search procedure $\mbox{LS}$ is 
started at point $x$.
If $S$ contains a total of  $w$ local minima,  from the definition above follows:
\begin{equation}
 \cup_{i=1}^wA_i = S   \label{closure}
\end{equation}
Let  $m(A)$ indicate the {\it Lebesgue measure} of $A \subseteq R^{n}$. 
Since the regions of attraction for deterministic local searches do not overlap, i.e.  
$ A_i \cap A_j = \emptyset \hbox{ for } \ i\ne j$,  then from eq. (\ref{closure})
one obtains:
\begin{equation}
m(S) = \sum_{i=1}^{w} m(A_i)
\end{equation}
If a point in $ S $ is sampled from a uniform distribution, the apriori probability
$ \pi_i$ that it is contained in $ A_i$ is given by 
$ \pi_i = \frac{m(A_i)}{m(S)}$.
If $K$ points are sampled from $ S $, the apriori  probability that at least one point
is contained in $ A_i $ is given  by:
\begin{equation}
1 - \left(1-\frac{m(A_i)}{m(S)}\right)^K = 1 -(1-\pi_i)^K
\end{equation}
From the above we infer that for large enough $ K $, this probability tends to
one, i.e. it becomes ``asymptotically certain'' that at least one sampled 
point will be found to belong to $A_i$. This holds $ \forall A_i, 
\hbox{ with } m(A_i) \ne 0 $. \\
The main disadvantage of {\it Multistart\ } is that the local search may be initiated 
from points belonging to the same basin of attraction, leading to the discovery
of the same minimizer over and over, wasting computational resources.
A way of curing that, would be to design algorithms capable of recognizing if a point
belongs to the basin of an already found minimizer and hence avoid 
starting a local search from there.  This however can be achieved only within 
a probabilistic framework, since otherwise it would mean the apriori knowledge of 
the different regions of attraction.
In this line the clustering approach aims to form clusters of points that belong to the same 
region of attraction and then start a local search from only one point of each cluster.
%
Several stopping rules have been developed in the past, most of them
based on Bayesian considerations (\citet{Ziel,Kan,Betro,Romeijn}) and they
have been successfully used in practical applications.  A review that analyzes the
topic of stopping rules is given by $T\ddot{o}rn$ and $\check{Z}ilinskas$ in their book (\citet{ToZil}).
We refer also to Hart (\citet{Hart}) noting however
that his stopping rules aim to terminate the search as soon as possible once the global 
minimum is found and they are not designed for the retrieval of all the local minima.
We present three different stopping rules. In section~\ref{DBSR}, a rule that
relies on a coverage argument is presented. In section~\ref{OBSE}, a rule
based on the comparison of asymptotic to measured values of observable quantities
is developed, and in section~\ref{EXMI}, a probabilistic approach is employed to 
estimate the expected number of minimizers.
We report in section~\ref{COEX}, results of numerical experiments in conjunction
with 2 of the  {\it Multistart} based methods.
%
%
\section{The Double-Box Stopping Rule \label{DBSR}}
This termination rule is tightly coupled to the sampling scheme. In the conducted experiments
we need to know the uncovered portion of the search domain in order to prevent the local search
procedure from performing unnecessary computations. A relative measure for the region that remains uncovered
is given by: 
\begin{equation}
	U=1-\sum_{i=1}^{w}\frac{m(A_i)}{m(S)}
	\label{eq:us1}
\end{equation}
where $w$ is the number of the discovered
so far local minima. The quantity $\frac{m(A_i)}{m(S)}$ can
be approximated asymptotically by the fraction $\frac{L_i}{L}$ where $L_i$ is the number of local searches that have
ended up to the local minimum $x_i^{*}$ and $L$ is the total number of performed local searches. An approximation 
for $U$ may then be given by:
\begin{equation}
	U\simeq\tilde{U}=1-\sum_{i=1}^{w}\frac{L_i}{L}
	\label{eq:tildeus1}
\end{equation}
Unfortunately in every iteration 
the quantity $\sum_{i=1}^{w}\frac{L_i}{L}$ has the value of 1, and as a consequence the uncovered space
can not be estimated with the above procedure. 
A larger box $ S_2$ is constructed that  contains $S$ and such that 
$m(S_2) = 2 \times m(S)$. We consider that a unique (fake) local minimum is located in $A_0=S_2-S$. 
The volume of the region of attraction of the fake minimum is $m(A_0)=m(S)$. Hence we obtain:
\begin{equation}
	U=1-\frac{\sum_{i=0}^{w}m(A_i)}{m(S_2)}=1-\frac{m(A_0)}{m(S_2)}-\frac{\sum_{i=1}^{w}m(A_i)}{m(S_2)}=\frac{1}{2}-\frac{\sum_{i=1}^{w}m(A_i)}{m(S_2)}
\end{equation}
The quantity $\frac{m(A_i)}{m(S_2)}$ is approximated again by the fraction $\frac{L_i}{L}$, where now $L$ stands for 
the total number of local searches started in $S_2$ and hence $U$ may be approximated by:
\begin{equation}
	U\simeq\tilde{U}=\frac{1}{2}-\sum_{i=1}^{w}\frac{L_i}{L}
\end{equation}

At every iteration, $N$ points in $S$ are collected,
by sampling uniformly from $S_2$ and rejecting points not contained in $S$. 
(Note that for  {\it Multistart} $N=1$).
After $k$ iterations, let the accumulated number of points sampled from $S_2$ 
be $M_k$, $kN$ of which are contained in $S$.
The quantity then: $\delta_k \equiv \frac{k N}{M_k}$
has an expectation value $<\delta>_{k} = \frac{1}{k}\sum_{i=1}^k \delta_i $
that asymptotically, i.e. for large $k$, tends to $\frac{m(S)}{m(S_2)}=\frac{1}{2}$.
The variance is given by $\sigma_{k}^2(\delta) = <\delta^2>_{k}-<\delta>_{k}^2$ tends to zero
as $k \rightarrow \infty$. 
\begin{figure}
\caption{Plots of  $<\delta>_k-\frac{1}{2}$ and  $\sigma_{k}^2({\delta})$ versus $k$ }
\label{deltavalue}
\includegraphics{all_delta.eps}
\end{figure}
This is a smoother quantity than $<\delta>_k$ (see figure \ref{deltavalue} ) and hence better suited for 
 a termination criterion.
We permit iterating without
finding new minima until $\sigma^2(\delta) < p\sigma^2_{last}(\delta)$, 
where $\sigma_{last}(\delta)$ is
the standard deviation at the iteration during which the most recent minimum was found and $p\in(0,1)$, a  parameter
that controls the compromise between an exhaustive search $(p\rightarrow 0)$ and a search optimized for speed 
$(p\rightarrow 1)$. 
\begin{table}
\caption{Multistart with Double Box rule for a set of $p$-values.}
\label{expwithp}
\begin{center}\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline 
&
\multicolumn{2}{c|}{$p=0.3$}&
\multicolumn{2}{c|}{$p=0.5$}&
\multicolumn{2}{c|}{$p=0.7$}&
\multicolumn{2}{c|}{$p=0.9$}\tabularnewline
\hline
\hline 
FUNCTION&
MIN&
FC&
MIN&
FC&
MIN&
FC&
MIN&
FC\tabularnewline
\hline 
SHUBERT&
400&
1150243&
400&
577738&
400&
322447&
395&
139768\tabularnewline
\hline 
GKLS(3,30)&
30&
961269&
29&
302583&
23&
41026&
15&
3920\tabularnewline
\hline 
RASTRIGIN&
49&
50384&
49&
19593&
49&
13581&
49&
10034\tabularnewline
\hline 
Test2N(5)&
32&
78090&
32&
30607&
32&
20870&
32&
13462\tabularnewline
\hline 
Test2N(6)&
64&
85380&
64&
34840&
64&
22535&
64&
15393\tabularnewline
\hline 
Guilin(20,100)&
100&
3405112&
100&
1906288&
100&
854511&
71&
79331\tabularnewline
\hline 
Shekel10&
10&
93666&
10&
36838&
10&
23780&
10&
15976\tabularnewline
\hline
\end{tabular}\end{center}
\end{table}

In table \ref{expwithp} we list the results from the application of the double box termination rule and the
Multistart method in a series of test problems for different values of the parameter $p$. As $p$ increases
the method becomes faster, but some local minima may not be found. The suggested value for general use is $p=0.5$.
Hence the algorithm may be stated as :
\begin{enumerate}
\item Initially set $\alpha = 0$
\item Sample $N$ points as described above.
\item Calculate $\sigma^2(\delta)$
\item Apply an iteration of a {\it Multistart}--like algorithm, neglecting its first step 
      and using instead the $N$ points already sampled. 
\item If a new minimum is found, set: $\alpha = p\sigma^2(\delta)$ and 
      repeat from step 2.
\item STOP if $\sigma^2(\delta) <\alpha$, otherwise repeat from step 2.
\end{enumerate}
%
%
\section{The Observables Stopping Rule \label{OBSE}}
We have developed  a scheme based on probabilistic estimates 
for the number of times each of the minima is being rediscovered by the local search.
Let $ L_1, L_2, \cdots, L_w$ be the number of local searches that
end--up to the local minima $x_1^*,x_2^*, \cdots, x_w^*$ that are indexed
in order of their appearance. Let $m(A_1), m(A_2), \cdots, m(A_w) $ be the measures
of the corresponding regions of attraction, and let $m(S)$, be the measure
of the bounded domain $ S $. 
$x_1^*$  is discovered for the first time with one application of the local search.
Let  $n_2$ be the number of the subsequent applications of the local search procedure 
spent, until  $x_2^*$  is discovered for the first time.
Similarly denote by $n_3, n_4, \cdots, n_w $ the incremental  number of
local search applications to discover $x_3^*, x_4^*, \cdots, x_w^*$.
Considering the above and taking into account that we sample points 
using a uniform distribution, the expected number $L^{(w)}_J$ of local search applications
that have ended--up to $ x_J^* $ at the time when the $w^{th}$ minimum is 
discovered for the first time, is given by:
\begin{equation}
\label{LJ}
L^{(w)}_J = L^{(w-1)}_J + (n_w -1)\frac{m(A_J)}{m(S)}.
\end{equation}
The apriori probability that a local search procedure starting from a point
sampled at random, concludes to the local minimum $x_J^*$ is given by the ratio
$m(A_J)/m(S)$,  while the posteriori 
probability (observed frequency) is correspondingly given by $ L_J/\sum_{i=1}^w L_i  $.
On the asymptotic limit the posteriori reaches the apriori probability, 
which implies $ m(A_i)/m(A_j) = L_i/L_j $, which in turn
permits substituting in eq. (\ref{LJ})  $L_i$ in place of $m(A_i)$ leading to:
\begin{eqnarray}
\nonumber
L^{(w)}_J &=& L^{(w-1)}_J + (n_w -1)\frac{L_J}{\sum_{i=1}^{w}L_i} \\
          &=& L^{(w-1)}_J + (n_w -1)\frac{L_J}{\sum_{i=1}^{w}n_i}
\end{eqnarray}
with $ n_1=1,\ \ J \le w-1$ and $L^{(w)}_w =1$.
Now consider that after having found $w$ minima, an additional number of
$K$ local searches are performed without discovering any new minima.
We denote by  ${\mathcal  L}^{(w)}_J(K)$ the expected number of times 
the $J^{th}$ minimum is found at that moment.
One readily obtains: 
\begin{equation}
%{\mathcal  L}^{(w)}_J(K) = L^{(w)}_J + K\frac{L_J}{K+\sum_{i=1}^{w}n_i}
{\mathcal  L}^{(w)}_J(K) = {\mathcal L}^{(w)}_J(K-1) + \frac{L_J}{K+\sum_{i=1}^{w}n_i}
\end{equation}
with ${\mathcal L}^{(w)}_J(0)=L^{(w)}_J $. \\
The quantity 
\begin{equation}
 E_2(w,K) \equiv \frac{1}{w}\sum_{J=1}^w \left( \frac{{\mathcal  L}^{(w)}_J(K)-L_J}{\sum_{l=1}^w L_l} \right)^2
\end{equation}
tends to zero asymptotically, hence  a criterion based on the variance $\sigma^2(E_2)$  may be stated as: \\
{\bf  Stop if} $ \sigma^2(E_2) < p\sigma^2_{last}(E_2)$ \\
where $\sigma^2_{last}(E_2)$ is the variance of $E_2$ calculated at the time 
when the last minimum was retrieved. The value of the parameter $p$ has the same justification as in  
the  Double Box rule and the suggested value is again $p=0.5$, although the user may choose to modify it according to his
needs.
%
%
\section{The Expected Minimizers Stopping Rule \label{EXMI}}
This technique is based on estimating the expected number of existing
minima of the objective function in the specified domain. The search stops
when the number of recovered minima, matches this estimate.
Note that the estimate is updated iteratively as the algorithm proceeds.
Let  $\ds P^{l}_{m} $ denote the probability that after $\ds m $ draws,
$\ds l $ minima have been discovered.
Here by ``draw'' we mean the application of a local search, initiated from a 
point sampled from the uniform distribution.
Let also $\ds \pi_{k} $ denote the probability that
with a single draw the minimum located at  $\ds x^*_k $ is found.
This probability is apriori equal to $\ds \pi_k =\frac{m(A_k)}{m(S)}$.
The $P^l_m $ probability can be recursively calculated by:
\begin{equation}
P^l_m =\left(1-\sum_{i=1}^{l-1}\pi_i\right)P^{l-1}_{m-1} + \left(\sum_{i=1}^l\pi_i\right)P^l_{m-1}
\label{prob}
\end{equation}
Note that $\ds P^0_1=0, \ \hbox{and } P^1_1=1$.
Also $P^l_m = 0 \hbox{ if } l > m$, $P^0_m = 0, \ \forall m \ge 1 $.
The rational for the derivation of eq. (\ref{prob}) is as follows.
The probability that at the $\ds m^{th} $ draw $\ds l $ minima are recovered,
is connected with the probabilities at the level of the  $\ds (m-1)^{th} $ draw,
that either $\ds l-1 $ minima are found (and the $l^{th}$ is found at the next, 
i.e. the $\ds m^{th}$, draw) or $\ds l $ minima are found (and no new minimum
is found at the $\ds m^{th} $ draw).
The quantity $ \sum_{i=1}^l\pi_i $ is the probability that one of the 
$\ds l$ minima is found in a single draw, likewise the quantity 
$ 1-\sum_{i=1}^{l-1}\pi_i $ is the probability that none of the $ l-1$ minima
is found in a single draw. 
Combining these observations the recursion above is readily verified.
Since $P^l_m $ denote probabilities they ought obey the closure:
\begin{equation}
\sum_{l=1}^{m}P^{l}_{m} = 1.
\end{equation}
To prove the above let us define the quantity $s_l = \sum_{i=1}^{l}\pi_i $.
Perform a summation over $l$ on both sides of eq. (\ref{prob}) and obtain:
\begin{equation}
\sum_{l=1}^{m}P^l_m = \sum_{l=1}^{m}P^{l-1}_{m-1} -\sum_{l=1}^{m}s_{l-1}P^{l-1}_{m-1}
 +\sum_{l=1}^{m}s_{l}P^{l}_{m-1} \label{sum}
\end{equation}
Note that since $P^0_{m-1}=0$ and $P^m_{m-1}=0$ the last  two sums in eq. (\ref{sum})
cancel, and hence we get: $\sum_{l=1}^{m}P^{l}_{m} = \sum_{l=1}^{m-1}P^{l}_{m-1}$. 
This step can be repeated to show that
$$
\sum_{l=1}^{m}P_{m}^{l}=\sum_{l=1}^{m-1}P_{m-1}^{l}=\ldots = 
\sum_{l=1}^{m-k}P_{m-k}^{l}=\sum_{l=1}^{1}P_{1}^{l}=P_{1}^{1}=1
$$
The expected number of minima after $m$ draws is then given by:
$$ <L>_m \equiv \sum_{l=1}^m l P^l_m  $$
and its variance by:
\begin{equation}
\sigma^2(L)_m = \sum_{l=1}^m l^2 P^l_m -\left(\sum_{l=1}^m l P^l_m\right)^2  
\label{eq:variance}
\end{equation}
The quantities $\pi_i$ are unknown apriori and need to be estimated. Naturally the
estimation will improve as the number of draws grows. A plausible estimate 
$\pi_i^{(m)}$ for approximating  $\pi_i$ after $m$ draws, may be given by:
\begin{equation}
\pi_i^{(m)} \equiv \frac{L_i^{(m)}}{m} \rightarrow \frac{m(A_i)}{m(S)}=\pi_i
\end{equation}
where $L_i^{(m)}$ is the number of times the minimizer
$x^*_i$ is found after $m$ draws. Hence eq. (\ref{prob}) is modified and reads:
\begin{equation}
P^l_m =\left(1-\sum_{i=1}^{l-1}\pi_i^{(m-1)}\right)P^{l-1}_{m-1} + \left(\sum_{i=1}^l\pi_i^{(m-1)}\right)P^l_{m-1}
\end{equation}
%When $<L>_m\  \le w +\frac{1}{2}$, $w$ being the number of recovered minima, the algorithm terminates.
The expectation $<L>_m$ tends to $w$ asymptotically. Hence a criterion based on
the variance $\sigma^2(L)_m$, that asymptotically tends to zero, may be proper. Consequently,
the rule may be stated as:
{\bf Stop if} $\sigma^2(L)_m < p\sigma^2(L)_{last}$,  
where again $\sigma^2(L)_{last} $ is the variance at the time when the last minimum was found and
the parameter $p$ is used in the same manner as before. The suggested value for $p$ is again $p=0.5$.
%
%
\section{Computational Experiments \label{COEX}}
We compare the new stopping rules proposed in the present article to three established rules that have been 
successfully used in a host of applications. 
 If by $w$ we denote the number of recovered local minima after having performed $t$ local search procedures,
then the estimate of the fraction of the uncovered space is given by (\citet{Ziel}):
\begin{equation}
	P(w)=\frac{w(w+1)}{t(t-1)}.
\end{equation}
The corresponding rule is then:
\begin{equation}
	\hbox{Stop when } P(w)\le\epsilon
	\label{stoppcov}
\end{equation}
$\epsilon$ being a small positive number. In our experiments we used $\epsilon=0.001$.
\citet{Kan} showed that the estimated number of local minima is given by:
\begin{equation}
	w_{\mbox{est}}=\frac{w(t-1)}{t-w-2}
\end{equation}
and the associated rule becomes:
\begin{equation}
	\hbox{Stop when } w_{\mbox{est}}-w\le\frac{1}{2}
	\label{stopkan}
\end{equation}
In another rule (\citet{Romeijn}) the probability that all local minima have been observed is given by:
\begin{equation}
	\prod_{i=1}^{w}\left(\frac{t-1-i}{t-1+i}\right)
\end{equation}
leading to the rule:
\begin{equation}
	\hbox{Stop when } \prod_{i=1}^{w}\left(\frac{t-1-i}{t-1+i}\right)>\tau
	\label{stopmult}
\end{equation}
$\tau$ tends to 1 from below.
\\

Every experiment represents 100 runs, each with different seed for the random number generator. The local search procedure
used is a BFGS version due to Powell (\citet{Powell}). We report the average number of the local minima recovered, as well
as the mean number of functional evaluations. In tables \ref{multresults} and \ref{tmlresults} results are presented
for two global optimization methods, namely Multistart and TMLSL (\citet{Ali}).  We used a set of 21 test functions that 
cover a wide spectrum of cases, i.e. functions of lower or higher dimensionality, with a few or with many local minima,
with narrow or wide basins of attraction etc. These test functions are described in the appendix in an effort to make the
article as self contained as possible. Columns labeled as FUNCTION, MIN, FC list the function name, the number of 
recovered minimizers and the number of function calls. The labels PCOV and KAN refer to the stopping rules given in 
equations  (\ref{stoppcov}) and (\ref{stopkan}), while the labels DOUBLE, OBS and EXPM to the proposed rules in an 
obvious correspondence.
 Experiments have indicated that the rule in equation (\ref{stopmult}) is rather impractical, as can be readily verified
by inspecting tables \ref{multistart-mult} and \ref{tml-mult}. Note the excessive number of function calls even for
$\tau=0.7$ (a value that is too low) and also the premature termination for $\tau=0.8$ in the case of TMLSL (table \ref{tml-mult}). Hence this rule is not included in tables \ref{multresults} and \ref{tmlresults}, where the complete 
set of the test functions is used. As we can observe from tables \ref{multresults} and \ref{tmlresults} the new rules
in most cases perform better, requiring fewer functional evaluations. However in the case of functions such as CAMEL,
GOLDSTEIN, SHEKEL, HARTMAN, where only a few minima exist,  the rules PCOV and KAN have a small advantage. Among the new rules
there is not a clear winner, although EXPM seems to perform marginally better than the other two in terms of function
evaluations. The rule DOUBLE seems to be more exhaustive and retrieves in the case of Multistart a greater number of 
minimizers, while for TMLSL this is evened out.
%%%%
\begin{table}

\caption{Multistart with eq. (\ref{stopmult}) rule. \label{multistart-mult}}

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
&
\multicolumn{2}{c|}{$\tau$=0.7}&
\multicolumn{2}{c|}{$\tau$=0.8}&
\multicolumn{2}{c|}{$\tau$=0.9}\tabularnewline
\hline
\hline 
FUNCTION&
MIN&
FC&
MIN&
FC&
MIN&
FC\tabularnewline
\hline 
RASTRIGIN&
49&
168103&
49&
268721&
49&
568843\tabularnewline
\hline 
SHUBERT&
400&
11248711&
400&
17983401&
400&
38083156\tabularnewline
\hline 
GKLS(3,30)&
18&
10615&
24&
27910&
28&
77326\tabularnewline
\hline 
GUILIN(10,200)&
200&
6627109&
200&
10589110&
200&
22429999\tabularnewline
\hline
\end{tabular}
\end{table}
%
\begin{table}

\caption{TMLSL with eq. (\ref{stopmult}) rule. \label{tml-mult}}

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
&
\multicolumn{2}{c|}{$\tau$=0.7}&
\multicolumn{2}{c|}{$\tau$=0.8}&
\multicolumn{2}{c|}{$\tau$=0.9}\tabularnewline
\hline
\hline 
FUNCTION&
MIN&
FC&
MIN&
FC&
MIN&
FC\tabularnewline
\hline 
RASTRIGIN&
32&
7273&
46&
21954&
49&
58984\tabularnewline
\hline 
SHUBERT&
369&
502570&
400&
874785&
400&
1855688\tabularnewline
\hline 
GKLS(3,30)&
7&
751&
10&
1906&
23&
14753\tabularnewline
\hline 
GUILIN(10,200)&
199&
2501449&
200&
4029885&
200&
8580472\tabularnewline
\hline
\end{tabular}
\end{table}


%
\begin{table}
\caption{Multistart}
\label{multresults}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
&
\multicolumn{2}{c|}{\textbf{\scriptsize PCOV}}&
\multicolumn{2}{c|}{\textbf{\scriptsize KAN}}&
\multicolumn{2}{c|}{\textbf{\scriptsize DOUBLE}}&
\multicolumn{2}{c|}{\textbf{\scriptsize OBS}}&
\multicolumn{2}{c|}{\textbf{\scriptsize EXPM}}\tabularnewline
\hline
\hline 
\textbf{\scriptsize FUNCTION}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}\tabularnewline
\hline 
{\scriptsize CAMEL}&
{\scriptsize 6}&
{\scriptsize 5642}&
{\scriptsize 6}&
{\scriptsize 2549}&
{\scriptsize 6}&
{\scriptsize 5503}&
{\scriptsize 6}&
{\scriptsize 2720}&
{\scriptsize 6}&
{\scriptsize 2916}\tabularnewline
\hline 
{\scriptsize RASTRIGIN}&
{\scriptsize 49}&
{\scriptsize 38104}&
{\scriptsize 49}&
{\scriptsize 121182}&
{\scriptsize 49}&
{\scriptsize 19593}&
{\scriptsize 49}&
{\scriptsize 13342}&
{\scriptsize 49}&
{\scriptsize 9007}\tabularnewline
\hline 
{\scriptsize SHUBERT}&
{\scriptsize 400}&
{\scriptsize 316640}&
{\scriptsize 400}&
{\scriptsize 8034563}&
{\scriptsize 400}&
{\scriptsize 577738}&
{\scriptsize 400}&
{\scriptsize 369958}&
{\scriptsize 400}&
{\scriptsize 212353}\tabularnewline
\hline 
{\scriptsize HANSEN}&
{\scriptsize 527}&
{\scriptsize 426056}&
{\scriptsize 527}&
{\scriptsize 14220225}&
{\scriptsize 527}&
{\scriptsize 612015}&
{\scriptsize 527}&
{\scriptsize 391597}&
{\scriptsize 527}&
{\scriptsize 240092}\tabularnewline
\hline 
{\scriptsize GRIEWANK2}&
{\scriptsize 528}&
{\scriptsize 565932}&
{\scriptsize 529}&
{\scriptsize 18941546}&
{\scriptsize 529}&
{\scriptsize 1765175}&
{\scriptsize 528}&
{\scriptsize 996188}&
{\scriptsize 527}&
{\scriptsize 449090}\tabularnewline
\hline 
{\scriptsize GKLS(3,30)}&
{\scriptsize 16}&
{\scriptsize 5286}&
{\scriptsize 13}&
{\scriptsize 4249}&
{\scriptsize 29}&
{\scriptsize 302853}&
{\scriptsize 23}&
{\scriptsize 84291}&
{\scriptsize 25}&
{\scriptsize 96260}\tabularnewline
\hline 
{\scriptsize GKLS(3,100)}&
{\scriptsize 34}&
{\scriptsize 11464}&
{\scriptsize 61}&
{\scriptsize 97124}&
{\scriptsize 97}&
{\scriptsize 7492103}&
{\scriptsize 94}&
{\scriptsize 5658721}&
{\scriptsize 92}&
{\scriptsize 3416276}\tabularnewline
\hline 
{\scriptsize GKLS(4,100)}&
{\scriptsize 20}&
{\scriptsize 6010}&
{\scriptsize 12}&
{\scriptsize 7816}&
{\scriptsize 95}&
{\scriptsize 8629052}&
{\scriptsize 73}&
{\scriptsize 5290564}&
{\scriptsize 93}&
{\scriptsize 6358587}\tabularnewline
\hline 
{\scriptsize GUILIN(10,200)}&
{\scriptsize 191}&
{\scriptsize 354650}&
{\scriptsize 200}&
{\scriptsize 4736609}&
{\scriptsize 200}&
{\scriptsize 3351391}&
{\scriptsize 200}&
{\scriptsize 2178890}&
{\scriptsize 199}&
{\scriptsize 1136783}\tabularnewline
\hline 
{\scriptsize GUILIN(20,100)}&
{\scriptsize 96}&
{\scriptsize 263869}&
{\scriptsize 100}&
{\scriptsize 1760826}&
{\scriptsize 100}&
{\scriptsize 1906288}&
{\scriptsize 100}&
{\scriptsize 973307}&
{\scriptsize 99}&
{\scriptsize 655374}\tabularnewline
\hline 
{\scriptsize Test2N(4)}&
{\scriptsize 16}&
{\scriptsize 17373}&
{\scriptsize 16}&
{\scriptsize 18716}&
{\scriptsize 16}&
{\scriptsize 19424}&
{\scriptsize 16}&
{\scriptsize 5296}&
{\scriptsize 16}&
{\scriptsize 3970}\tabularnewline
\hline 
{\scriptsize Test2N(5)}&
{\scriptsize 32}&
{\scriptsize 37639}&
{\scriptsize 32}&
{\scriptsize 78931}&
{\scriptsize 32}&
{\scriptsize 30607}&
{\scriptsize 32}&
{\scriptsize 10700}&
{\scriptsize 32}&
{\scriptsize 7707}\tabularnewline
\hline 
{\scriptsize Test2n(6)}&
{\scriptsize 64}&
{\scriptsize 81893}&
{\scriptsize 64}&
{\scriptsize 336353}&
{\scriptsize 64}&
{\scriptsize 34840}&
{\scriptsize 64}&
{\scriptsize 27679}&
{\scriptsize 64}&
{\scriptsize 18367}\tabularnewline
\hline 
{\scriptsize Test2n(7)}&
{\scriptsize 128}&
{\scriptsize 175850}&
{\scriptsize 128}&
{\scriptsize 1435579}&
{\scriptsize 128}&
{\scriptsize 117953}&
{\scriptsize 128}&
{\scriptsize 70370}&
{\scriptsize 128}&
{\scriptsize 41981}\tabularnewline
\hline 
{\scriptsize GOLDSTEIN}&
{\scriptsize 4}&
{\scriptsize 5906}&
{\scriptsize 4}&
{\scriptsize 3812}&
{\scriptsize 4}&
{\scriptsize 5391}&
{\scriptsize 4}&
{\scriptsize 3842}&
{\scriptsize 4}&
{\scriptsize 3850}\tabularnewline
\hline 
{\scriptsize BRANIN}&
{\scriptsize 3}&
{\scriptsize 2173}&
{\scriptsize 3}&
{\scriptsize 1782}&
{\scriptsize 3}&
{\scriptsize 1856}&
{\scriptsize 3}&
{\scriptsize 1782}&
{\scriptsize 3}&
{\scriptsize 1782}\tabularnewline
\hline 
{\scriptsize HARTMAN3}&
{\scriptsize 3}&
{\scriptsize 3348}&
{\scriptsize 3}&
{\scriptsize 2750}&
{\scriptsize 3}&
{\scriptsize 3509}&
{\scriptsize 3}&
{\scriptsize 2778}&
{\scriptsize 3}&
{\scriptsize 2772}\tabularnewline
\hline 
{\scriptsize HARTMAN6}&
{\scriptsize 2}&
{\scriptsize 3919}&
{\scriptsize 2}&
{\scriptsize 3851}&
{\scriptsize 2}&
{\scriptsize 3903}&
{\scriptsize 2}&
{\scriptsize 3907}&
{\scriptsize 2}&
{\scriptsize 3851}\tabularnewline
\hline 
{\scriptsize SHEKEL5}&
{\scriptsize 5}&
{\scriptsize 8720}&
{\scriptsize 5}&
{\scriptsize 4733}&
{\scriptsize 5}&
{\scriptsize 22128}&
{\scriptsize 5}&
{\scriptsize 6430}&
{\scriptsize 5}&
{\scriptsize 8850}\tabularnewline
\hline 
{\scriptsize SHEKEL7}&
{\scriptsize 7}&
{\scriptsize 11742}&
{\scriptsize 6}&
{\scriptsize 5485}&
{\scriptsize 7}&
{\scriptsize 30702}&
{\scriptsize 7}&
{\scriptsize 7581}&
{\scriptsize 7}&
{\scriptsize 10914}\tabularnewline
\hline 
{\scriptsize SHEKEL10}&
{\scriptsize 10}&
{\scriptsize 16020}&
{\scriptsize 10}&
{\scriptsize 10611}&
{\scriptsize 10}&
{\scriptsize 36838}&
{\scriptsize 9}&
{\scriptsize 9812}&
{\scriptsize 10}&
{\scriptsize 12751}\tabularnewline
\hline
\end{tabular}
\end{table}
\thispagestyle{empty}


\begin{table}

\caption{TMLSL}
\label{tmlresults}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
&
\multicolumn{2}{c|}{\textbf{\scriptsize PCOV}}&
\multicolumn{2}{c|}{\textbf{\scriptsize KAN}}&
\multicolumn{2}{c|}{\textbf{\scriptsize DOUBLE}}&
\multicolumn{2}{c|}{\textbf{\scriptsize OBS}}&
\multicolumn{2}{c|}{\textbf{\scriptsize EXPM}}\tabularnewline
\hline
\hline 
\textbf{\scriptsize FUNCTION}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}&
\textbf{\scriptsize MIN}&
\textbf{\scriptsize FC}\tabularnewline
\hline 
{\scriptsize CAMEL}&
{\scriptsize 4}&
{\scriptsize 406}&
{\scriptsize 4}&
{\scriptsize 404}&
{\scriptsize 6}&
{\scriptsize 3415}&
{\scriptsize 6}&
{\scriptsize 7325}&
{\scriptsize 6}&
{\scriptsize 1815}\tabularnewline
\hline 
{\scriptsize RASTRIGIN}&
{\scriptsize 31}&
{\scriptsize 1821}&
{\scriptsize 15}&
{\scriptsize 1614}&
{\scriptsize 49}&
{\scriptsize 24123}&
{\scriptsize 49}&
{\scriptsize 12815}&
{\scriptsize 49}&
{\scriptsize 9199}\tabularnewline
\hline 
{\scriptsize SHUBERT}&
{\scriptsize 52}&
{\scriptsize 2971}&
{\scriptsize 236}&
{\scriptsize 226048}&
{\scriptsize 400}&
{\scriptsize 358623}&
{\scriptsize 400}&
{\scriptsize 321031}&
{\scriptsize 400}&
{\scriptsize 275773}\tabularnewline
\hline 
{\scriptsize HANSEN}&
{\scriptsize 66}&
{\scriptsize 3837}&
{\scriptsize 361}&
{\scriptsize 451662}&
{\scriptsize 527}&
{\scriptsize 811679}&
{\scriptsize 527}&
{\scriptsize 781209}&
{\scriptsize 527}&
{\scriptsize 501844}\tabularnewline
\hline 
{\scriptsize GRIEWANK2}&
{\scriptsize 295}&
{\scriptsize 56348}&
{\scriptsize 48}&
{\scriptsize 298174}&
{\scriptsize 528}&
{\scriptsize 1929165}&
{\scriptsize 527}&
{\scriptsize 1602467}&
{\scriptsize 526}&
{\scriptsize 591899}\tabularnewline
\hline 
{\scriptsize GKLS(3,30)}&
{\scriptsize 8}&
{\scriptsize 908}&
{\scriptsize 7}&
{\scriptsize 624}&
{\scriptsize 28}&
{\scriptsize 191867}&
{\scriptsize 28}&
{\scriptsize 364849}&
{\scriptsize 29}&
{\scriptsize 483227}\tabularnewline
\hline 
{\scriptsize GKLS(3,100)}&
{\scriptsize 10}&
{\scriptsize 1171}&
{\scriptsize 7}&
{\scriptsize 727}&
{\scriptsize 91}&
{\scriptsize 6683608}&
{\scriptsize 90}&
{\scriptsize 2535356}&
{\scriptsize 98}&
{\scriptsize 32034155}\tabularnewline
\hline 
{\scriptsize GKLS(4,100)}&
{\scriptsize 2}&
{\scriptsize 310}&
{\scriptsize 2}&
{\scriptsize 310}&
{\scriptsize 78}&
{\scriptsize 12269342}&
{\scriptsize 72}&
{\scriptsize 11199668}&
{\scriptsize 93}&
{\scriptsize 70398347}\tabularnewline
\hline 
{\scriptsize GUILIN(10,200)}&
{\scriptsize 139}&
{\scriptsize 76928}&
{\scriptsize 181}&
{\scriptsize 1600657}&
{\scriptsize 200}&
{\scriptsize 3470206}&
{\scriptsize 200}&
{\scriptsize 2650971}&
{\scriptsize 199}&
{\scriptsize 1752886}\tabularnewline
\hline 
{\scriptsize GUILIN(20,100)}&
{\scriptsize 74}&
{\scriptsize 72794}&
{\scriptsize 99}&
{\scriptsize 734645}&
{\scriptsize 100}&
{\scriptsize 1915478}&
{\scriptsize 100}&
{\scriptsize 1333144}&
{\scriptsize 99}&
{\scriptsize 867312}\tabularnewline
\hline 
{\scriptsize Test2N(4)}&
{\scriptsize 12}&
{\scriptsize 874}&
{\scriptsize 8}&
{\scriptsize 508}&
{\scriptsize 16}&
{\scriptsize 3821}&
{\scriptsize 16}&
{\scriptsize 2807}&
{\scriptsize 16}&
{\scriptsize 4162}\tabularnewline
\hline 
{\scriptsize Test2N(5)}&
{\scriptsize 32}&
{\scriptsize 3798}&
{\scriptsize 32}&
{\scriptsize 7750}&
{\scriptsize 32}&
{\scriptsize 8953}&
{\scriptsize 32}&
{\scriptsize 6634}&
{\scriptsize 32}&
{\scriptsize 6092}\tabularnewline
\hline 
{\scriptsize Test2N(6)}&
{\scriptsize 20}&
{\scriptsize 1513}&
{\scriptsize 11}&
{\scriptsize 1184}&
{\scriptsize 64}&
{\scriptsize 54555}&
{\scriptsize 64}&
{\scriptsize 34649}&
{\scriptsize 64}&
{\scriptsize 27500}\tabularnewline
\hline 
{\scriptsize Test2N(7)}&
{\scriptsize 104}&
{\scriptsize 10776}&
{\scriptsize 128}&
{\scriptsize 73947}&
{\scriptsize 128}&
{\scriptsize 88750}&
{\scriptsize 128}&
{\scriptsize 69371}&
{\scriptsize 128}&
{\scriptsize 52248}\tabularnewline
\hline 
{\scriptsize GOLDSTEIN}&
{\scriptsize 4}&
{\scriptsize 583}&
{\scriptsize 3}&
{\scriptsize 587}&
{\scriptsize 4}&
{\scriptsize 4606}&
{\scriptsize 4}&
{\scriptsize 11709}&
{\scriptsize 4}&
{\scriptsize 2522}\tabularnewline
\hline 
{\scriptsize BRANIN}&
{\scriptsize 3}&
{\scriptsize 354}&
{\scriptsize 3}&
{\scriptsize 359}&
{\scriptsize 3}&
{\scriptsize 1007}&
{\scriptsize 3}&
{\scriptsize 182919}&
{\scriptsize 3}&
{\scriptsize 1227}\tabularnewline
\hline 
{\scriptsize HARTMAN3}&
{\scriptsize 3}&
{\scriptsize 1567}&
{\scriptsize 3}&
{\scriptsize 1567}&
{\scriptsize 3}&
{\scriptsize 2014}&
{\scriptsize 3}&
{\scriptsize 18271}&
{\scriptsize 3}&
{\scriptsize 3857}\tabularnewline
\hline 
{\scriptsize HARTMAN6}&
{\scriptsize 2}&
{\scriptsize 685}&
{\scriptsize 2}&
{\scriptsize 677}&
{\scriptsize 2}&
{\scriptsize 912}&
{\scriptsize 2}&
{\scriptsize 87124}&
{\scriptsize 2}&
{\scriptsize 2094}\tabularnewline
\hline 
{\scriptsize SHEKEL5}&
{\scriptsize 4}&
{\scriptsize 446}&
{\scriptsize 4}&
{\scriptsize 446}&
{\scriptsize 5}&
{\scriptsize 6434}&
{\scriptsize 5}&
{\scriptsize 90356}&
{\scriptsize 5}&
{\scriptsize 3310}\tabularnewline
\hline 
{\scriptsize SHEKEL7}&
{\scriptsize 4}&
{\scriptsize 436}&
{\scriptsize 4}&
{\scriptsize 434}&
{\scriptsize 6}&
{\scriptsize 14617}&
{\scriptsize 7}&
{\scriptsize 161969}&
{\scriptsize 6}&
{\scriptsize 4363}\tabularnewline
\hline 
{\scriptsize SHEKEL10}&
{\scriptsize 5}&
{\scriptsize 412}&
{\scriptsize 5}&
{\scriptsize 406}&
{\scriptsize 9}&
{\scriptsize 18447}&
{\scriptsize 10}&
{\scriptsize 78645}&
{\scriptsize 9}&
{\scriptsize 10288}\tabularnewline
\hline
\end{tabular}
\end{table}


\section{Conclusions}
We presented three new stopping rules for use in conjunction with
{\it Multistart}--based methods for global optimization.
These rules, although quite different in nature, perform similarly
and significantly better than other rules that have been widely used in practice. 
The comparison does not render a clear winner among them, 
hence the one that is more conveniently 
integrated with the global optimization method of choice may be used.
Efficient stopping rules are important especially for problems where the number of
minima is large and the objective function expensive. Such problems occur
frequently in molecular physics, chemistry and biology where the interest is
in collecting stable molecular conformations that correspond to
local minimizers of the steric energy function (\citet{Wiberg, Saunders1, Saunders2}). 
Devising new rules and adapting the present ones to other stochastic global 
optimization methods is within our interests and currently under investigation.
\pagebreak
\appendix
\section{Test Functions}
We list the test functions used in our experiments,
the associated search domains and the number of the existing local minima.
\begin{enumerate}
\item {\bf Rastrigin}. \\
$\ds f(x)= x_1^2 + x_2^2 -cos(18x_1)-cos(18x_2)$ \\
$x \in [-1,1]^2$ with 49 local minima.
\item {\bf Shubert}.\\
$\ds f(x) = -\sum_{i=1}^{2}\sum_{j=1}^{5}j\{ sin[(j+1)x_i]+1\}$\\
$x \in [-10,10]^2$ with 400 local minima.
\item {\bf GKLS}. \\
$f(x)=Gkls(x,n,w)$, is a function
with $w$ local minima, described in \citet{Gav}.\\
$ x \in [-1,1]^n, n \in [2,100] $.  In our experiments we considered the following cases:

\begin{enumerate}
\item $n=3,\  w=30$.
\item $n=3,\  w=100$.
\item $n=4,\  w=100$.
\end{enumerate}

\item {\bf Guilin Hills}. \\
$\ds f(x) = 3+
\sum_{i=1}^{n}c_i\frac{x_i+9}{x_i+10}sin\left(\frac{\pi}{1-x_i+1/(2k_i)}\right)$\\
$x \in [0,1]^n $, 
$c_i>0, \hbox{\ and }  k_i \hbox{\ are positive integers}$.
This function has $\prod_{i=1}^{n}k_i $ minima.
In our experiments we chose $n=10$  and $n=20$ and arranged $k_i$ so that the number of minima is 200 and
100 respectively.
\item {\bf Griewank \# 2}. \\
$\ds f(x)=1+\frac{1}{200}\sum_{i=1}^{2}x_i^2 -\prod_{i=1}^{2}\frac{cos(x_i)}{\sqrt(i)}$\\
$ x \in [-100,100]^2$ with 529 minima.
\item {\bf Hansen}. \\
$\ds f(x)=\sum_{i=1}^{5}i \cos[(i-1)x_1+i] \sum_{j=1}^{5}j \cos[(j+1)x_2+j]$ \\
$ x \in [-10,10]^2$ with 527 minima.
\item {\bf Camel}. \\
$\ds f(x)=4x_1^2-2.1x_1^4+\frac{1}{3}x_1^6+x_1x_2-4x_2^2+4x_2^4$\\
$ x \in [-5,5]^2$ with 6 minima.
\item {\bf Test2N}.\\
\[
f(x)=\frac{1}{2}\sum_{i=1}^{n}x_{i}^{4}-16x_{i}^{2}+5x_{i}\]
with $x\in[-5,5]^{n}$. The function has $2^{n}$ local minima in the
specified range. In our experiments we have used the values $n=4,5,6,7$.
These cases are denoted by Test2N(4), Test2N(5), Test2N(6) and Test2N(7)
respectively.

\item {\bf Branin}.\\
$f(x)=\left(x_{2}-\frac{5.1}{4\pi^{2}}x_{1}^{2}+\frac{5}{\pi}x_{1}-6\right)^{2}+10\left(1-\frac{1}{8\pi}\right)\cos(x_{1})+10$
with $-5\le x_{1}\le10,\ 0\le x_{2}\le15$. The function has 3 minima
in the specified range.
\item{\bf Goldstein \& Price}\\
\begin{eqnarray*}
f(x) & = & [1+(x_{1}+x_{2}+1)^{2}\\
 &  & (19-14x_{1}+3x_{1}^{2}-14x_{2}+6x_{1}x_{2}+3x_{2}^{2})]\times\\
 &  & [30+(2x_{1}-3x_{2})^{2}\\
 &  & (18-32x_{1}+12x_{1}^{2}+48x_{2}-36x_{1}x_{2}+27x_{2}^{2})]\end{eqnarray*}
The function has 4 local minima in the range $[-2,2]^{2}$.
\item {\bf Hartman3}\\

\[
f(x)=-\sum_{i=1}^{4}c_{i}\exp\left(-\sum_{j=1}^{3}a_{ij}\left(x_{j}-p_{ij}\right)^{2}\right)\]
with $x\in[0,1]^{3}$ and \[
a=\left(\begin{array}{ccc}
3 & 10 & 30\\
0.1 & 10 & 35\\
3 & 10 & 30\\
0.1 & 10 & 35\end{array}\right)\]
and \[
c=\left(\begin{array}{c}
1\\
1.2\\
3\\
3.2\end{array}\right)\]
and\[
p=\left(\begin{array}{ccc}
0.3689 & 0.117 & 0.2673\\
0.4699 & 0.4387 & 0.747\\
0.1091 & 0.8732 & 0.5547\\
0.03815 & 0.5743 & 0.8828\end{array}\right)\]
The function has 3 minima in the specified range.


\item {\bf Hartman6}\\

\[
f(x)=-\sum_{i=1}^{4}c_{i}\exp\left(-\sum_{j=1}^{6}a_{ij}\left(x_{j}-p_{ij}\right)^{2}\right)\]
with $x\in[0,1]^{6}$ and \[
a=\left(\begin{array}{cccccc}
10 & 3 & 17 & 3.5 & 1.7 & 8\\
0.05 & 10 & 17 & 0.1 & 8 & 14\\
3 & 3.5 & 1.7 & 10 & 17 & 8\\
17 & 8 & 0.05 & 10 & 0.1 & 14\end{array}\right)\]
and\[
c=\left(\begin{array}{c}
1\\
1.2\\
3\\
3.2\end{array}\right)\]
and

\[
p=\left(\begin{array}{cccccc}
0.1312 & 0.1696 & 0.5569 & 0.0124 & 0.8283 & 0.5886\\
0.2329 & 0.4135 & 0.8307 & 0.3736 & 0.1004 & 0.9991\\
0.2348 & 0.1451 & 0.3522 & 0.2883 & 0.3047 & 0.6650\\
0.4047 & 0.8828 & 0.8732 & 0.5743 & 0.1091 & 0.0381\end{array}\right)\]
The function has 2 local minima in the specified range.

\item {\bf Shekel-5}.\\

\[
f(x)=-\sum_{i=1}^{5}\frac{1}{(x-a_{i})(x-a_{i})^{T}+c_{i}}\]
 with $x\in[0,10]^{4}$ and \[
a=\left(\begin{array}{cccc}
4 & 4 & 4 & 4\\
1 & 1 & 1 & 1\\
8 & 8 & 8 & 8\\
6 & 6 & 6 & 6\\
3 & 7 & 3 & 7\end{array}\right)\]
and \[
c=\left(\begin{array}{c}
0.1\\
0.2\\
0.2\\
0.4\\
0.4\end{array}\right)\]
The function has 5 local minima in the specified range.

\item {\bf Shekel-7}.\\

\[
f(x)=-\sum_{i=1}^{7}\frac{1}{(x-a_{i})(x-a_{i})^{T}+c_{i}}\]
 with $x\in[0,10]^{4}$ and \[
a=\left(\begin{array}{cccc}
4 & 4 & 4 & 4\\
1 & 1 & 1 & 1\\
8 & 8 & 8 & 8\\
6 & 6 & 6 & 6\\
3 & 7 & 3 & 7\\
2 & 9 & 2 & 9\\
5 & 3 & 5 & 3\end{array}\right)\]
and \[
c=\left(\begin{array}{c}
0.1\\
0.2\\
0.2\\
0.4\\
0.4\\
0.6\\
0.3\end{array}\right)\]
The function has 7 local minima in the specified range.


\item {\bf Shekel-10}.\\
$\ds f(x)=-\sum_{i=1}^m\left( \frac{1}{(x-A_i)(x-A_i)^T+c_i}\right)$\\
where:
$
  m=10, 
  A=\left[\begin{tabular}{cccc} 
  4&4&4&4\\ 
  1&1&1&1\\
  8&8&8&8\\
  6&6&6&6\\
  3&7&3&7\\
  2&9&2&9\\
  5&5&3&3\\
  8&1&8&1\\
  6&2&6&2\\
  7&3.6&7&3.6\\
  \end{tabular}\right]
  \ 
  c=\left[\begin{tabular}{c}
  0.1\\
  0.2\\
  0.2\\
  0.4\\
  0.4\\
  0.6\\
  0.3\\
  0.7\\
  0.5\\
  0.5\\
  \end{tabular}\right]
$\\
$ x \in [0,10]^4$ with 10 minima.
\end{enumerate}
%
\newpage
\begin{thebibliography}{}

\bibitem[Powell(1989)] {Powell} Powell, M.J.D. (1989) {\it A Tolerant Algorithm for Linearly Constrained
Optimization Calculations}, Mathematical Programming {\bf 45},
547.
\bibitem[Hart(1998)] {Hart} Hart, W.E. (1998) {\it Sequential stopping rules for random optimization methods
	with applications to multistart local search}, Siam J. Optim. {\bf 9}, 270-290.
\bibitem[$T\ddot{o}rn$ and $\check{Z}ilinskas$ (1987)] {ToZil} $T\ddot{o}rn$ A. and 
	$\check{Z}ilinskas$ A. (1987),{\it Global Optimization, volume 350 of Lecture Notes in Computer Science}, Springer, Heidelberg.
\bibitem[Ali and Storey(1994)]	{Ali} Ali, M.M. and Storey, C.(1994),
                {\it Topographical Multilevel Single Linkage},
                Journal of Global Optimization {\bf 5}, 349-358.
\bibitem[Betr\`{o} and Schoen (1992)] 
                {Betro} Betr\`{o} B., Schoen F. (1992),
                {\it Optimal and sub-optimal stopping rules for the Multistart 
                 algorithm in global optimization},
                Mathematical Programming {\bf 57}, 445-458
\bibitem[Boender and Rinnooy Kan (1987)]
                {Kan}   Boender C.G.E., Kan  Rinnooy  A.H.G. (1987),
                {\it Bayesian stopping rules for multistart global optimization methods},
                 Mathematical Programming {\bf 37}, 59-80 
\bibitem[Boender and Romeijn (1995)]
                {Romeijn} Boender C.G.E. and Romeijn Edwin H. (1995),
                {\it Stochastic Methods}, in {\it Handbook of Global Optimization}
                (Horst, R. and Pardalos, P. M. eds.), Kluwer, Dordrecht, 829-871
\bibitem[Gaviano et al (2003)]{Gav}   
                Gaviano, M. and  Ksasov, D.E. and Lera, D.  and  Sergeyev, Y.D.(2003),
                {\it Software for generation of classes of test functions
                with known local and global minima for global optimization},
                ACM Trans. Math. Softw. {\bf 29}, 469-480
\bibitem[Pardalos et al (2000)]
                {Panos} Pardalos Panos M., Romeijn Edwin H., Tuy Hoang (2000),
                {\it Recent developments and trends in global optimization},
                Journal of Computational and Applied Mathematics {\bf 124}, 209-228
\bibitem[Zieli\'{n}ski (1981)]
                {Ziel}  Zieli\'{n}ski   Ryszard (1981),
                {\it A statistical estimate of the structure of multiextremal problems},
                Mathematical Programming {\bf 21}, 348-356
\bibitem[Wiberg and Boyd (1972)] {Wiberg} Wiberg K. M. and Boyd R. H. (1972), 
		{\it Application of Strain Energy Minimization to the Dynamics
		of Conformational Changes}, J. Am. Chem.Soc., {\bf 94}, 8426.
\bibitem[Saunders (1987)] {Saunders1} Saunders M. (1987), {\it Stochastic Exploration
	of Molecular Mechanics Energy Surfaces. Hunting for the Global Minimum},
	J. Am. Chem. Soc., {\bf 109}, 3150-3152.
\bibitem[Saunders (1990)] {Saunders2} Saunders M., Houk K.N., Wu Yun-Dong, Still W. C., Lipton M., Chang G., Guida W.G. (1990), {\it Conformations of Cycloheptadecane. A comparison of Methods for
Conformational Searching}, J. Am. Chem. Soc. {\bf 112}, 1419-1427.

\end{thebibliography}{}
\end{document}
