On the Convergence of Pattern Search Algorithms.
We introduce an abstract definition of pattern search methods for solving nonlinear unconstrained optimization problems. Our definition unifies an important collection of optimization methods that neither compute nor explicitly approximate derivatives. We exploit our characterization of pattern search methods to establish a global convergence theory that does not enforce a notion of sufficient decrease. Our analysis is possible because the iterates of a pattern search method lie on a scaled, translated integer lattice. This allows us to relax the classical requirements on the acceptance of the step, at the expense of stronger conditions on the form of the step, and still guarantee global convergence.
Introduction
. We consider the familiar problem of minimizing a continuously
di#erentiable function f : R n
# R. Direct search methods for this problem
are methods that neither compute nor explicitly approximate derivatives of f . Our
interest is in a particular subset of direct search methods that we will call pattern
search methods. Our purpose is to generalize these methods and to present a global
convergence theory for them. To our knowledge, this is the first convergence result
for some of these methods and the first general convergence theory for all of them.
Examples of pattern search methods include such classical direct search algorithms
as coordinate search with fixed step sizes, evolutionary operation using factorial
designs (first proposed by G. E. P. Box [2, 3, 13]), and the original pattern search
algorithm of Hooke and Jeeves [7]. A more recent example is the multidirectional
search algorithm of Dennis and Torczon [6, 15]. For some time, it has been apparent
to us that the unifying theme that distinguishes these algorithms from other direct
search methods is that each of them performs a search using a "pattern" of points
that is independent of the objective function f . This informal insight is the basis for
our general definition of pattern search methods-it turns out that each of the above
pattern search methods is an instance of our general model.
Formally, our definition of pattern search methods requires the existence of a
lattice T such that if {x 1 , . , xN } are the first N iterates generated by a pattern
search method, then there exists a scale factor #N such that the steps {x 1
lie in the scaled lattice #N T . The lattice depends on the
pattern that defines the individual method and on the initial choice of the step length
control parameter, but it is independent of the objective function f . The scaling
# Received by the editors June 23, 1993; accepted for publication (in revised form) September 20,
1995. This research was sponsored by Air Force O#ce of Scientific Research grants 89-0363, F49620-
93-1-0212, and F49620-95-1-0210; United States Air Force grant F49629-92-J-0203; and Department
of Energy grant DE-FG005-86ER25017. This research was also supported in part by the Geophysical
Parallel Computation Project under State of Texas contract 1059.
http://www.siam.org/journals/siopt/7-1/25078.html
Department of Computer Science, The College of William &Mary, Williamsburg, VA 23187-8795
(va@cs.wm.edu). This work was completed while the author was in the Department of Computational
and Applied Mathematics and the Center for Research on Parallel Computation, Rice University,
Houston,
depends solely on the sequence of updates that have been applied to the step length
control parameter.
Despite isolated convergence results [4, 11, 16] for certain individual pattern search
methods, a general theory of convergence for the class of such methods remained
elusive for some time. The standard convergence theory for line search and trust
region methods depends crucially on some notion of su#cient decrease, but pattern
search methods do not enforce any such notion. Therefore, attempts such as [18]
to apply the standard theory to pattern search methods arbitrarily introduce some
notion of su#cient decrease, thereby modifying the original algorithms. Thus, the
challenge was to develop a general convergence theory for pattern search methods
without redefining what they are.
Our convergence analysis is guided by that found in Torczon [16] for the multidirectional
search algorithm; however, the present level of abstraction makes the
important elements of that analysis easier to appreciate. The present paper also
includes a correction to the specification of the scaling factors found in [16].
There are three key points to our analysis. First, we show that pattern search
methods are descent methods. Second, we prove that pattern search methods are
gradient-related methods in the sense of [10]. Finally, we demonstrate that pattern
search methods cannot terminate prematurely due to inadequate step length control
mechanisms. The crucial element of this analysis is the fact that pattern search
methods are able to relax the conditions on accepting a step by enforcing stronger
conditions on the step itself. The lattice T , together with the way in which the step
length control parameter is updated, prevent a pathological choice of steps: steps of
arbitrary lengths along arbitrary search directions are not permitted.
We are able to guarantee that, if the function f is continuously di#erentiable, then
an explicit representation of the gradient or the
directional derivative. In particular, we prove global convergence for pattern search
methods despite the fact that they do not explicitly enforce a notion of su#cient
decrease on their iterates, such as fraction of Cauchy decrease, fraction of optimal de-
crease, or the Armijo-Goldstein-Wolfe conditions. However, our convergence analysis
does share certain characteristics with the classical convergence analysis of both line
search and trust region methods. This connection is both subtle and unexpected.
Our convergence analysis for pattern search methods makes it clear why these
methods are as robust as their proponents have long claimed, while clarifying some of
the limitations that have long been ascribed to them. In addition, having identified
the common structure of these methods, it is now possible to develop new pattern
search methods with guaranteed global convergence.
In section 2 we establish the notation and general specification of pattern search
methods. In section 3 we prove that if the function to be minimized is continuously dif-
ferentiable, then pattern search methods guarantee that lim inf k#f(x k
In addition, we identify the modifications that must be made to pattern search methods
to obtain the stronger result lim k#f(x k In section 4 we show that
the classical pattern search methods mentioned above, as well as the newer multidirectional
search algorithm of Dennis and Torczon, conform to the general specification
for pattern search methods. In section 5, we give some concluding remarks; section 6
contains technical results needed for the proofs of section 3.
Notation. We denote by R, Q, Z, and N the sets of real, rational, integer, and
natural numbers, respectively.
All norms are Euclidean vector norms or the associated operator norm. We define
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 3
2. Pattern search methods. We begin by introducing the following abstraction
of pattern search methods. We defer to section 4 demonstrations that the pattern
search methods mentioned above fall comfortably within this abstraction.
2.1. The pattern. To define a pattern we need two components, a basis matrix
and a generating matrix.
The basis matrix can be any nonsingular matrix B # R n-n .
The generating matrix is a matrix C k # Z n-p , where p > 2n. We partition the
generating matrix into components
(1)
We require that M k # M # Z n-n , where M is a finite set of nonsingular matrices,
and that L k # Z n-(p-2n) and contains at least one column, the column of zeros.
A pattern P k is then defined by the columns of the matrix P Because
both B and C k have rank n, the columns of P k span R n . For convenience, we use the
partition of the generating matrix C k given in (1) to partition P k as follows:
(2)
Given # k # R, # k > 0, we define a trial step s i
k to be any vector of the form
denotes a column of C
]. Note that Bc i
determines the direction
of the step, while # k serves as a step length parameter.
At iteration k, we define a trial point as any point of the form x i
x k is the current iterate.
2.2. The exploratory moves. Pattern search methods proceed by conducting
a series of exploratory moves about the current iterate before declaring a new iterate
and updating the associated information. These moves can be viewed as sampling the
function about the current iterate x k in a well-defined deterministic fashion in search of
a new iterate x with a lower function value. The individual pattern search
methods are distinguished, in part, by the manner in which these exploratory moves
are conducted. To allow the broadest possible choice of exploratory moves and yet still
maintain the properties required to prove convergence for the pattern search methods,
we place two requirements on the exploratory moves associated with any particular
pattern search method. These requirements are given in the following Hypotheses on
exploratory moves. (Please note an abuse of notation that is nonetheless convenient:
means that the vector y is contained in the set of columns of the matrix A.)
Hypotheses on exploratory moves.
1.
2. If min{f(x k
The choice of exploratory moves must ensure two things:
1. The direction of any step s k accepted at iteration k is defined by the pattern
its length is determined by # k .
2. If simple decrease on the function value at the current iterate can be found
among any of the 2n trial steps defined by # k B# k , then the exploratory
moves must produce a step s k that also gives simple decrease on the function
value at the current iterate. In particular, f(x k need not be less than
or equal to min{f(x k
Thus, a legitimate exploratory moves algorithm would be one that somehow
guesses which of the steps defined by # k P k will produce simple decrease
and then evaluates the function at only one such step. (And that step may
be contained in # k BL k rather than in # k B# k .) At the other extreme, a
legitimate exploratory moves algorithm would be one that evaluates all p
steps defined by # k P k and returns the step that produced the least function
value.
These are the properties of the exploratory moves that enable us to prove
lim inf
even though we only require simple decrease on f . Thus we avoid the necessity
of enforcing either fraction of Cauchy decrease, fraction of optimal decrease, or the
Armijo-Goldstein-Wolfe conditions on the iterates. To obtain
lim
we need to place stronger hypotheses on the exploratory moves as well as place a
boundedness condition on the columns of the generating matrices. These extensions
will be discussed further in section 3.3.2.
2.3. The generalized pattern search method. Algorithm 1 states the generalized
pattern search method for unconstrained minimization.
Algorithm 1. The Generalized Pattern Search Method.
For
(a) Compute
(b) Determine a step s k using an exploratory moves algorithm.
(c) Compute
(d) If # k > 0 then x
Update C k and # k .
To define a particular pattern search method, it is necessary to specify the basis
matrix B, the generating matrix C k , the exploratory moves to be used to produce a
step s k , and the algorithms for updating C k and # k .
2.4. The updates. Algorithm 2 specifies the requirements for updating # k .
The aim of the updating algorithm for # k is to force # k > 0. An iteration with
otherwise, the iteration is unsuccessful. Again we note that to
accept a step we only require simple, as opposed to su#cient, decrease.
Algorithm 2. Updating # k .
Given # Q, let # w0 and # k # w1 , . , # wL
(a) If # k # 0 then #
(b) If # k > 0 then #
The conditions on # and # ensure that 0 < # < 1 and # i # 1 for all # i #. Thus,
if an iteration is successful it may be possible to increase the step length parameter
k is not allowed to decrease. Not surprisingly, this is crucial to the success
of the analysis. Also crucial to the analysis is the relationship (overlooked in [16])
between # and the elements of #.
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 5
The algorithm for updating C k depends on the pattern search method. For theoretical
purposes, it is su#cient to choose the columns of C k so that they satisfy (1) and
the conditions we have placed on the matrices M k # M # Z n-n and L k # Z n-(p-2n) .
3. The convergence theory. Having set up the machinery to define pattern
search methods, we are now ready to analyze these methods. This analysis produces
theorems of several types. The first, developed in section 3.1, demonstrates an algebraic
fact about the nature of pattern search methods that requires no assumption
on the function f . This theorem is critical to the proof of the convergence results
for it shows that we only need require simple decrease in f to ensure global conver-
gence. The second theorem, developed in section 3.2, describes the limiting behavior
of the step length control parameter # k if we place only a very mild condition on the
function f and exploit the interaction of the simple decrease condition for the generalized
pattern search method with the algorithm for updating # k . Finally, the third
and fourth theorems, developed in section 3.3, give the global convergence results.
The first theorem guarantees lim inf k#f(x k generalized pattern
search method that satisfies the specifications given in section 2. This is significant
since the theorem applies to all the pattern search methods we discuss in section 4
without the need to impose any modifications on the methods as originally stated.
The second theorem is equivalent to convergence results for line search and trust-region
globalization strategies. We can guarantee lim k#f(x k but to do
so requires placing stronger conditions on the specifications for generalized pattern
search methods. We could certainly impose these stronger conditions on the pattern
search methods presented in section 4-none of them are unreasonable to suggest or
to enforce-but we would do so at the expense of attractive algorithmic features found
in the original methods.
3.1. The algebraic structure of the iterates. The results found in this section
are purely algebraic facts about the nature of pattern search methods; they are
also independent of the function to be optimized. It is the algebraic structure of the
iterates that allows us to prove global convergence for pattern search methods without
imposing a notion of su#cient decrease on the iterates.
We begin by showing in what sense # k is a step length parameter.
Lemma 3.1. There exists a constant # > 0, independent of k, such that for any
trial step s i
produced by a generalized pattern search method (Algorithm 1) we
have
Proof. From (3) we have s i
k . The conditions we have placed on the
generating matrix C k ensure that c i
the smallest singular value of B. Then
The last inequality holds because at least one of the components of c i
k is a nonzero
integer, and hence #c i
k # 1.
From Lemma 3.1 we can see that the role of # k as a step length parameter is to
regulate backtracking and thus prevent excessively short steps.
Theorem 3.2. Any iterate xN produced by a generalized pattern search method
6 VIRGINIA TORCZON
(Algorithm 1) can be expressed in the following form:
z k ,
where
. x 0 is the initial guess,
. # , with # N and relatively prime, and # is as defined in the
algorithm for updating # k (Algorithm 2),
. r LB and r UB depend on N ,
. # 0 is the initial choice for the step length control parameter,
. B is the basis matrix, and
. z k # Z n ,
Proof. The generalized pattern search algorithm, as stated in Algorithm 1, guarantees
that any iterate xN is of the form
s k .
(We adopt the convention that s iteration k is unsuccessful.) We also know
that the step s k must come from the set of trial steps s i
p. The trial steps
are of the form s i
k .
Consider the step length parameter # k . For any k # 0, the update for # k given
in Algorithm 2 guarantees that # k is of the form
(Recall that We have also placed the following
restrictions on the form of # and
L. We can thus rewrite (5) as:
where r k # Z. Let
Then from (4) and (6) we have
Since # is rational, we can express # as #
, where # N are relatively prime.
Then, using (7),
z k ,
where z k # Z n .
Theorem 3.2 synthesizes the requirements we have placed on the pattern, the
definition of the trial steps, and the algorithm for updating # k . Note that this means
that for a fixed N , all the iterates lie on a translated integer lattice generated by x 0
and the columns of # rLB # -rUB # 0 B.
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 7
3.2. The limiting behavior of the step length control parameter. The
next theorem combines the strict algebraic structure of the iterates with the simple decrease
condition of the generalized pattern search algorithm, along with the algorithm
for updating # k , to give us a useful fact about the limiting behavior of # k .
Theorem 3.3. Assume that L(x 0 ) is compact. Then lim inf k#
Proof. The proof is by contradiction. Suppose 0 < #LB # k for all k. From (6)
we know that # k can be written as #
The hypothesis that #LB # k for all k means that the sequence {# rk
} is bounded
away from zero. Meanwhile, we also know that the sequence {# k } is bounded above
because all the iterates x k must lie inside the set L(x 0 and the
latter set is compact; Lemma 3.1 then guarantees an upper bound #UB for {# k }.
This, in turn, means that the sequence {# rk
} is bounded above. Consequently, the
sequence {# rk
} is a finite set. Equivalently, the sequence {r k } is bounded above and
below.
Let
Then (8) now holds for the bounds given in (9), rather than (7), and we see that for
all k, x k lies in the translated integer lattice G generated by x 0 and the columns of
The intersection of the compact set L(x 0 ) with the translated integer lattice G is
finite. Thus, there must exist at least one point x # in the lattice for which x
for infinitely many k.
We appeal to the simple decrease condition in the generalized pattern search
method (Algorithm 1 (d)), which guarantees that a lattice point cannot be revisited
infinitely many times since we accept a new step s k if and only if f(x k ) >
Thus there exists an N such that for all k # N , x which implies that #
We now appeal to the algorithm for updating # k (Algorithm 2 (a)) to see that
thus leading to a contradiction.
3.3. Global convergence. Throughout the discussion in this section, we assume
that f is continuously di#erentiable on a neighborhood of L(x 0 ); however, this
assumption can be weakened, using the same style of argument found in [16].
3.3.1. The general result. To prove Theorem 3.5 we need Proposition 3.4. We
defer the proof of Proposition 3.4 to section 6 in part because we wish to discuss there
several other issues that are tangential to the proof of Theorem 3.5. It is also the case
that the proofs for the results in section 6 are similar to those given for the equivalent
results found in [16], though now restated more succinctly in terms of the machinery
developed in section 2.
Proposition 3.4. Assume that L(x 0 ) is compact, that f is continuously di#er-
entiable on a neighborhood of L(x 0 ), and that lim inf k#f(x k )#= 0. Then there
exists a constant #LB > 0 such that for all k, # k > #LB .
We emphasize that the existence of a positive lower bound #LB for # k is guaranteed
only under the null hypothesis that lim inf k#f(x k )#= 0.
Theorem 3.5. Assume that L(x 0 ) is compact and that f is continuously di#er-
entiable on a neighborhood of L(x 0 ). Then for the sequence of iterates {x k } produced
by the generalized pattern search method (Algorithm 1),
lim inf
Proof. The proof is by contradiction. Suppose that lim inf k#f(x k )#= 0.
Then Proposition 3.4 tells us that there exists #LB > 0 such that for all k, # k #LB .
But this contradicts Theorem 3.3.
3.3.2. The stronger result. We can strengthen the result given in Theorem 3.5
at the expense of wider applicability. To begin with, we must add three further
restrictions: one on the pattern matrix, one on the Hypotheses on exploratory moves,
and one on the limiting behavior of the step length control parameter # k .
First, we must ensure that the columns of the generating matrix C k are bounded
in norm, i.e., that there exists a constant C > 0 such that for all k, C > #c i
k # for all
p. Given this bound, we can place an upper bound, in terms of # k , on the
norm of any trial step s i
k .
Lemma 3.6. Given a constant C > 0 such that for all k, C > #c i
k # for all
there exists a constant # > 0, independent of k, such that for any trial
step s i
k produced by a generalized pattern search method (Algorithm 1) we have
Proof. From (3) we have s i
k . Then #s i
C||B|| .
Note that the columns of M k # M are bounded by the assumption that |M| <
+#; we use this fact in the proof of Proposition 6.4. The stronger boundedness
condition on the columns of C is needed to monitor the behavior
of L k .
Second, we must replace the original Hypotheses on exploratory moves with a
stronger version, as given below. Together, Lemma 3.6 and the Strong hypotheses
on exploratory moves allow us to tie decrease in f to the norm of the gradient when
the step sizes get small enough. This is the import of Corollary 6.5, which is given in
section 6.
Strong hypotheses on exploratory moves.
1.
2. If min{f(x k
Third, we require that lim k# We can use the algorithm for updating
to ensure that this condition holds. For instance, we can force # k
to be nonincreasing by requiring w which when taken together
with Theorem 3.3 guarantees that lim k# All the algorithms we consider
in section 4, except the multidirectional search algorithm, enforce this condition by
limiting
However, it is not necessary to force the steps to be nonin-
creasing; we need only require that in the limit the step length control parameter goes
to zero, which, in conjunction with Lemmas 3.1 and 3.6, has the e#ect of ultimately
forcing the steps to zero.
Theorem 3.7. Assume that L(x 0 ) is compact and that f is continuously differentiable
on a neighborhood of L(x 0 ). In addition, assume that the columns of
the generating matrices are bounded in norm, that lim k# and that the
generalized pattern search method (Algorithm 1) enforces the Strong hypotheses on
exploratory moves. Then for the sequence of iterates {x k } produced by the generalized
pattern search method,
lim
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 9
Proof. The proof is by contradiction. Suppose lim sup k#f(x k )#= 0. Let
be such that there exists a subsequence #f(xm i
)#. Since
lim inf
given any 0 < #, there exists an associated subsequence l i such that
)#.
Then, since # k # 0, we can appeal to Corollary 6.5 to obtain for
su#ciently large,
Then the telescoping sum
l i
gives us
Since f is bounded below, f(xm i
because #f is uniformly continuous,
for i su#ciently large. However,
)# 2#.
Since equation (10) must hold for any #, 0 < #, we have a contradiction (e.g., try
The proof of Theorem 3.7 is almost identical to that of an equivalent result for
trust-region methods that was first given by Thomas [14] and which is included, in a
more general form, in the survey by Mor-e [8].
One final note: the hypotheses of Theorem 3.7 suggest that in the absence of
any explicit higher-order information about the function to be minimized, it makes
sense to terminate a generalized pattern search algorithm when # k is less than some
reasonably small tolerance. In fact, this is a common stopping condition for algorithms
of this sort and the one implemented for the multidirectional search algorithm [17].
4. The particular pattern search methods. In section 2 we stated the conditions
an algorithm must satisfy to be a pattern search method. We now illustrate
these conditions by considering the following specific algorithms:
. coordinate search with fixed step lengths,
. evolutionary operation using factorial designs [2, 3, 13],
. the original pattern search method of Hooke and Jeeves [7], and
. the multidirectional search algorithm of Dennis and Torczon [6, 15].
We will show that these algorithms satisfy the conditions that define pattern search
methods and thus are special cases of the generalized pattern search method presented
as Algorithm 1. Then we can appeal to Theorem 3.5 to claim global convergence for
these methods.
There are other algorithms for which the abstraction and accompanying analysis
holds-including various modifications to the algorithms presented-but we shall
confine our investigation to these, the best known of the pattern search methods, to
illustrate the power of our abstract approach to pattern search methods.
4.1. Coordinate search with fixed step lengths. The method of coordinate
search is perhaps the simplest and most obvious of all the pattern search methods.
Davidon describes it concisely in the opening of his belated preface to Argonne National
Laboratory Research and Development Report 5990 [5]:
Enrico Fermi and Nicholas Metropolis used one of the first digital
computers, the Los Alamos Maniac, to determine which values of
certain theoretical parameters (phase shifts) best fit experimental
data (scattering cross sections). They varied one theoretical parameter
at a time by steps of the same magnitude, and when no such
increase or decrease in any one parameter further improved the fit
to the experimental data, they halved the step size and repeated the
process until the steps were deemed su#ciently small. Their simple
procedure was slow but sure.
This simple search method enjoys many names, among them alternating direc-
tions, alternating variable search, axial relaxation, and local variation. We shall refer
to it as coordinate search.
Perhaps less obvious is that coordinate search is a pattern search method. To see
this, we begin by considering all possible outcomes for a single iteration of coordinate
search when shown in Fig. 1. We mark the current iterate x k . The x i
's
denote trial points considered during the course of the iteration. The next iterate x k+1
is marked. Solid circles indicate successful intermediate steps taken during the course
of the exploratory moves while open circles indicate points at which the function was
evaluated but that did not produce further decrease in the value of the objective
function. Thus, in the first scenario shown a step from x k to x 1
k resulted in a decrease
in the objective function, so the step from x 1
k to x k+1 was tried and led to a further
decrease in the objective function value. The iteration was then terminated with a
new point x k+1 that satisfies the simple decrease condition f(x k+1 ) < f(x k ). In the
worst case, the last scenario shown, 2n trial points were evaluated
k , and
producing decrease in the function value at the current iterate x k . In
this case, x and the step size must be reduced for the next iteration.
We now show this algorithm is an instance of a generalized pattern search method.
4.1.1. The matrices. Coordinate search is usually defined so that the basis
matrix is the identity matrix; i.e., However, knowledge of the problem may
lead to a di#erent choice for the basis matrix. It may make sense to search using
a di#erent coordinate system. For instance, if the variables are known to di#er by
several orders of magnitude, this can be taken into account in the choice of the basis
matrix (though, as we will see in section 6.2, this may have a significant e#ect on the
behavior of the method).
The generating matrix for coordinate search is fixed across all iterations of the
method. The generating matrix C contains in its columns all possible combi-
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 11
Fig. 1. All possible subsets of the steps for coordinate search in R 2 .
#k
z }| {
Fig. 2. The pattern for coordinate search in R 2 with a given step length control parameter # k .
nations of {-1, 0, 1}. Thus, C has columns. In particular, the columns of C
contain both I and -I, as well as a column of zeros. We define
of the remaining 3 n
columns of C. Since C is fixed across all iterations of the
method, there is no need for an update algorithm.
For
.
Thus, when possible trial points defined by the pattern
given step length # k , can be seen in Fig. 2. Note that the pattern includes all the
possible trial points enumerated in Fig. 1.
4.1.2. The exploratory moves. The exploratory moves for coordinate search
are given in Algorithm 3, where the e i 's denote the unit coordinate vectors.
Algorithm 3. Exploratory Moves Algorithm for Coordinate Search.
Given x k , # k , f(x k ), and B, set s
For do
(a) s i
. Compute
(b) If f(x i
Otherwise,
k . Compute
(ii) If f(x i
k .
Return.
The exploratory moves are executed sequentially in the sense that the selection of
the next trial step is based on the success or failure of the previous trial step. Thus,
while there are 3 n possible trial steps, we may compute as few as n trial steps, but
we compute no more than 2n at any given iteration, as we saw in Fig. 1.
From the perspective of the theory, there are two conditions that need to be met
by the exploratory moves algorithm. First, as Figs. 1 and 2 illustrate, all possible
trial steps are contained in # k P .
The second condition on the exploratory moves is the more interesting; coordinate
search demonstrates the laxity of this second hypothesis. For instance, in the first
scenario shown in Fig. 1, decrease in the objective function was realized for the first
trial step
so the second trial step
was tried and accepted. It is certainly possible that greater decrease in the value of
the objective function might have been realized for the trial step
which is defined by a column in the matrix M (the step s 2
k is defined by a column in the
matrix L), but s #
k is not tried when simple decrease is realized by the step s 1
k . However,
in the worst case, as seen in Fig. 1, the algorithm for coordinate search ensures that
all 2n steps defined by # k B# k B[M -M are tried before returning
the step s In other words, the exploratory moves given in Algorithm 3 examine
all 2n steps defined by # k B# unless a step satisfying
4.1.3. Updating the step length. The update for # k is exactly as given in
Algorithm 2. As noted by Davidon, the usual practice is to continue with steps of
the same magnitude until no further decrease in the objective function is realized, at
which point the step size is halved. This corresponds to setting
Thus,
This su#ces to verify that coordinate search with fixed step length is a pattern
search method. Theorem 3.5 thus holds. The exploratory moves algorithm for coordinate
search would need to be modified to satisfy the Strong hypotheses on exploratory
moves for the conditions of Theorem 3.7 to be met.
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 13
4.2. Evolutionary operation using factorial designs. In 1957 G. E. P. Box
[2] introduced the notion of evolutionary operation as a method for increasing industrial
productivity. The ideas were developed within the context of the on-line
management of industrial processes, but Box recognized that the technique had more
general applicability. Subsequent authors [3, 13] argued that the basic technique was
readily applicable to general unconstrained optimization and it is within this context
that we examine the ideas here.
In its simplest form, evolutionary operation is based on using two-level factorial
designs: evaluate the function at the vertices of a hypercube centered about the
current iterate. (G. E. P. Box refers to this as one of a variety of "pattern of variants"
[2].) If simple decrease in the value of the objective function is observed at one of
the vertices, it becomes the new iterate. Otherwise, the lengths of the edges in the
hypercube are halved and the process is repeated.
4.2.1. The matrices. As with coordinate search, the usual choice for the basis
matrix is though, as with coordinate search, other choices may be made to
reflect information known about the problem to be solved.
The generating matrix for evolutionary operation is fixed across all iterations of
the method. The generating matrix C contains in its columns all possible
combinations of {-1, 1}; to this we append a column of zeros. Thus C has
columns.
We take M to be any linearly independent subset of n columns of C; -M necessarily
will be contained in C. Once again, L is fixed and consists of the remaining
columns of C.
There is no need for an algorithm to update C since the generating matrix is
fixed.
4.2.2. The exploratory moves. The exploratory moves given in Algorithm 4
are simultaneous in the sense that every possible trial step s i
computed at each iteration. It is then the case that every trial step s i
k is contained in
. The second observation of note is that since
of our choice of M (and thus, by extension, our choice of #). Furthermore, we are
guaranteed that the Strong hypotheses on exploratory moves are satisfied.
Algorithm 4. Exploratory Moves Algorithm for Evolutionary Operation

Given x k , # k , f(x k ), B, and
, set s
For do
(a) s i
k . Compute
(b) If f(x i
k .
Return.
4.2.3. Updating the step length. The algorithm for updating # k is exactly
as given in Algorithm 2, with # usually set to 1/2 and
Since we have shown that evolutionary operation satisfies all the necessary re-
quirements, we can therefore conclude that it, too, is a pattern search method, so
Theorem 3.5 holds. The algorithm, as stated above, also satisfies the conditions of
Theorem 3.7.
14 VIRGINIA TORCZON
Fig. 3. The pattern step in R 2 , given x k #= x k-1 , k > 0.
4.3. Hooke and Jeeves' pattern search algorithm. In addition to introducing
the general notion of a "direct search" method, Hooke and Jeeves introduced the
pattern search method, a specific kind of search strategy [7]. The pattern search of
Hooke and Jeeves is a variant of coordinate search that incorporates a pattern step
in an attempt to accelerate the progress of the algorithm by exploiting information
gained from the search during previous successful iterations.
The Hooke and Jeeves pattern search algorithm is opportunistic. If the previous
iteration was successful (i.e., # k-1 > 0), then the current iteration begins by conducting
coordinate search about a speculative iterate x k
the current iterate x k . This is the pattern step. The idea is to investigate whether
further progress is possible in the general direction x k - x k-1 (since, if x k #= x k-1 ,
then x k - x k-1 is clearly a promising direction).
To make this a little clearer, we consider the example shown in Fig. 3. Given
x k-1 and x k (we assume, for now, that k > 0 and that x k #= x k-1 ), the pattern search
algorithm takes the step x k - x k-1 from x k . The function is evaluated at this trial
step and the trial step is accepted, temporarily, even if f(x k
The Hooke and Jeeves pattern search algorithm then proceeds to conduct coordinate
search about the temporary iterate x k Thus, in R 2 , the exploratory
moves are exactly as shown in Fig. 1, but with x k substituted for x k .
If coordinate search about the temporary iterate x k
then the point returned by coordinate search about the temporary iterate is accepted
as the new iterate x k+1 . If not, i.e., then the
pattern step is deemed unsuccessful, and the method reduces to coordinate search
about x k . For the two dimensional case, then, the exploratory moves would simply
resort to the possibilities shown in Fig. 1.
If the previous iteration was not successful, so x
the iteration is limited to coordinate search about x k . In this instance, though, the
updating algorithm for # k will have reduced the size of the step (i.e., #
The algorithm does not execute the pattern step when
To express the pattern search algorithm within the framework we have developed,
we use all the machinery required for coordinate search. Once again, the basis matrix
is usually defined to be We append to the generating matrix another set of
columns to capture the e#ect of the pattern step and we change the exploratory
moves algorithm, as detailed below.
4.3.1. The generating matrix. Recall that the generating matrix for coordinate
search consists of all possible combinations of {-1, 0, 1} and is never changed.
For the Hooke and Jeeves pattern search method, we allow the generating matrix to
change from iteration to iteration to capture the e#ect of the pattern step. We append
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 15
another set of 3 n columns, consisting of all possible combinations of {-1, 0, 1}, to the
initial generating matrix for coordinate search. Thus C k has columns. The
additional 3 n columns allow us to express the e#ect of the pattern step with respect
to x k , rather than with respect to the temporary iterate x k which is
how the Hooke and Jeeves pattern search method usually is described. The matrix
M is unchanged; is allowed to vary, though
only in the 3 n columns associated with the pattern step. For
.
For notational convenience, we require that the last column of C 0 , which we denote
as c p
0 , be the column of zeros. In both the algorithm for updating C k (Algorithm 5)
and the algorithm for the exploratory moves (Algorithm 6), we use the column c p
k to
measure the accumulation of a sequence of successful pattern steps. This can be seen,
in (12), for our example from Fig. 3. In this example, we have the generating matrix
.
The pattern step represented by the vector (1 1) T , seen in the last
column of C k . Note that the only di#erence between the columns of C 0 given in (11)
and the columns of C k given in (12) is that (1 1) T has been added to the last 3 2
columns of C k .
The algorithm for updating the generating matrix updates the last 3 n columns
of C k ; the first 3 n columns remain unchanged, as in coordinate search. The purpose
of the updating algorithm is to incorporate the result of the search at the current
iteration into the pattern for the next iteration. This is done using Algorithm 5. Note
the distinguished role of c p
k , the last column of C k , which represents the pattern step
Algorithm 5. Updating C k .
For do
k .
Return.
Since (1/# k )s k is necessarily a column of C k and C 0 # Z n-p , an argument by
induction shows that the update algorithm for C k ensures that the columns of C k
always consist of integers.
4.3.2. The exploratory moves. In Algorithm 6, the e i 's denote the unit co-ordinate
vectors and c p
k denotes the last column of C k . We set
is defined when
A useful example for working through the logic of the algorithm can be found in
[1], though the presentation and notation di#er somewhat from that given here.
Algorithm 6. Exploratory Moves Algorithm for Hooke and Jeeves.
Given x k , # k , f(x k ), B, and # k-1 , set #
For do
(a)s i
k . Compute
(b)If f(x i
k .
Otherwise,
k . Compute
k .
For do
(a)s i
k . Compute
(b)If f(x i
k .
Otherwise,
k . Compute
k .
Return.
All possible steps are contained in # k P k since C k contains columns that represent
the "pattern steps" tried at the beginning of the iteration. And, once again, the
exploratory moves given in Algorithm 6 examine all 2n steps defined by # k B# unless
a step satisfying
Since we have shown that the pattern search algorithm of Hooke and Jeeves
satisfies all the necessary requirements, we can therefore conclude that it, too, is a
special case of the generalized pattern search method and Theorem 3.5 holds.
4.4. Multidirectional search. The multidirectional search algorithm was introduced
by Dennis and Torczon in 1989 [15] as a first step towards a general purpose
optimization algorithm with promising properties for parallel computation. While
subsequent work led to a class of algorithms (based on the multidirectional search
algorithm) that allows for more flexible computation [6, 17], one of the unanticipated
results of the original research was a global convergence theorem for the multidirectional
search algorithm [16].
The multidirectional search algorithm is a simplex-based algorithm. The pattern
of points can be expressed as a simplex (i.e., points or vertices) based at the
current iterate; as such, multidirectional search owes much in its conception to its
predecessors, the simplex design algorithm of Spendley, Hext, and Himsworth [12] and
the simplex algorithm of Nelder and Mead [9]. However, multidirectional search is a
di#erent algorithm-particularly from a theoretical standpoint. Convergence for the
Spendley, Hext, and Himsworth algorithm can be shown only with some modification
of the original algorithm, and then only under the additional assumption that the
function f is convex. There are numerical examples to demonstrate that the Nelder-Mead
simplex algorithm may fail to converge to a stationary point of the function
because the uniform linear independence property (discussed in section 6.2), which
plays a key role in the convergence analysis, cannot be guaranteed to hold [15].
The multidirectional search algorithm is described in detail in both [6] and [16].
The formulation given here is di#erent and, in fact, introduces some redundancy that
can be eliminated when actually implementing the algorithm. However, the way of
expressing the algorithm that we use here allows us to make clear the similarities
between this and other pattern search methods.
4.4.1. The matrices. It is most natural to express multidirectional search in
terms of multiple basis matrices B k and a fixed generating matrix C, which is at odds
with our definition for generalized pattern search methods. As we shall see, however,
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 17
it is possible to convert the more natural specification to one that conforms to our
requirements for a pattern search method.
The multidirectional search algorithm centers around a family of basis matrices
B that consists of all matrices representing the edges adjacent to each vertex in a
nondegenerate n-dimensional simplex that the user is allowed to specify. Since the
ordering of the columns is not unique and typically not preserved in the implementation
of the method, we consider all possible representations of the columns of the
matrices associated with the edges adjacent to the (n+1) vertices of the simplex. We
then add the negatives of these (n basis matrices to account for the e#ect of the
reflection step allowed by the multidirectional search algorithm. Thus the cardinality
of the set B is
Fortunately, there is no need to construct this unwieldy number of basis matrices
to initialize the method. We can update the basis matrix after each iteration k
by reconstructing the new basis matrix B k+1 , given the outcome of the exploratory
moves, from the trial points x i
during the course of the
exploratory moves. This procedure is given in Algorithm 7. The scalar scale is
chosen during the course of the exploratory moves (see Algorithm 8) to ensure that
factoring out any change in the size of the simplex introduced by a
change in # k . This has the further e#ect of preserving the role of # k as a step length
parameter.
Algorithm 7. Updating B k .
Given
scale, best, and x i
For (best - 1) do
best
For (best do
best
Otherwise
For do
Return.
Given this use of a family of basis matrices to help define the multidirectional
search algorithm, the generating matrix is then the fixed matrix
Thus, C contains To ensure that C # Z n-p , we
Z. Furthermore, to ensure that the role of # k as a step length parameter
is not lost with the introduction of the expansion step represented by -I, we require
- #. The algorithm is defined so that # w1 , # w2
This
requires the further restriction that # N. Again, this is not an onerous restriction.
Multidirectional search usually is specified so that 2.
Now, to bring this notation into conformity with our definition for a generalized
pattern search method, observe that we can represent all possible basis matrices B #
in terms of a single reference matrix B # B so that
A convenient feature of using the edges of a simplex to form the set of basis matrices
is that the matrices -
consist only of elements from the set {-1, 0, 1}. The matrices
are necessarily nonsingular because of the nondegeneracy of the simplex. We use
to represent the set of matrices -
and observe that since B is a finite set, the set
B is also finite.
We then observe that
Thus we can define the pattern in terms of the single reference matrix B and the
redefined generating matrix
with
B. We also have L k # [-
0] and since - # Z,
4.4.2. The exploratory moves. The exploratory moves for the multidirectional
search method are given in Algorithm 8; the e i 's denote the unit coordinate
vectors. We use the notion of B k # B for consistency with the update algorithm given
in Algorithm 6, but we could just as easily substitute B -
in the algorithm
given below.
Algorithm 8. Exploratory Moves Algorithm for Multidirectional
Search.
Given
# N, set s
For do
(a) s i
k . Compute
(b) If f(x i
k , and best = i.
For do
(a) s i
k . Compute
(b) If f(x i
k , and best = i.
For do
(a) s i
(b) If f(x i
Return.
Clearly, s k # k P k . Since the exploratory moves algorithm considers all steps
of the form # k B# k , unless simple decrease is found after examining only the steps
defined by # k BM k , this guarantees we satisfy the condition that if min{f(x k +y), y #
4.4.3. Updating the step length. The algorithm for updating # k is that given
in Algorithm 2. In this case, while # usually is set to 1/2 so that
and include an expansion factor usually equals
one. Thus usually 2. The choice of # k # is made during the
execution of the exploratory moves.
Since we have shown that the multidirectional search algorithm satisfies all the
necessary requirements, we conclude that it is also a pattern search method and thus
Theorem 3.5 applies. Note that since we allow - > 1, which is a useful algorithmic
feature, we cannot guarantee that lim k# and so Theorem 3.7 does not
automatically apply.
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 19
5. Conclusions. We have presented a framework in which one can analyze pattern
search methods. This framework abstracts and quantifies the similarities of the
classical pattern search methods and enables us to prove lim inf k#f(x k
for this class of algorithms. We also specify the conditions under which the limit
can be shown to hold.
These convergence results are perhaps surprising, given the simplicity of pattern
search methods, but derive from the algebraic rigidity imposed on the iterates produced
by pattern search methods. This is gratifying, since while this rigidity originally
was introduced as a heuristic for directing the exploratory moves, it turns out to be
the key to proving convergence as well. This analysis also highlights just how weak
the conditions on the acceptance of the step can be and yet still allow a global convergence
analysis, an observation that may prove useful in the analysis of other classes
of optimization methods.
6. Technical results. We deferred the proof of Proposition 3.4 for several rea-
sons. First, many of the results in this section are generalizations of similar results to
be found in [16]. The abstraction in section 2 leads to more succinct proofs. Second,
the proof of Proposition 3.4 is closely related to that of several other results presented
in this section and requires us to introduce several additional notions.
We return to our definition of the pattern as to show that the pattern
contains at least one direction of descent whenever #f(x k ) #= 0.
Recall that we require the columns of C k to contain both M k and -M k . Thus,
can be partitioned as follows:
We now elaborate on these requirements. Since M k is an n-n nonsingular matrix
and B is nonsingular, we are guaranteed that BM k forms a basis for R n . Further,
we are guaranteed that at any iteration k, if #f(x k ) #= 0, x k - Bc i
is a direction of
descent for at least one column c i
k contained in the block # k .
6.1. Descent methods. Of course, the existence of a trial step in a descent
direction is not su#cient to guarantee that decrease in the value of the objective
function will be realized. To guarantee that a pattern search method is a descent
method, we need to guarantee that in a finite number of iterations the method produces
a positive step size # k that achieves decrease on the objective function at the
current iterate. We now show that this is the case.
Lemma 6.1. Suppose that f is continuously di#erentiable on a neighborhood of
there exists q # Z, q # 0 such that # k+q > 0 (i.e., the
q)th iteration is successful).
Proof. A key hypothesis placed on the exploratory moves is that if descent can
be found for one of the trial steps defined by # k B# k , then the exploratory moves
returns a step that produces descent.
Because BC k has rank n, if there exists at least one trial
direction d i
loss of generality. Thus, there exists an h k > 0
such that for 0 < h # h k ,
If at iteration k, # k > h k , then the iteration may be unsuccessful; that is, #
When the iteration is unsuccessful, the generalized pattern
search method sets x and the updating algorithm sets #
is strictly less than one, there exists q # Z, q # 0, such that # q # k # h k . Thus we are
guaranteed descent, i.e., a successful iteration, in at most q iterations.
6.2. Uniform linear independence. The pattern P k guarantees the existence
of at least one direction of descent whenever #f(x k ) #= 0. We now want to guarantee
the existence of a bound on the angle between the direction of descent contained in
B# k and the negative gradient at x k (whenever #f(x k ) #= 0). We will show, in fact,
that this bound is uniform across all iterations of the pattern search algorithm. To
do so, we use the notion of uniform linear independence [10].
Lemma 6.2. For a pattern search algorithm, there exists a constant # > 0 such
that for all k # 0 and x #= 0,
Proof. To demonstrate the existence of #, we first consider the simplest possible
I and and use this to derive a bound for any
choice of B and C k that satisfies the conditions we have imposed.
Lemma 6.3. Suppose
where the e j 's are the unit coordinate vectors.
I and
min
cos #(y) =# n
Proof. We have |y T e j
are guaranteed that |y j | # 1/ # n for some j, so |y T e j | # 1/ # n for some j. Thus
cos #(y) # 1/ # n.
Now note that cos #(y) attains this lower bound for any y
Thus, if the pattern search is restricted to the coordinate directions defined by
gives the lower bound on the absolute value of the cosine of
the angle between the gradient and a guaranteed direction of descent. We now use
the bound for this particular case to derive a bound for the general case.
Assume a general basis matrix B and a general matrix M k # M, where |M| <
+#. We adopt the notation BM
k ]. Then for any x #= 0 we have the
If we set -T w, we have
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 21
where #(BM k ) is the condition number of the matrix BM k . Thus, we have
To ensure a bound # that is independent of the choice of any particular matrix
simply observe that the set M is required to be finite. Thus, # is taken
to be
M#M
.
The bound given in (14) points to two features that explain much about the behavior
of pattern search methods. Since we never explicitly calculate-or approximate-
the gradient, we are dependent on the fact that in the worst case at least one of our
search directions is not orthogonal to the gradient; # gives us a bound on how far
away we can be. Thus, as either the condition number of the product BM k increases,
or the dimension of the problem increases, our bound on the angle between the search
direction and the gradient deteriorates. This suggests two things. First, we should
be very careful in our choice of B and M for any particular pattern search method.
Second, we should not be surprised that these methods become less e#ective as the
dimension of the problem increases.
Nevertheless, even though pattern search methods neither require nor explicitly
approximate the gradient of the function, the uniform linear independence condition
demonstrates that the pattern search methods are, in fact, gradient-related methods,
as defined by Ortega and Rheinboldt [10], which is one reason why we can establish
global convergence.
6.3. The descent condition. Having introduced the notion of uniform linear
independence with the bound #, we are now ready to show that pattern search methods
reduce # k only when necessary to find descent. To do this we will show that once
the steps s i
are small enough, then a successful step must be returned
by the exploratory moves algorithm. Lemma 3.1 allows us to restate this condition
in terms of # k . We use the result to prove Proposition 3.4.
Proposition 6.4. Suppose that L(x 0 ) is compact and f is continuously di#er-
entiable on a neighborhood of L(x 0 ). Given # > 0,
Suppose also that x 0
# . Then there exists # > 0, independent of k, such that if
# and # k < #, then the kth iteration of a generalized pattern search method
(see Algorithm 1) will be successful (i.e., # thus
Proof. We restrict our attention to the steps defined by the columns of # k B# k .
This is su#cient since the Hypotheses on exploratory moves ensure that a step s k
satisfying the simple decrease condition # k > 0 must be returned if a trial step defined
by a column of # k B# k satisfies the simple decrease condition.
If s i
is a step defined by # k B# k (we assume that P k is partitioned
as in (2) so that the first 2n columns of P k contain the columns of B# k #
independent of k,
22 VIRGINIA TORCZON
since M k # M # Z n-n and M is a finite set of matrices. Together, (15) and
Lemma 3.1 yield
allows us to define
dist (L(xN are compact and disjoint, we
know that d > 0. If # k < d/2# , then #s i
Thus x i
k lies in the interior of L(x 0 ) for all precisely, for all
lies in the ball B(x k , d/2) # L(x 0 ).
x#f(x)#. By design, # > 0. Since #f is continuous on a
neighborhood of L(x 0 ), #f is uniformly continuous on a neighborhood of L(x 0 ).
Thus, there exists a constant r > 0, depending only on # and the # from (13), such
that
We define
min  d, r  .
We are now assured that if
then
and
We are ready to argue that if at any iteration k # N , x k
# and (17) is satisfied,
then an acceptable step will be found.
Choose a trial point x i
and
The definitions
of# and the pattern P k , together with Lemma 6.2, guarantee the
existence of at least one such x i
k .
Since (17) holds by assumption, (18) also holds. We can apply the mean value
theorem to obtain f(x i
Consider the first term on the right-hand side of (20). Our choice of x i
k gives us
ON THE CONVERGENCE OF PATTERN SEARCH ALGORITHMS 23
Furthermore, since #f(x k ) T
Now consider the second term on the right-hand side of (20). The Cauchy-Schwarz
inequality gives us
Combine (21) and (22) to rewrite (20) as
holds by assumption, (19) also holds. We then have
Thus, when # k < #, f(x i
for at least one s i
k defined by # k Bc i
2n. The Hypotheses on exploratory moves guarantee that if min{f(x k
and the algorithm for updating # k (Algorithm 2) ensures that # k+1 # k .
Proposition 6.4 guarantees that if # k is small enough, a generalized pattern search
method realizes simple decrease because there exists at least one step among the 2n
steps defined by # k B# k that gives decrease as a function of the norm of the gradient
at the current iterate, as shown in (23); the Hypotheses on exploratory moves then
ensure that the exploratory moves algorithm must return a step that satisfies at least
simple decrease. However, there are no guarantees that the step returned by an
exploratory moves algorithm satisfies more than the simple decrease condition.
To tie the amount of actual decrease to the norm of the gradient, we must place
much stronger conditions on the generalized pattern search method, as discussed in
section 3.3.2. Once we have done so, Corollary 6.5 follows more or less immediately
from Proposition 6.4.
Corollary 6.5. Suppose that L(x 0 ) is compact and f is continuously di#eren-
tiable on a neighborhood of L(x 0 ). Suppose that the columns of the generating matrix
are bounded in norm and that the generalized pattern search method (Algorithm 1)
enforces the Strong hypotheses on exploratory moves. Given # > 0, let
Suppose also that x 0
# . Then there exist # > 0 and # > 0, independent of k, such
that for all but finitely many k, if x k
# and # k < #, then
Proof. From Proposition 6.4, (23) says that for k #
(Lemma 6.1 guarantees the existence of N), there exists at least one trial step s i
such that once # k < #, where # is as defined in (16), we have
The Strong hypotheses on exploratory moves give us
Lemma 3.1 ensures that
Lemma 3.6, which holds only when the columns of the generating matrix are bounded
in norm, gives us
We define #
2 # to complete the proof.
We now prove Proposition 3.4.
Proof. By assumption, lim inf k#f(x k )#= 0. Then we can find N 1 and
such that for all k # N 1 , x k
guarantees the existence of N
From Proposition 6.4 we are assured of # > 0 such that if # k #, then the
iteration will be successful. Given # 0 , there exists a constant q # Z, q # 0, such
that # q # 0 #, where # (0, 1) and is as defined in the algorithm for updating # k
(Algorithm 2). Thus, for k # N , # q+1 # 0 < # k .

Acknowledgments

. This paper benefited from conversations with J. E. Dennis,
Stephen Nash, Michael Trosset, Lu-s Vicente, and especially Michael Lewis. In partic-
ular, discussions with Michael Lewis were critical in the distillation of the abstraction
for pattern search methods found in section 2 and in the development of the analytic
arguments for the algebraic structure of the iterates found in section 3.1.
The review and comments made by an anonymous referee, Danny Ralph (the
second referee, who agreed to reveal his identity for this acknowledgment), and Jorge
Mor-e, the editor, are gratefully acknowledged. In particular, the observation by Danny
Ralph that the pattern contains only vectors in a fixed lattice led to a more general
result and a much more elegant presentation.



--R

Analysis and Methods



Variable metric method for minimization

"Direct search"

A simplex method for function minimization
Iterative Solution of Nonlinear Equations in Several Variables
Computational Methods in Optimization: A Unified Approach
Sequential application of simplex designs in optimisation and evolutionary operation
in Numerical Methods for Unconstrained Optimization
Sequential Estimation Techniques for Quasi-Newton Algorithms
A Direct Search Algorithm for Parallel Machines
On the convergence of the multidirectional search algorithm
PDS: Direct Search Methods for Unconstrained Optimization on Either Sequential or Parallel Machines
Positive basis and a class of direct search techniques
--TR

--CTR
M. Hintermller, Solving nonlinear programming problems with noisy function values and noisy gradients, Journal of Optimization Theory and Applications, v.114 n.1, p.133-169, July 2002
D. Byatt , I. D. Coope , C. J. Price, Conjugate Grids for Unconstrained Optimisation, Computational Optimization and Applications, v.29 n.1, p.49-68, October 2004
Stefano Lucidi , Marco Sciandrone, A Derivative-Free Algorithm for Bound Constrained Optimization, Computational Optimization and Applications, v.21 n.2, p.119-142, February 2002
rpd Brmen , Janez Puhan , Tadej Tuma, Grid Restrained Nelder-Mead Algorithm, Computational Optimization and Applications, v.34 n.3, p.359-375, July      2006
J. M. Gablonsky , C. T. Kelley, A Locally-Biased form of the DIRECT Algorithm, Journal of Global Optimization, v.21 n.1, p.27-37, September 2001
Peter Buchholz , Dennis Mller , Peter Kemper , Axel Thmmler, OPEDo: a tool framework for modeling and optimization of stochastic models, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
Lennart Frimannslund , Trond Steihaug, A generating set search method using curvature information, Computational Optimization and Applications, v.38 n.1, p.105-121, September 2007
Todd A. Sriver , James W. Chrissis, Combined pattern search and ranking and selection for simulation optimization, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
Michael Heitzer, Structural Optimization with FEM-based Shakedown Analyses, Journal of Global Optimization, v.24 n.3, p.371-384, November 2002
Hong-Xuan Huang , Panos M. Pardalos , Zuo-Jun Shen, A Point Balance Algorithm for the Spherical Code Problem, Journal of Global Optimization, v.19 n.4, p.329-344, April 2001
Convergence Analysis of Unconstrained and Bound Constrained Evolutionary Pattern Search, Evolutionary Computation, v.9 n.1, p.1-23, January 2001
Rommel G. Regis , Christine A. Shoemaker, Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions, Journal of Global Optimization, v.31 n.1, p.153-171, January   2005
Hart, Locally-adaptive and memetic evolutionary pattern search algorithms, Evolutionary Computation, v.11 n.1, p.29-51, Spring
Matthias Ihme , Alison L. Marsden , Heinz Pitsch, Generation of optimal artificial neural networks using a pattern search algorithm: Application to approximation of chemical systems, Neural Computation, v.20 n.2, p.573-601, February 2008
Genetha Anne Gray , Tamara G. Kolda , Ken Sale , Malin M. Young, Optimizing an Empirical Scoring Function for Transmembrane Protein Structure Determination, INFORMS Journal on Computing, v.16 n.4, p.406-418, Fall 2004
Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA,
coordinate search;evolutionary operation;pattern search;direct search methods;local variation;multidirectional search;convergence analysis;axial relaxation;unconstrained optimization;globalization strategies;downhill simplex search;alternating variable search