Template based implementation for the Downhill Simplex Optimiztation method. More...

#include <SimplexOptimizer.h>

Inheritance diagram for icl::math::SimplexOptimizer< T, Vector >:

Public Types
typedef utils::Function< T, const Vector & >	error_function
	error function type that is used
typedef SimplexOptimizationResult< T, Vector >	Result
typedef utils::Function< void, const Result & >	iteration_callback
Public Member Functions
	SimplexOptimizer (error_function f, int dim, int iterations=1E5, T minError=1.0E-10, T minDelta=1.0E-10, T a=1.0, T b=1.0, T g=0.5, T h=0.5)
	creates a new instance with given parameters
void	setDim (int dim)
	sets the optimizers dimension (note, that usually the error function must be changed then as well)
void	setA (T a)
	sets the reflection factor
void	setB (T b)
	sets the extenxion factor
void	setG (T g)
	sets the contraction factor
void	setH (T h)
	sets the multiple contraction factor
void	setIterations (int iterations)
	sets the maximum iteration termination criterion
void	setMinError (T minError)
	sets the minimum error termination criterion
void	setMinDelta (T minDelta)
	sets the minimum delta termination criterion
void	setErrorFunction (error_function f)
	sets the error function
int	getDim () const
	returns the data dimesions
T	getA () const
	returns the reflection factor
T	getB () const
	returns the extension factor
T	getG () const
	returns the contraction factor
T	getH () const
	returns the multiple contraction factor
int	getIterations () const
	returns the maximum iteration termination criterion
T	getMinError () const
	returns the minimum error termination criterion
T	getMinDelta () const
	returns the minimum delta termination criterion
error_function	getErrorFunction () const
	returns the curren error function
void	setIterationCallback (const iteration_callback &cb)
	sets a callback function, that is called after every iteration step
Result	optimize (const Vector &init)
	runs an optimization using internal parameters starting at given input vector
Result	optimize (const std::vector< Vector > &init)
	rens an optimization using internal parameters using the given initial simplex
Static Public Member Functions
static std::vector< Vector >	createDefaultSimplex (const Vector &init)
	create a default simplex structure
Private Attributes
Data *	m_data
	internal data structure

Detailed Description

template<class T, class Vector = DynColVector<T>>
class icl::math::SimplexOptimizer< T, Vector >

Template based implementation for the Downhill Simplex Optimiztation method.

Downhill Simplex Optimiztation Algorithm

Here, we give a very short pseudo code overview

        input: start position s (in R^D), 
        constants: MAX_ITERATIONS, MIN_ERROR, MIN_DELTA, A, B, G, H

        error function: f: R^D -> R
        S <- R+1 simplex nodes (R[i]=s, R[i][i] = S[i]*1.1, or given)
        F <- R+1 function values F[i] = f(S[i])

        for i=1 to MAX_ITERATIONS
          best <- min_idx(F)

          if F(best) < MIN_ERROR
            break
          endif

          worst <- max_idx(F)
          worst2 <- max_idx(F \ F[worst]) # 2nd worst point

          # find the reflection point xg and data center c
          xg <- sum(S \ S[worst])
          c <- xg + S[worst]
          xg = xg / D

          # break if error could not be decreased significantly
          if (i>0) and (|c-c_old| < MIN_DELTA)
            break
          else
            c_old <- c
          endif

          # get reflection vector xr using factor A
          xr = xg + A (xg - S[worst])
          fxr = f(xr)

          if F[best] <= fxr <= F[worst2]
            # proceed using the reflection
            S[worst] <- xr
            F[worst] <- fxr
          else if fxr < F[best]
            # try an expansion vector xe using factor B
            xe <- xr + B (xr - xg)
            fxe <- f(xe)
            if fxe < fxr
               # use the extension
               S[worst] <- xe
               F[worst] <- fxe
            else
               # use the reflection
               S[worst] <- xr
               F[worst] <- fxr
            endif
          else # fxr > F[worst2]
            # apply contraction xc using constant G
            xc <- xg + G (S[worst] - xg)
            fxc = f(xc)
            if fxc < F[worst]
              # use contraction
              S[worst] = xc
              F[worst] = fxc
            else{ 
              # apply multiple contraction using constant H
              forall j in [0 .. DIM] \ best
                 S[j] = S[best] + H (S[j] - S[best])
                 F[j] = f(S[j])
              endforall
            endif
          endif
        endfor
        return { S[best], F[best], i, S }

Explicit Instantiation

The class template is instantated explicitly for all common float and double vector types:

icl::DynColVector<float> and icl::DynColVector<double>
icl::DynRowVector<float> and icl::DynRowVector<double>
icl::DynMatrix<float> and icl::DynMatrix<double> (the entries are used linearily)
std::vector<float> and std::vector<double>
FixedRowVector<float,D> and FixedRowVector<double,D> where D is
FixedColVector<float,D> and FixedColVector<double,D> where D is 2,3,4,5,6
FixedMatrix<float,D,1> and FixedMatrix<double,D,1> where D is 2,3,4,5,6
FixedMatrix<float,1,D> and FixedMatrix<double,1,D> where D is 2,3,4,5,6

Demo Location

There are two graphical demos located in the ICLGeom-package due to their dependencies to 2D/3D rendering