NMSearch

class NMSearch : public SimplexSearch

NMSearch class

Inheritance:

Public

constructors and destructors

NMSearch(long dim, Vector<double> &startPoint ): Constructor
NMSearch(long dim, Vector<double> &startPoint, double sig, Vector<double> &lengths): Constructor which allows shrinking coefficient initialization and specification of starting_edgeLengths
NMSearch(long dim, Vector<double> &startPoint, double NewSigma, double NewAlpha, double NewBeta, double NewGamma): Constructor which allows initialization of all four coefficients
NMSearch(const NMSearch& Original): Copy constructor
NMSearch(long dim, Vector<double> &startPoint, double NewSigma, double NewAlpha, double NewBeta, double NewGamma, double startStep, double stopStep, void (*objective)(long vars, Vector<double> &x, double & func, bool& flag, void* an_obj), void * input_obj): Special constructor using void function and object pointers
~NMSearch(): Destructor

other public methods

NMSearch& operator= (const NMSearch& A): Overloaded assignment operator
void ReadInFile(istream& fp): May also pass cin as input stream if desired
void ChooseRightSimplex(): Specifies that a right simplex will be used
void ChooseRegularSimplex(): Specifies that a regular simplex will be used
void BeginSearch(): This method begins the actual searching
void SetAlpha(double newAlpha): Sets the reflection coefficient
double GetAlpha(): Returns the value of alpha, the reflection coefficient
void SetBeta(double newBeta): Sets the contraction coefficient
double GetBeta(): Returns the value of beta, the contraction coefficient
void SetGamma(double newGamma): Sets the expansion coefficient
double GetGamma(): Returns the value of gamma, the expansion coefficient
double GetDelta(): Overloaded to return NMdelta, in this search overloaded to equal the mean of all the edgelengths of the simplex

Protected Fields
double alpha: The reflection coefficient
double beta: The contraction coefficient
double gamma: The expansion coefficient
long maxIndex: The index of point generating max f(x)
Vector <double> * reflectionPt: The reflection point
double reflectionPtValue: The value of f(reflectionPt)
Vector <double> * expansionPt: The expansion point
double expansionPtValue: The value of f(expansionPt)
Vector <double> * contractionPt: The contraction point
double contractionPtValue: The value of f(contractionPt)
double maxPrimePtValue: min(f(maxIndexPoint),reflectionPtValue)
long maxPrimePtId: Set by FindContractionPt() and used in ExploratoryMoves() to branch in possibility 3
double NMdelta: Analogous to delta in the other searches, but here it is the mean of the lengths of all the edges of the simplex

Protected Methods
void ExploratoryMoves(): This method does the actual work of the search
void InitRegSimplex(): Deletes any existing simplex and replaces it with a regular triangular simplex
void InitRightSimplex(): Deletes any existing simplex and replaces it with a right-angle simplex
void InitGeneralSimplex(const Matrix<double> *plex): Used to implement all simplex initializations
bool Stop(): Returns true if the stopping criteria have been satisfied
void CalculateNMDelta(): Calculates NMdelta, the mean of the lengths of the edges of the simplex
void CopySearch(const NMSearch & Original): Used to implement the overloaded assignment operator
void FindMinMaxIndices(): Sets minIndex to the simplex index of the point which generates the lowest value of f(x) and sets maxIndex to the simplex index of the point which generates the highest value of f(x)
long SecondHighestPtIndex(): Returns simplex index of the point which generates the second highest value of f(x)
void FindCentroid(): Finds the centroid
void FindReflectionPt(): Finds the reflection point and sets its f(x) value
void FindExpansionPt(): Finds the expansion point and sets its f(x) value
void FindContractionPt(): Finds the contraction point and sets its f(x) value

Inherited from SimplexSearch:

Public Fields
static const int def_Length

Public
Constructors and destructor

SimplexSearch(long dim, Vector<double> &startPoint)
Constructor
SimplexSearch(const SimplexSearch& Original)
Copy constructor
SimplexSearch(long dim, Vector<double> &startPoint, double sig)
Constructor which allows shrinking coefficient initialization
SimplexSearch(long dim, Vector<double> &startPoint, double sig, const Vector<double> &lengths)
Constructor which allows shrinking coefficient initialization and specification of starting_edgeLengths
SimplexSearch(long dim, Vector<double> &startPoint, double startStep, double stopStep, void (*objective)(long vars, Vector<double> &x, double & func, bool& flag, void* an_obj), void * input_obj)
Special constructor using void function and object pointers
Other public methods

