A class to implement the NelderMead optimization method. More...

#include <NelderMead.hpp>

Inheritance diagram for Unfit::NelderMead:

Public Member Functions
	NelderMead ()

virtual	~NelderMead ()

int	FindMin (GenericCostFunction &CostFunction, std::vector< double > &coordinates) override
	Implements the Nelder-Mead optimization method. More...

void	Reset () override

Public Member Functions inherited from Unfit::GenericOptimizer
	GenericOptimizer ()

virtual	~GenericOptimizer ()

void	ResetGenericOptimizer ()

virtual double	GetCost (std::size_t index=0) const noexcept

virtual bool	GetIsPopulationBased () const noexcept

virtual std::size_t	GetNumberOfIterations () const noexcept

virtual std::size_t	GetNumberOfFunctionEvaluations () const noexcept

virtual std::vector< std::vector< double > >	GetPopulation () const

virtual std::vector< double >	GetSolution (std::size_t index=0) const

virtual void	SetPopulation (const std::vector< std::vector< double >> &population)

Private Types
enum	Operation { Reflected, Expanded, ContractedIn, ContractedOut, Shrunk, Restarted }

Private Member Functions
int	GeneratePopulation (GenericCostFunction &CostFunction, const std::vector< double > &initial_point)
	Generate the initial simplex by accepting a vector which contains the initial guess and the CostFunction to compute costs. More...

void	ComputeCentroid ()

bool	ContractInside (GenericCostFunction &CostFunction)

bool	ContractOutside (GenericCostFunction &CostFunction)

bool	Reflect (GenericCostFunction &CostFunction)

bool	Expand (GenericCostFunction &CostFunction)

bool	Shrink (GenericCostFunction &CostFunction)

bool	IsDegenerate ()

void	InitialiseVectors ()

void	UseAdaptiveParameters ()

void	PrintInitialOutput (double best_cost) const override

void	PrintIterationOutput (double best_cost) const override

int	ProcessFindMin (GenericCostFunction &CostFunction)

int	RegeneratePopulation (GenericCostFunction &CostFunction)

Private Attributes
std::vector< double >	contract_

std::vector< double >	centroid_

std::vector< double >	reflect_

std::vector< double >	expand_

std::size_t	dimensions_

std::size_t	best_vertex_

std::size_t	worst_vertex_

std::size_t	next_worst_vertex_

std::size_t	cost_

double	restart_best_cost_

enum Operation	process_

Friends
class	TestNelderMead

Additional Inherited Members
Public Attributes inherited from Unfit::GenericOptimizer
Unfit::Bounds	bounds

Unfit::Options	options

Protected Member Functions inherited from Unfit::GenericOptimizer
virtual bool	CalculateCost (GenericCostFunction &CostFunction, std::vector< double > &x)

void	GeneratePopulation (GenericCostFunction &CostFunction, std::size_t dimensions)

void	GenerateRandomEngines ()

virtual bool	IsConverged (const std::vector< double > &best_member, std::size_t truncated_index=0) const
	Checks to see if the population has converged. More...

virtual void	PrintFinalOutput () const

virtual void	SortPopulation () noexcept

Protected Attributes inherited from Unfit::GenericOptimizer
std::vector< std::vector< double > >	population_

std::vector< std::mt19937 >	random_engines_

std::atomic< std::size_t >	function_evaluations_

std::atomic< std::size_t >	iterations_

bool	is_population_based_

Detailed Description

A class to implement the NelderMead optimization method.

This class implements the NelderMead optimization method. It requires a cost function (written by the user) and an initial guess of the unknown parameters. It then proceeds to try to find a set of parameters that minimize the cost function.

The inspiration for this implementation was derived from the paper: Implementing the Nelder-Mead simplex algorithm with adaptive parameters, Journal of Computational Optimization and Applications, Fuchang Gao & Lixing Han, 51(1):259-277, 2012

Member Enumeration Documentation

◆ Operation

enum Unfit::NelderMead::Operation

private

Operation contains the various operations that are possible at each iteration of the NelderMead algorithm.

Constructor & Destructor Documentation

◆ NelderMead()

Unfit::NelderMead::NelderMead ( )

The constructor sets all of the parameters to their default values.

◆ ~NelderMead()

virtual Unfit::NelderMead::~NelderMead ( )

inlinevirtual

As we are deriving from this class, the destructor should be virtual. In this case an empty destructor is just fine as we are putting everything into std::vectors which take care of themselves.

Member Function Documentation

◆ ComputeCentroid()

void Unfit::NelderMead::ComputeCentroid ( )

private

Compute the centroid of n good vertices without computing the cost function by averaging the positions of all of the vertices except the vertex with the worst cost.

◆ ContractInside()

bool Unfit::NelderMead::ContractInside ( GenericCostFunction & CostFunction )

private

ContractInside is called by ProcessFindMin. As the name suggests, it performs an inside contraction, which creates a new candidate point for the simplex between the worst point and the centroid. The distance is controlled by the gamma parameter.

