Consider the unconstrained optimization problem of maximizing
a nonlinear function 
for 
.
A well-known class of methods for solving this problem
is direct search, which does not rely on derivative information (either
explicitly or implicitly), but employs only function
evaluations [2].
One of the most widely used direct search methods for nonlinear unconstrained
optimization problems is the Nelder-Mead simplex
algorithm [15]. (This simplex algorithm should not
be confused with the simplex algorithm of Dantzig for linear programming.)
Nelder-Mead's algorithm is parsimonious in the number
of function evaluations per iteration, and is often able to find reasonably
good solutions quickly. On the other hand, the theoretical underpinnings
of the algorithm, such as its convergence properties, are less than
satisfactory [10, 13].
In response, a number of variants have been proposed in the literature
which attempt to address such issues [14, 20, 21].
For a detailed survey of the Nelder-Mead algorithm, the reader may
refer to [25, 26].
In this paper, we focus on one implementation of the
Nelder-Mead algorithm as described in the popular handbook
Numerical Recipes [17], where it is
called the amoeba algorithm.
The amoeba algorithm maintains at each iteration a nondegenerate simplex,
a geometric figure in n dimensions of nonzero volume that is the convex
hull of n+1 vertices, 
, and their respective
function values. In each
iteration, new points are computed, along with their function values, to form
a new simplex. The algorithm terminates when the function values at the
vertices of the simplex satisfy a predetermined condition.
One iteration of the amoeba algorithm consists of the following steps:
, such that
.
Since we want to maximize, we refer to 
as the
best vertex or point, to 
as the worst point, and to
as the next-worst point. Let 
refer to
the centroid of the n best points in the vertex (i.e., all vertices except
for 
.
,
Evaluate 
.
If 
,
accept the reflected point and terminate the iteration.
,
compute the expansion point 
,
If 
accept and terminate
the iteration; otherwise
(i.e., if 
) accept and
terminate the iteration.
,
perform a contraction between and
If 
accept 
and
terminate the iteration.
at the n new vertices for
.
For the four coefficients, the standard values reported in the
literature are: 
.