virtual SimplexSearch& operator= (const SimplexSearch& A)
Overloaded assignment operator
virtual void BeginSearch()
This method begins the actual searching in the concrete classes
virtual void ChooseRegularSimplex()
Allows the user to choose a regular simplex for the search
virtual void ChooseRightSimplex()
Virtual void function, unimplemented in this absstract base class
virtual void ReadInFile(istream& fp)
Pure virtual in this abstract base class
virtual void PrintDesign() const
Prints out the simplex points by row, their corresponding f(x) values, and the number of function calls thus far
Accessor and mutator methods

long GetReplacementIndex() const
Returns replacementIndex
void SetStartingEdgeLengths(const Vector<double> & lengths)
Sets starting_edgeLengths to equal lengths
void GetStartingEdgeLengths(Vector<double> & lengths)
Assigns the input Vector lengths the values of the member field starting_edgeLengths
void SetSigma(double newSigma)
Allows the user to set a new value for the shrinking coefficient
double GetSigma()
Returns the value of sigma
void GetCurrentSimplexValues(double* &simValues) const
performs a deep copy of the simplexValues array to a double pointer points to a newly allocated chunk of memory upon return USER SHOULD PASS JUST A NULL POINTER, WITHOUT PREALLOCATED MEMORY
int GetTolHit() const
Returns toleranceHit, which indicates whether the simplex size has refined down to the value of stoppingStepLength
long GetMinIndex() const
Returns minIndex
void GetCentroid(Vector<double>* &troid)
Upon return the input Vector* troid will point to a newly allocated Vector of doubles representing the centroid of the simplex
double GetDelta()
Returns delta, the length of the longest simplex edge
bool Is_Stop_on_std() const
Returns value of the Stop_on_std field
void Set_Stop_on_std()
Allows user to specify that the standard Nelder-Mead stopping criterion will be used
void Set_Stop_on_delta()
Allows users to specify that the search will terminated based on delta
protected methods

virtual void ExploratoryMoves()
Pure virtual in this abstract base class
virtual void CalculateFunctionValue(long index)
Finds the f(x) value for the simplex point indexed at index and replaces the proper value in simplexValues
virtual bool Stop()
returns true if the stopping criteria have been satisfied
virtual void CopySearch(const SimplexSearch & Original)
Used to implement the overloaded assignment operator
virtual void Initialize_Right(Matrix<double> *plex)
Inititializes a right simplex
virtual void Initialize_Regular(Matrix<double> *plex)
Inititializes a regular simplex, following an algorithm given by Jacoby, Kowalik, and Pizzo in "Iterative Methods for Nonlinear Optimization Problems," Prentice-Hall (1972)
virtual void InitGeneralSimplex(const Matrix<double> *plex)
Deletes any existing design matrix and replaces it with one pointed to by plex
virtual void SetReplacementIndex(long newIndex)
Sets replacementIndex to the value of newIndex
virtual void FindCentroid()
Finds the centroid and assigns the value to the member field centroid
virtual void ShrinkSimplex()
Goes through the simplex and reduces the lengths of the edges adjacent to the best vertex
virtual void ReplaceSimplexPoint(long index, const Vector<double>& newPoint)
Replaces simplex point indexed at index with parameter newPoint
Protected fields