contractin = centroid - gamma*(reflect - centroid)

Parameters

CostFunction (input) the function to be implemented

Returns: true = Success
false = Failure. Cannot contract and maintain a valid simplex

◆ ContractOutside()

bool Unfit::NelderMead::ContractOutside ( GenericCostFunction & CostFunction )

private

ContractOutside is called by ProcessFindMin. As the name suggests, it performs an outside contraction, which creates a new candidate point for the simplex between the reflect point and the centroid. The distance is controlled by the gamma parameter.

contractout = centroid + gamma*(reflect - centroid_[i])

Parameters

CostFunction (input) the function to be implemented

Returns: true = Success
false = Failure. Cannot contract and maintain a valid simplex

◆ Expand()

bool Unfit::NelderMead::Expand ( GenericCostFunction & CostFunction )

private

Computes the expanded coordinates and their cost function based on beta

expand = centroid + beta*(reflect - centroid)

Parameters

CostFunction (input) the function specified by the user

Returns: true = Success
false = Failure. Cannot expand and maintain a valid simplex

◆ FindMin()

int Unfit::NelderMead::FindMin	(	GenericCostFunction &	CostFunction,
		std::vector< double > &	coordinates
	)

overridevirtual

Implements the Nelder-Mead optimization method.

This method takes in a cost function (user supplied) and an initial guess for the unknown parameters and uses the Nelder-Mead simplex algorithm to try to find the set of parameters that provides a minimum cost. This is implemented as a nonlinear least squares problem, so the cost will always be >= 0. This is known as a local optimizer, so the results you get will depend on how good the initial guess is.

Intended use: auto rc = object.FindMin(CostFunction, coordinates)

Parameters

CostFunction	A user supplied cost function that returns a vector of residuals.
coordinates	A vector that contains the initial guess (coordinates) of the unknown parameters.

Returns: rc return code; zero upon success, non-zero upon failure.
0 = Success
1 = Max function evaluations reached
2 = Max iteration reached
3 = Optimisation was unable to find a valid simplex
4 = Convergence was achieved but the tolerance(s) were not met
GENERATED SIMPLEX:
-1 = Invalid initial guess (check cost and bounds)
-2 = Unable to generate initial simplex within the bounds
-3 = Initial simplex had has invalid costs
-4 = Number of coordinates is zero
USER SUPPLIED SIMPLEX:
-1 = Empty population
-2 = Empty population member(s)
-3 = Population is the wrong size (vertices != dimensions + 1)
-4 = Vertex lengths are inconsistent
-5 = One or more vertices has invalid costs

Implements Unfit::GenericOptimizer.

◆ GeneratePopulation()

int Unfit::NelderMead::GeneratePopulation	(	GenericCostFunction &	CostFunction,
		const std::vector< double > &	initial_point
	)

private

Generate the initial simplex by accepting a vector which contains the initial guess and the CostFunction to compute costs.

The initial simplex is generated following L.Pfeffer at Stanford. The initial simplex is scaled with respect to the characteristic lengths of the problem. The scaling is defined with respect to the initial point. The method proceeds by defining the scale. Scale : non-zero scale : 0.05 zero scale : 0.00025

The first vertex is always the initial guess.

For the subsequent vertices, we examine ith coordinate and if nth coordinate is zero, scale it up by zero scale while keeping the other coordinates constant. The new set of coordinates will be the nth vertex.

If nth coordinate is non-zero, scale the value up by non-zero scale while keeping the other coordinates constant. The new set of coordinates will be the nth vertex.

If the coordinates cross a bound, the algorithm tries to find a valid simplex if it can. If the cost of any of the vertices in a geometrically valid simplex are NAN or INF then the algorithm is considered to have failed.

NOTES: Vertices of the initial simplex are not sorted under this function. Generated simplex is stored in the 2D vector vertices_

Parameters

CostFunction	(input) the function to be implemented
initial_point	(input) the initial guess point for the FindMin function

Returns: 0 = Success.
1 = Failure. Invalid initial point
2 = Failure. Bounds are too close together to form a simplex
3 = Failure. Invalid vertex costs in the initial simplex

◆ InitialiseVectors()

void Unfit::NelderMead::InitialiseVectors ( )

private

Initialise the working vectors vertices_, contract_, centroid_, reflect_, expand_ to size depending on the dimension of the problem.

◆ IsDegenerate()

bool Unfit::NelderMead::IsDegenerate ( )

private

Check if the vertices in the simplex have become colinear. If they have the simplex is considered degenerate.

Returns: true Simplex is degenerate
false Simplex is not degenerate

◆ PrintInitialOutput()

void Unfit::NelderMead::PrintInitialOutput ( double best_cost ) const

overrideprivatevirtual

Prints the column headers relating to iteration by iteration output to the screen if the output level has been set to be >= 1.

Parameters

best_cost The best cost after the initial setup

Reimplemented from Unfit::GenericOptimizer.

