vec_math
Class Amoeba

java.lang.Object
  vec_math.Amoeba

Direct Known Subclasses:

LeastFourier.FourierAmoeba

public class Amoeba
extends Object

An amoeba is a simplex method for finding (local) minimas of a multi-dimensional function. It is slow, but very robust. Based on the algorithm's in Numerical Recipes in C, p.408ff. For function whose evaluation might introduce some noise, convergence will never be achieved. Thus, a setNoiseLevel(double) is introduced that relaxes the tolerance criterium a little bit as the offset reaches the noise level. There is no literature I'm aware off on these matters, thus we have an ad-hoc approach: In the presence of noise stop the optimization when either the diameter of the simplex is smaller then the noise level or if the tolerance level falls below the random noise level.

Nested Class Summary

static class

Amoeba.Test Class for testing the amoeba.

Field Summary

private double	chimin Smalles value of the function ever encountered.
private double	dchi Smalles decrease of the function ever encountered.
static int	DEFCRAWL
static int	DEFDIMCRAWL
static int	DEFMAXCRAWL The default maximum number of crawl tries.
static double	DEFTOLERANCE Default tolerance level.
private Multidimensional	f An n-dimensional function that is evaluated with an VectorG.
private VectorG	fout On output, the evaluation of f at points #out.
private int	nmax A maximum number of crawls.
private double	noise If we have a noisy function, optimize at max to this noise level.
private VectorG[]	p An n+1-dimensional set of starting points.
private VectorG[]	pout On output, the n+1 points lying within tolerance around min.
private VectorG	smallest Vectro where the smalles function value was encountered.
private static double	TINY To avoid 0/0 divisions spoiling the convergence.
private double	tolerance A convergence criteria, a small positive number .

Constructor Summary

Amoeba()
Creates an amoeba with the default tolerance level and the default maximum number of crawls.

Amoeba(double ftol)
Creates an amoeba with the default maximum number of crawls.

Amoeba(double ftol, int max)
Creates an amoeba specifying the tolerance level and the maximum number of crawls.

Amoeba(int dimension)
Creates an amoeba with the default tolerance level and the default maximum number of crawls.

Method Summary

private double	amotry(VectorG[] base, VectorG val, VectorG psum, int ih, double direction) An ugly method that extrapolates through the face of the simplex from the highest point.
int	crawl() Slides down from the starting points p until it reaches a local minimum, i.e.
int	crawl(boolean print) Slides down from the starting points p until it reaches a local minimum, i.e.
void	estimateStart(VectorG single, double scale) Tries to estimate a starting simplex from a single start point.
void	estimateStart(VectorG single, VectorG scale) Tries to estimate a starting simplex from a single start point.
double	getApproximation() On successful crawls, this method returns the last function evaluation closest to the function minimum.
VectorG	getClosestPoint() On successful crawls, this method returns the point closest to the function minimum.
Multidimensional	getFunction() Returns the function set.
VectorG[]	getSimplex() On successful crawls, this method returns the last points of the simplex.
VectorG	getSimplexValue() On successful crawls, this method returns the last function evaluations at the simplex's points, see getSimplex().
VectorG	getSmallestArgument() On minimization of a chi-square value, it makes sense to record the smallest functional value that was obtained during the Amoeba.
double	getSmallestDecrease() Returns the smallest relative decrease during Amoeba crawl.
double	getSmallestValue() On minimization of a chi-square value, it makes sense to record the smallest functional value that was obtained during the Amoeba.
private VectorG	getSum(VectorG[] calc) Evaluates the sum of a vector array.
void	setFunction(Multidimensional fmult) Sets the multidimensional function that should be minimized.
void	setNoiseLevel(double white) Sets a noise level on the minimization function thus changing the convergence criterium to exit the crawl either when the simplex's diameter or the tolerance level has fallen below the noise level.
void	setStart(VectorG[] start) Sets the starting simplex.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFTOLERANCE

public static final double DEFTOLERANCE

Default tolerance level.

See Also:

Constant Field Values

DEFMAXCRAWL

public static final int DEFMAXCRAWL

The default maximum number of crawl tries.

See Also:

Constant Field Values

TINY

private static final double TINY

To avoid 0/0 divisions spoiling the convergence.

See Also:

Constant Field Values

DEFCRAWL

public static final int DEFCRAWL

See Also:

Constant Field Values

DEFDIMCRAWL

public static final int DEFDIMCRAWL

See Also:

Constant Field Values

f

private Multidimensional f

An n-dimensional function that is evaluated with an VectorG.

p

private VectorG[] p

An n+1-dimensional set of starting points.

tolerance

private double tolerance

A convergence criteria, a small positive number .

chimin

private double chimin

Smalles value of the function ever encountered.

dchi