double* simplexValues
f(x) values of the points corresponding to the rows of the design matrix
Vector <double> * starting_edgeLengths
The edgelengths of the simplex that will be represented by the design matrix
double sigma
The shrinking coefficient
long minIndex
Index of point generating min f(x)
long replacementIndex
Index of point to be replaced
Vector <double> * centroid
The current centroid
int toleranceHit
Flag to indicate the reason for stopping the search
bool SimplexSpecified
Flag to indicate whether a specific simplex type has been chosen
bool Stop_on_std
Flag to indicate that the user has chosen (where available) to use the standard-deviation (i
double delta
Named to recall the "delta" of the pattern searches, this is generally the length of (at the start) the longest edge of the simplex; it is used for the stopping test where Stop_on_std is false (as it is by default)
Vector <double> * scratch
The two scratch vectors are simply extra storage space to be used by methods that require a vector of size = dimensions

Inherited from DirectSearch:

Public Fields
static const long NO_MAX

Public
Other initialization methods

virtual void ReadInFile(istream & fp)
Reads the design in from a file supplied by the user
virtual void CleanSlate(long dim, Vector<double> & startPoint)
Reinitializes values in order to reuse the same search object
virtual void CleanSlate(long dim, Vector<double> &startPoint, double stopStep, void (*objective)(long vars, Vector<double> &x, double &func, bool &flag, void* an_obj), void * input_obj)
overloaded version of CleanSlate using void function and object pointers
void InitializeDesign(const Matrix<double> *designPtr)
Deletes any existing pattern and replaces it with the one pointed to by designPtr
virtual void PrintDesign() const
Prints out search information
Search method

virtual void BeginSearch()
BeginSearch() is an unimplemented virtual void method in the abstract base classes
Accessors and Mutators

long GetFunctionCalls() const
Returns number of objective function evaluations so far
void SetFunctionCalls(long newCalls)
Sets number of function calls already used--useful for times when you are using multiple searches for the same optimization; for example, if you wanted to do 100 function calls worth of SMDSearch followed by 100 calls (max) of HJSearch
int GetID() const
Returns the ID Number of the search
void GetMinPoint(Vector<double> & minimum) const
Retrieves the minimum point and assigns it to minimum The vector minimum should be of the correct dimension
void SetMinPoint(Vector<double> & minimum) const
Resets minPoint to the point represented by the input parameter minimum
void GetMinVal(double & value) const
Retrieves the best objective function value found thus far
void SetMinVal(double & value)
Resets the minimum value to the value of the input parameter
long GetDimension() const
Returns the dimension of the problem
long GetMaxCalls() const
Returns the number of function calls in the budget; if the value is equal to NO_MAX, will terminate based only on refinement of the design
void SetMaxCalls(long calls)
Use to set a function call budget; by default set to the value of NO_MAX, which indicates no budget, in which case the search will terminate based only upon grid refinement
void SetMaxCallsExact(long calls)
Sets maxCalls to the value of calls, and sets exact_count to true, so search will terminate precisely when the call budget runs out
Matrix <double> * GetDesign()
Returns a pointer to a matrix initialized from the design matrix
void CopyDesign(Matrix<double>* &designPtr) const
Deep copy of the pattern to a Matrix pointer
double GetStoppingStepLength() const
Returns stoppingStepLength, the smallest step length allowed in the search
void SetStoppingStepLength(double len)
Sets stoppingStepLength, the smallest step length allowed in the search, to the value of the input parameter
virtual void SetExact()
Allows the user to specify that the search will terminate precicely upon completion of maxCalls number of function calls
virtual void SetInexact()
Allows the user to specify that the search will terminate upon completion of roughly maxCalls number of function calls, but only after a pattern decrease or "shrink" step
virtual bool IsExact()
Returns the value of exact_count(q

Protected Fields
Matrix <double> * design
long dimension
Vector <double> * minPoint
double minValue
long functionCalls
long maxCalls
double stoppingStepLength
void* some_object
bool exact_count
int IDnumber

Protected Methods
void fcnCall(long n, Vector<double> &x, double & f, bool& flag, void * nothing)
bool BreakOnExact()
void (*fcn_name)(long dim, Vector<double> &x, double & function, bool & success, void* an_object)

Documentation

NMSearch class. A simplex search using the method described by Nelder and Mead.

constructors and destructors

NMSearch(long dim, Vector<double> &startPoint )
Constructor. This constructor has two parameters. Other data members will be set to default values, as follows. This is of course in addition to assignments and initializations made in DirectSearch and SimplexSearch classes.

alpha = 1.0;
beta = 0.5;
gamma = 2.0;
memory is allocated for fields reflectionPt, expansionPt, and contractionPt.
IDnumber = 3200

Parameters:
dim - the dimension of the problem
startpoint - the start point for the search. This will be initialized as the minPoint.

NMSearch(long dim, Vector<double> &startPoint, double sig, Vector<double> &lengths)
Constructor which allows shrinking coefficient initialization and specification of starting_edgeLengths. sigma will be set to the value of sig by the SimplexSearch constructor with the same signature, and starting_edgeLengths will be initialized from lengths. Other fields will be assigned as in NMSearch(long dim, Vector<double> &startPoint).

Parameters:
dim - the dimension of the problem.
startpoint - the start point for the search. This will be initialized as the minPoint.
sig - the user-defined value for sigma, the shrinking coefficient.
lengths - reference to a Vector of doubles representing the desired edgelengths of the simplex.

NMSearch(long dim, Vector<double> &startPoint, double NewSigma, double NewAlpha, double NewBeta, double NewGamma)
Constructor which allows initialization of all four coefficients. sigma will be set to the value of NewSigma by the SimplexSearch constructor with the same signature, and the other coefficients will be initialized here. Other fields will be assigned as in NMSearch(long dim, Vector<double> &startPoint).

Parameters:
dim - the dimension of the problem.
startpoint - the start point for the search. This will be initialized as the minPoint.
NewSigma - the user-defined value for sigma, the shrinking coefficient.
NewAlpha - the user-defined value for alpha, the reflection coefficient.
NewBeta - the user-defined value for beta, the contraction coefficient.
NewGamma - the user-defined value for gamma, the expansion coefficient.

NMSearch(const NMSearch& Original)
Copy constructor
Parameters:
Original - a reference to the object from which to construct *this

NMSearch(long dim, Vector<double> &startPoint, double NewSigma, double NewAlpha, double NewBeta, double NewGamma, double startStep, double stopStep, void (*objective)(long vars, Vector<double> &x, double & func, bool& flag, void* an_obj), void * input_obj)
Special constructor using void function and object pointers. The objective function can be sent in as the fourth parameter here; the last parameter is used for any other information that may be necessary; it is used in MAPS, for example, to send in an object from an outside class. Usually, though, the final parameter will simply be set to NULL.
This constructor takes ten input parameters. The arguments dim, startPoint, startStep, stopStep, objective, and input_obj are sent to one of the SimplexSearch constructors for assignment; NewSigma, NewAlpha, NewBeta, and NewGamma are assigned in this constructor.Other fields are set by default as in SHHSearch(long dim, Vector<double> &startPoint).

Parameters:
dim - the dimension of the problem.
startPoint - a Vector of doubles, the starting point for the search.
NewSigma - the user-defined value for sigma, the shrinking coefficient.
NewAlpha - the user-defined value for alpha, the reflection coefficient.
NewBeta - the user-defined value for beta, the contraction coefficient.
NewGamma - the user-defined value for gamma, the expansion coefficient.
startStep - will be used as the edge length of a fixed-length right simplex.
stopStep - the stopping step length for the search
objective - a pointer to the function to be minimized
input_obj - used to send additional data as needed--will normally be set to NULL.

~NMSearch()
Destructor

other public methods

NMSearch& operator= (const NMSearch& A)
Overloaded assignment operator
Returns:
NMSearch&
Parameters:
A - the search to be assigned to *this.

void ReadInFile(istream& fp)
May also pass cin as input stream if desired. input the values of each trial point. NOTE: THIS FUNCTION WILL ONLY ACCEPT n+1 POINTS
functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED.
Returns:
void
Parameters:
fp - reference to an input stream.

void ChooseRightSimplex()
Specifies that a right simplex will be used
Returns:
void

void ChooseRegularSimplex()
Specifies that a regular simplex will be used
Returns:
void

void BeginSearch()
This method begins the actual searching.
Returns:
void

void SetAlpha(double newAlpha)
Sets the reflection coefficient
Returns:
void
Parameters:
newAlpha - the new value for alpha

double GetAlpha()
Returns the value of alpha, the reflection coefficient
Returns:
double

void SetBeta(double newBeta)
Sets the contraction coefficient
Returns:
void
Parameters:
newBeta - the new value for Beta

double GetBeta()
Returns the value of beta, the contraction coefficient
Returns:
double

void SetGamma(double newGamma)
Sets the expansion coefficient
Returns:
void
Parameters:
newGamma - the new value for Gamma

double GetGamma()
Returns the value of gamma, the expansion coefficient
Returns:
double

double GetDelta()
Overloaded to return NMdelta, in this search overloaded to equal the mean of all the edgelengths of the simplex
Returns:
double

void ExploratoryMoves()

This method does the actual work of the search. It uses the Nelder Mead algorithm to find the function minimum.

Returns:: void

void InitRegSimplex()

Deletes any existing simplex and replaces it with a regular triangular simplex.

minPoint points to a point that will be the "origin" of the simplex points (it will be a part of the simplex) starting_edgeLengths[0] is the length of each edge of the "triangle."

functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED.

Returns:: void
Parameters:: plex - pointer to a Matrix of doubles representing a simplex.

void InitRightSimplex()

Deletes any existing simplex and replaces it with a right-angle simplex.

starting_edgeLengths points to an array of n doubles, where n is the dimension of the given search. x_1 will then be located a distance of edgeLengths[0] away from the basepoint along the the x_1 axis, x_2 is edgeLengths[1] away on the x_2 axis, etc.

functionCalls is reset to 0 and ALL FUNCTION VALUES ARE CALCULATED.