◆ PrintIterationOutput()

void Unfit::NelderMead::PrintIterationOutput ( double best_cost ) const

overrideprivatevirtual

At each iteration, prints nothing if the output level is zero, the iteration number if the output level is one, and the iteration number plus the number of function evaluations and the best cost if the output level is greater than one, along with the operation from the last iteration.

Parameters

best_cost The best cost after the latest iteration

Reimplemented from Unfit::GenericOptimizer.

◆ ProcessFindMin()

int Unfit::NelderMead::ProcessFindMin ( GenericCostFunction & CostFunction )

private

Here is the main implementation of the Nelder Mead simplex algorithm to which the FindMin methods are a front-end.

Parameters

CostFunction (input) a user function

Returns: rc return code; zero upon success, non-zero upon failure.
0 = Success
1 = Max function evaluations reached
2 = Max iteration reached
3 = Optimisation was unable to find a valid simplex
4 = Convergence was achieved but the tolerance(s) were not met

◆ Reflect()

bool Unfit::NelderMead::Reflect ( GenericCostFunction & CostFunction )

private

Compute the centroid and the reflection point and evaluate the value of R based on alpha (alpha>0). This computes the centroid of best and good vertices, and get the reflected point with respect to the worst vertex and alpha.

reflect = centroid_ + alpha*(centroid_ - worst)

Parameters

CostFunction (input) the function to be implemented

Returns: true = Success
false = Failure. Cannot reflect and maintain a valid simplex

◆ RegeneratePopulation()

int Unfit::NelderMead::RegeneratePopulation ( GenericCostFunction & CostFunction )

private

Creates a new simplex around the best vertex by making a call to GeneratePopulation internally.

Parameters

CostFunction (input) the function to be implemented

Returns: 0 = Success
1 = Unable to generate valid simplex

◆ Reset()

void Unfit::NelderMead::Reset ( )

overridevirtual

Resets the variables to default values of NelderMead. Equivalent to destroying the object and creating a new one.

Implements Unfit::GenericOptimizer.

◆ Shrink()

bool Unfit::NelderMead::Shrink ( GenericCostFunction & CostFunction )

private

Shrink shifts Good and Worst vertices towards Best vertex It shifts all the vertices except the Best vertex, based on delta

Parameters

CostFunction (input) the function to be implemented

Returns: true = Success
false = Failure. Cannot shrink and maintain a valid simplex

◆ UseAdaptiveParameters()

void Unfit::NelderMead::UseAdaptiveParameters ( )

private

Set the parameters to be used based on the number of dimensions

Friends And Related Function Documentation

◆ TestNelderMead

friend class TestNelderMead

friend

For unit testing purposes only

Member Data Documentation

◆ best_vertex_

std::size_t Unfit::NelderMead::best_vertex_

private

The index of the best vertex

◆ centroid_

std::vector<double> Unfit::NelderMead::centroid_

private

Vector to store the centroid

◆ contract_

std::vector<double> Unfit::NelderMead::contract_

private

Vector to store the contracted point

◆ cost_

std::size_t Unfit::NelderMead::cost_

private

The index of the cost of each vertex

◆ dimensions_

std::size_t Unfit::NelderMead::dimensions_

private

Variable to store the number of dimensions

◆ expand_

std::vector<double> Unfit::NelderMead::expand_

private

Vector to store the expanded point

◆ next_worst_vertex_

std::size_t Unfit::NelderMead::next_worst_vertex_

private

The index of the next-to-worst vertex

◆ process_

enum Operation Unfit::NelderMead::process_

private

Enum data type to store the operation executed

◆ reflect_

std::vector<double> Unfit::NelderMead::reflect_

private

Vector to store the reflected point

◆ restart_best_cost_

double Unfit::NelderMead::restart_best_cost_

private

Variable to store the best cost before a restart

◆ worst_vertex_

std::size_t Unfit::NelderMead::worst_vertex_

private

The index of the worst vertex

The documentation for this class was generated from the following files:

include/NelderMead.hpp
src/NelderMead.cpp

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ Operation

Constructor & Destructor Documentation

◆ NelderMead()

◆ ~NelderMead()

Member Function Documentation

◆ ComputeCentroid()

◆ ContractInside()

◆ ContractOutside()

◆ Expand()

◆ FindMin()

◆ GeneratePopulation()

◆ InitialiseVectors()

◆ IsDegenerate()

◆ PrintInitialOutput()

◆ PrintIterationOutput()

◆ ProcessFindMin()

◆ Reflect()

◆ RegeneratePopulation()

◆ Reset()

◆ Shrink()

◆ UseAdaptiveParameters()

Friends And Related Function Documentation

◆ TestNelderMead

Member Data Documentation

◆ best_vertex_

◆ centroid_

◆ contract_

◆ cost_

◆ dimensions_

◆ expand_

◆ next_worst_vertex_

◆ process_

◆ reflect_

◆ restart_best_cost_

◆ worst_vertex_