private double dchi

Smalles decrease of the function ever encountered.

smallest

private VectorG smallest

Vectro where the smalles function value was encountered.

nmax

private int nmax

A maximum number of crawls.

pout

private VectorG[] pout

On output, the n+1 points lying within tolerance around min.

fout

private VectorG fout

On output, the evaluation of f at points #out.

noise

private double noise

If we have a noisy function, optimize at max to this noise level.

Constructor Detail

Amoeba

public Amoeba()

Creates an amoeba with the default tolerance level and the default maximum number of crawls. The multidimensional function and the starting simplex must be set with setFunction(vec_math.Multidimensional) and setStart(vec_math.VectorG[]) before calling the crawl() method.

Amoeba

public Amoeba(int dimension)

Creates an amoeba with the default tolerance level and the default maximum number of crawls. The multidimensional function and the starting simplex must be set with setFunction(vec_math.Multidimensional) and setStart(vec_math.VectorG[]) before calling the crawl() method.

Amoeba

public Amoeba(double ftol)

Creates an amoeba with the default maximum number of crawls. The multidimensional function and the starting simplex must be set with setFunction(vec_math.Multidimensional) and setStart(vec_math.VectorG[]) before calling the crawl() method.

Amoeba

public Amoeba(double ftol,
              int max)

Creates an amoeba specifying the tolerance level and the maximum number of crawls. The multidimensional function and the starting simplex must be set with setFunction(vec_math.Multidimensional) and setStart(vec_math.VectorG[]) before calling the crawl() method.

Method Detail

setFunction

public void setFunction(Multidimensional fmult)

Sets the multidimensional function that should be minimized.

getFunction

public Multidimensional getFunction()

Returns the function set.

setStart

public void setStart(VectorG[] start)

Sets the starting simplex. Consists of n+1 points.

estimateStart

public void estimateStart(VectorG single,
                          double scale)

Tries to estimate a starting simplex from a single start point. The missing n-simplex points are constructed using the typical length-scale supplied and adding the n Eigenvectors multiplied with this length scale to the single starting point.

estimateStart

public void estimateStart(VectorG single,
                          VectorG scale)

Tries to estimate a starting simplex from a single start point. The missing n-simplex points are constructed using the typical length-scales supplied and adding the n Eigenvectors multiplied with this length scale to the single starting point.

setNoiseLevel

public void setNoiseLevel(double white)

Sets a noise level on the minimization function thus changing the convergence criterium to exit the crawl either when the simplex's diameter or the tolerance level has fallen below the noise level.

getSimplex

public VectorG[] getSimplex()

On successful crawls, this method returns the last points of the simplex. For convenience, the point closest to the function minimum is at index zero.

getClosestPoint

public VectorG getClosestPoint()

On successful crawls, this method returns the point closest to the function minimum. Is identical to the point at index zero returned by getSimplex()

getSimplexValue

public VectorG getSimplexValue()

On successful crawls, this method returns the last function evaluations at the simplex's points, see getSimplex(). For convenience, the smallest value is at index zero.

getApproximation

public double getApproximation()

On successful crawls, this method returns the last function evaluation closest to the function minimum. This is identically to the value of getSimplexValue() at index zero

crawl

public int crawl()

Slides down from the starting points p until it reaches a local minimum, i.e. until all vertex point lie within tolerance around the function minimum. It returns the number of steps it took the algoritm to converge or -1 if no convergence was reached. In case of convergence, the resulting points and the evaluation of f at these points can be retrieved with calls to #getVertex and #getValues, respectively.

crawl

public int crawl(boolean print)

Slides down from the starting points p until it reaches a local minimum, i.e. until all vertex point lie within tolerance around the function minimum. It returns the number of steps it took the algoritm to converge or -1 if no convergence was reached. In case of convergence, the resulting points and the evaluation of f at these points can be retrieved with calls to #getVertex and #getValues, respectively.

getSmallestValue

public double getSmallestValue()

On minimization of a chi-square value, it makes sense to record the smallest functional value that was obtained during the Amoeba.

getSmallestDecrease

public double getSmallestDecrease()

Returns the smallest relative decrease during Amoeba crawl. This value is tested against the tolerance level and the crawl is ended once this level is undershot.

getSmallestArgument

public VectorG getSmallestArgument()

On minimization of a chi-square value, it makes sense to record the smallest functional value that was obtained during the Amoeba.

amotry

private double amotry(VectorG[] base,
                      VectorG val,
                      VectorG psum,
                      int ih,
                      double direction)

An ugly method that extrapolates through the face of the simplex from the highest point. If the new point is better, then the highest point is replaced with the new one.

Returns:

The function value of the approximation.

getSum

private VectorG getSum(VectorG[] calc)

Evaluates the sum of a vector array.