The three Simplex Search classes were conceived as part of an undergraduate honors thesis by Adam Gurson under advisor Virginia Torczon in the Computer Science Department of the College of William and Mary. The project required access to a variety of simplex search algorithms that could be easily tested and compared. The classes implement three simplex search algorithms (discussed below): The simplex method of Spendley, Hext, and Himsworth; the algorithm by Nelder and Mead, as specified by Lagarias, Reeds, Wright, and Wright; and a sequential version of Torczon's multidimensional search. While each has its specific rules for simplex manipulation, they all follow roughly the same basic heuristic. Each begins with a nondegenerate simplex. The function is then evaluated at the vertices of the simplex. As the algorithms proceed, they keep track of the point at which the best function value is found. For each iteration of the algorithm, they attempt to replace simplex vertices that yield high function values with vertices whose new function values are lower. After each iteration, the vertices that replaced those in the starting simplex leave us with a new simplex. The goal of all three algorithms is to move the simplex, by replacing vertices, into the neighborhood of a minimizer.

The Vector and Matrix classes, built
from the Template Numerical
Toolkit, implement vectors and matrices in a fashion suitable for
mathematical computation. The Template Numerical Toolkit was
originally created by Roldan
Pozo,
who is a research scientist in the
Mathematical and Computational
Sciences Division
of the Information
Technology Laboratory at the
National Institute of Standards and
Technology (NIST). This version was modified by Chris Siefert from
the College of William and Mary,
to add increased functionality. New
features include 2-norm computation (based on the BLAS
implementation of `drnm2`)
for vectors, alternative methods for
accessing matrix data.

The SHHSearch class performs a simple search on trial points located in the positions described by the vertices of a rigid simplex. We adapted the classic Spendley, Hext, and Himsworth algorithm, originally designed for evolutionary operation rather than optimization, to better suit the purpose of numerical optimization. The underlying heuristic is to flip (by replacing vertices) the simplex along the gradient of the function, with the goal of locating a valid local minimizer. We use the notion of point age to decide when to shrink the simplex to narrow in on the exact location of a minimizer. For an in-depth discussion of the algorithm, see Adam Gurson's Honors Thesis.

The NMSearch class is another classic search, first described by Nelder and Mead, and later specified by Lagarias, Reeds, Wright, and Wright. The main difference betweed the NMSearch and the SHHSearch is that in the Nelder-Mead search the simplex does not as a rule remain rigid. In addition to a shrink step, the NMSearch allows for a contraction, an expansion, and a reflection. The idea is to allow the simplex to deform so it can better follow the gradient of the function being sampled. The algorithm is designed to provide a means whereby the simplex can expand itself along directions of improvement and contract itself opposite areas where improvement is not found. The stopping criterion we use is the one recommended by Nelder and Mead, a standard-deviation test. We have made some adjustments to the algorithm to improve the algrorithm's success near the boundaries of a bounded objective function. For more information, see Adam's Honors Thesis.

The SMDSearch class is based on the algorithm
first developed by
Torczon for execution on a multi-processor machine. The version
included here is adapted for single-processor machines. The main
difference between the SMDSearch algorithm and the other simplex
searches is that, during a reflection step, rather than simply
reflecting the vertex with greatest function value through the
centroid of the other vertices, the Multi-Directional Search instead
reflects *all* vertices through the best *vertex*. As a
result, each iteration of the SMDSearch actually involves two
simplices: a primary simplex and its reflection through the current
best minimizer. The algorithm uses a greedy approach to function
sampling: function values are calculated only until a new minimizer is
found. If a new minimizer is identified in the reflection simplex, the
reflection simplex becomes the new primary simplex with the newly
identified minimizer as its basepoint, and a new reflection simplex is
constructed. If all *2n + 1* points in both primary and
reflection simplices have been evaluated with no improvement found,
the primary simplex shrinks around the basepoint, and a new iteration
is begun, with a smaller simplex. More details are in
Adam's Honors Thesis.

The objective files contain
declarations and user-defined specifications including initial step
length. `objective.cc ` implements the functions declared in
`objective.h`, including `fcn()` and
`Evalf()`. The first of these, `fcn()`, is a wrapper
for `Evalf()`, which uses the Unix fork-exec paradigm to call
the actual function to be minimized. We have provided a sample
function in the source file `shekel.cc`, so the user may become
familiar with this process. Before running the test programs, the
user must compile the shekel program on the same operating system in
which the simplex searches will be compiled. Using `g++`, for
example, the command would be:

`g++ -Wall -g shekel.cc -o shekel`

These test drivers
offer examples of declaring the necessary classes,
running the searches, and getting at some of the data possibilities.
The searches run are simple, and the format is interactive.
If users plan to use our `shekel.cc` file, they should first
compile a binary executable as discussed above. Instructions for
compiling each of the test programs can be found at the top of its source
file.

An example of a run of NMtest is below (the '%' is just the prompt character):

% ./NMtest

SEED=23185

RUNS=3

dim=4

maxCalls=-1

Fname=shekel

Lower bound (space separated)=0 0 0 0

Upper bound (space separated)=9 9 9 9

NMSearch calls=225, Value=-10.5364, TolHit=1, Point=4.00076 4.00056 3.99963 3.99954

SHEKEL FAILED!!!!

NMSearch calls=152, Value=-2.87114, TolHit=1, Point=5.99906 5.99735 5.99828 5.99658

NMSearch calls=160, Value=-10.5364, TolHit=1, Point=4.00073 4.00053 3.99962 3.99956

INITIAL STEP LENGTH = 2

Note that for this function the user must use dim = 4, and should keep
the lower and upper bounds within [0, 10]^4. The random seed must be a
positive integer. The function
evaluation must be printed to standard output. Any other output
statements must be sent either to standard error or to a file. A
value of -1 for maxCalls means that the search will terminate based
only on the refinement of the design, rather than because it has
reached its maximum allowable number of function calls.

Also note that the statement
"SHEKEL FAILED" in the listing above does not indicate that the program is not
working; it just means that the simplex has gone out of bounds at that
point. The algorithm will flip (or otherwise adapt) the simplex to
remedy this.