This is an implementation of the Downhill Simplex (Nelder & Mead, 1965) algorithm. More...

#include <downhill_simplex.h>

Collaboration diagram for TooN::DownhillSimplex< N, Precision >:

Public Member Functions
template<class Function >
	DownhillSimplex (const Function &func, const Vector< N > &c, Precision spread=1)
	Initialize the DownhillSimplex class. More...

template<class Function >
void	restart (const Function &func, const Vector< N > &c, Precision spread)
	This function sets up the simplex around, with one point at c and the remaining points are made by moving by spread along each axis aligned unit vector. More...

bool	finished ()
	Check to see it iteration should stop. More...

template<class Function >
void	restart (const Function &func, Precision spread)
	This function resets the simplex around the best current point. More...

const Simplex &	get_simplex () const
	Return the simplex.

const Values &	get_values () const
	Return the score at the vertices.

int	get_best () const
	Get the index of the best vertex.

int	get_worst () const
	Get the index of the worst vertex.

template<class Function >
void	find_next_point (const Function &func)
	Perform one iteration of the downhill Simplex algorithm. More...

template<class Function >
bool	iterate (const Function &func)
	Perform one iteration of the downhill Simplex algorithm, and return the result of not DownhillSimplex::finished. More...

Public Attributes
Precision	alpha
	Reflected size. Defaults to 1.

Precision	rho
	Expansion ratio. Defaults to 2.

Precision	gamma
	Contraction ratio. Defaults to .5.

Precision	sigma
	Shrink ratio. Defaults to .5.

Precision	epsilon
	Tolerance used to determine if the optimization is complete. Defaults to square root of machine precision.

Precision	zero_epsilon
	Additive term in tolerance to prevent excessive iterations if $x_\mathrm{optimal} = 0$. Known as `ZEPS` in numerical recipies. Defaults to 1e-20.

Detailed Description

template<int N = -1, typename Precision = double>
class TooN::DownhillSimplex< N, Precision >

This is an implementation of the Downhill Simplex (Nelder & Mead, 1965) algorithm.

This particular instance will minimize a given function.

The function maintains $N+1$ points for a $N$ dimensional function, $f$

At each iteration, the following algorithm is performed:

Find the worst (largest) point, $x_w$.
Find the centroid of the remaining points, $x_0$.
Let $v = x_0 - x_w$
Compute a reflected point, $ x_r = x_0 + \alpha v$
If $f(x_r)$ is better than the best point
- Expand the simplex by extending the reflection to $x_e = x_0 + \rho \alpha v $
- Replace $x_w$ with the best point of $x_e$, and $x_r$.
Else, if $f(x_r)$ is between the best and second-worst point
- Replace $x_w$ with $x_r$.
Else, if $f(x_r)$ is better than $x_w$
- Contract the simplex by computing $x_c = x_0 + \gamma v$
- If $f(x_c) < f(x_r)$
  - Replace $x_w$ with $x_c$.
If $x_w$ has not been replaced, then shrink the simplex by a factor of $\sigma$ around the best point.

This implementation uses:

$\alpha = 1$
$\rho = 2$
$\gamma = 1/2$
$\sigma = 1/2$

Example usage:

#include <TooN/optimization/downhill_simplex.h>
using namespace std;
using namespace TooN;
double sq(double x)
{
    return x*x;
}
double Rosenbrock(const Vector<2>& v)
{
        return sq(1 - v[0]) + 100 * sq(v[1] - sq(v[0]));
}
int main()
{
        Vector<2> starting_point = makeVector( -1, 1);
        DownhillSimplex<2> dh_fixed(Rosenbrock, starting_point, 1);
        while(dh_fixed.iterate(Rosenbrock))
        {
            cout << dh.get_values()[dh.get_best()] << endl;
        }
        
        cout << dh_fixed.get_simplex()[dh_fixed.get_best()] << endl;
}

@param   N The dimension of the function to optimize. As usual, the default value of <i>N</i> (-1) indicates
         that the class is sized at run-time.

Constructor & Destructor Documentation

◆ DownhillSimplex()

template<int N = -1, typename Precision = double>

template<class Function >

TooN::DownhillSimplex< N, Precision >::DownhillSimplex	(	const Function &	func,
		const Vector< N > &	c,
		Precision	spread = `1`
	)

inline

Initialize the DownhillSimplex class.

The simplex is automatically generated. One point is at c, the remaining points are made by moving c by spread along each axis aligned unit vector.

Parameters

func	Functor to minimize.
c	Origin of the initial simplex. The dimension of this vector is used to determine the dimension of the run-time sized version.
spread	Size of the initial simplex.

Member Function Documentation

◆ find_next_point()

template<int N = -1, typename Precision = double>

template<class Function >

void TooN::DownhillSimplex< N, Precision >::find_next_point ( const Function & func )

inline

Perform one iteration of the downhill Simplex algorithm.

Parameters

func	Functor to minimize

◆ finished()

template<int N = -1, typename Precision = double>

bool TooN::DownhillSimplex< N, Precision >::finished ( )

inline

Check to see it iteration should stop.

You probably do not want to use this function. See iterate() instead. This function updates nothing. The termination criterion is that the simplex span (distancve between the best and worst vertices) is small compared to the scale or small overall.

◆ iterate()

template<int N = -1, typename Precision = double>

template<class Function >

bool TooN::DownhillSimplex< N, Precision >::iterate ( const Function & func )

inline

Perform one iteration of the downhill Simplex algorithm, and return the result of not DownhillSimplex::finished.

Parameters

func	Functor to minimize

◆ restart() [1/2]

template<int N = -1, typename Precision = double>

template<class Function >

void TooN::DownhillSimplex< N, Precision >::restart	(	const Function &	func,
		const Vector< N > &	c,
		Precision	spread
	)

inline

This function sets up the simplex around, with one point at c and the remaining points are made by moving by spread along each axis aligned unit vector.

Parameters

func	Functor to minimize.
c	c corner point of the simplex
spread	spread simplex size

◆ restart() [2/2]

template<int N = -1, typename Precision = double>

template<class Function >

void TooN::DownhillSimplex< N, Precision >::restart	(	const Function &	func,
		Precision	spread
	)

inline

This function resets the simplex around the best current point.

Parameters

func	Functor to minimize.
spread	simplex size

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

TooN/optimization/downhill_simplex.h

Public Member Functions

Public Attributes

Detailed Description

template<int N = -1, typename Precision = double> class TooN::DownhillSimplex< N, Precision >

Constructor & Destructor Documentation

◆ DownhillSimplex()

Member Function Documentation

◆ find_next_point()

◆ finished()

◆ iterate()

◆ restart() [1/2]

◆ restart() [2/2]

template<int N = -1, typename Precision = double>
class TooN::DownhillSimplex< N, Precision >