DownhillSimplex< N, Precision > Class Template Reference
[Function optimization]

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

#include <downhill_simplex.h>

List of all members.

Public Member Functions

template<class Function >
 DownhillSimplex (const Function &func, const Vector< N > &c, Precision spread=1)
template<class Function >
void restart (const Function &func, const Vector< N > &c, Precision spread)
bool finished ()
template<class Function >
void restart (const Function &func, Precision spread)
const Simplexget_simplex () const
const Valuesget_values () const
int get_best () const
int get_worst () const
template<class Function >
void find_next_point (const Function &func)
template<class Function >
bool iterate (const Function &func)

Public Attributes

Precision alpha
Precision rho
Precision gamma
Precision sigma
Precision epsilon
Precision zero_epsilon


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:

This implementation uses:

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;
}

Parameters:
N The dimension of the function to optimize. As usual, the default value of N (-1) indicates that the class is sized at run-time.

Constructor & Destructor Documentation

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

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.

References DownhillSimplex< N, Precision >::alpha, DownhillSimplex< N, Precision >::epsilon, DownhillSimplex< N, Precision >::gamma, DownhillSimplex< N, Precision >::restart(), DownhillSimplex< N, Precision >::rho, DownhillSimplex< N, Precision >::sigma, and DownhillSimplex< N, Precision >::zero_epsilon.


Member Function Documentation

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.

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

References Matrix< Rows, Cols, Precision, Layout >::num_cols(), Matrix< Rows, Cols, Precision, Layout >::num_rows(), and Vector< Size, Precision, Base >::size().

Referenced by DownhillSimplex< N, Precision >::DownhillSimplex(), and DownhillSimplex< N, Precision >::restart().

bool finished (  ) 

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.

References DownhillSimplex< N, Precision >::epsilon, DownhillSimplex< N, Precision >::get_best(), DownhillSimplex< N, Precision >::get_worst(), TooN::norm(), and DownhillSimplex< N, Precision >::zero_epsilon.

Referenced by DownhillSimplex< N, Precision >::iterate().

void restart ( const Function &  func,
Precision  spread 
)

This function resets the simplex around the best current point.

Parameters:
func Functor to minimize.
spread simplex size

References DownhillSimplex< N, Precision >::get_best(), and DownhillSimplex< N, Precision >::restart().

const Simplex& get_simplex (  )  const

Return the simplex.

const Values& get_values (  )  const

Return the score at the vertices.

int get_best (  )  const

int get_worst (  )  const

void find_next_point ( const Function &  func  ) 

bool iterate ( const Function &  func  ) 

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

Parameters:
func Functor to minimize

References DownhillSimplex< N, Precision >::find_next_point(), and DownhillSimplex< N, Precision >::finished().


Member Data Documentation

Precision alpha

Precision rho

Precision gamma

Precision sigma

Precision epsilon

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

Referenced by DownhillSimplex< N, Precision >::DownhillSimplex(), and DownhillSimplex< N, Precision >::finished().

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.

Referenced by DownhillSimplex< N, Precision >::DownhillSimplex(), and DownhillSimplex< N, Precision >::finished().


Generated on Tue Oct 27 16:09:25 2009 for TooN by  doxygen 1.5.9