Basic Concept:
A simplex is a collection of n+1
points in n-dimensional space.
The downhill simplex search repeatedly
replaces the point having the highest function value in a simplex
with another point.
When combined with other operations, the simplex
under consideration adapts itself to the local landscape,
elongating down long inclined planes, changing direction on
encountering a valley at an angle,
and contracting in the neighborhood of a minimum.
Initialization:
To start the downhill simplex search, we must initialize a simplex of
n+1 points. For example, a simplex is a triangle in
two-dimensional space and a tetrahedron in three-dimensional space.
Moreover, we would like the simplex to be nondegenerate--that is, it
encloses a finite inner n-dimensional volume.
An easy way to set up
a simplex is to start with an initial starting point
and the
other n points can be taken as
where
's
are unit vectors consisting of a basis of the
n-dimensional space and
is a constant reflecting the guess of the characteristic
length scale of the optimization problem in question.
We write
for the function value at
and let
In other words, l and h are respectively the indices
for the minimum and maximum of
.
In symbols,
Let
be the average (centroid) of these n+1 points.
Each cycle of this method starts with a reflection point
of 
.
Depending on the function value at
,
we have four possible operations to change the current simplex
to explore the landscape of the function efficiently in
multidimensional space.
These four operations are
(1) reflection away from
;
(2) reflection and expansion away from
;
(3) contraction along one dimension connecting
and
; and
(4) shrinkage toward
along all dimensions.
When f is a two-input function,
these four operations are shown in the following figure.
|
|
Before describing the full cycle of the simplex search, we need to define four intervals to be used in the search process:
.
|
| Four intervals used in the downhill simplex search. |
A Full Cycle of Downhill Simplex Search:
A full cycle of the downhill simplex search involves the following
four steps:
and its value
as
where the reflection coefficient
is a positive constant. Thus
is on the line joining
and ,
on the far side of
from
.
Depending on the value of
,
we have the following actions:
is in interval 1, go to
expansion.
is in interval 2, replace
with
and finish this cycle.
is in interval 3, replace
with
and go to contraction.
is in interval 4, go to contraction.
and its value
as
where the expansion coefficient
is greater than unity.
If
is in interval 1, replace
with
and finish this cycle. Otherwise, replace
with the original reflection point
and finish this cycle.
and its value
as
where the contraction coefficient
lies between 0 and 1.
If
is in interval 1, 2, or 3, replace
with
and finish this cycle. Otherwise, go to shrinkage.
with
.
Finish this cycle.
The foregoing cycle is repeated until a given stopping criterion is met.
A complete flow chart of the foregoing steps is given next.
|
| Flowchart for downhill simplex search. |
Before starting using this method, we still need to determine three
constants
,
and
,
which are the coefficients for reflection, contraction, and expansion.
Generally speaking, the optimal values for these coefficients are
application dependent, and the best way to select their values is
by doing some trial-and-error experiments.
A good starting point is
;
these values are suggested in Nelder and Mead's original paper.
Downhill Simplex Search for Continuous Optimization:
An Example:
Find the min. of the peaks function:
z = peaks(x, y)
= 3*(1-x)^2*exp(-(x^2) - (y+1)^2)
- 10*(x/5 - x^3 - y^5)*exp(-x^2-y^2) - 1/3*exp(-(x+1)^2 - y^2).
|
|
| Surface plot of z = peaks(x, y) | Contour plot of z = peaks(x, y) |
|
| An example of simplex search |
Advantages of Simplex Search:
Weakness of Simplex Search:
Reported Simplex Search Applications:
Reference:
Neuro-Fuzzy and Soft Computing