neldermead.algo {neldermead}

Nelder-Mead Algorithm

Description

neldermead.algo performs an optimization without restart using the method associated with the method element of the neldermead object; neldermead.fixed, neldermead.variable, neldermead.box, boxlinesearch, neldermead.storehistory, neldermead.termination, and neldermead.interpolate are utility functions for neldermead.algo.

Usage

  neldermead.algo(this = NULL)
  neldermead.fixed(this = NULL)
  neldermead.variable(this = NULL)
  neldermead.box(this = this)
  boxlinesearch(this = NULL, n = NULL, xbar = NULL, xhigh = NULL, fhigh = NULL,
                rho = NULL)
  neldermead.storehistory(this = NULL, n = NULL, fopt = NULL, xopt = NULL,
                          fv = NULL, xcoords = NULL)
  neldermead.termination(this = NULL, fvinitial = NULL, oldfvmean = NULL,
                         newfvmean = NULL, previousxopt = NULL,
                         currentxopt = NULL, simplex = NULL)
  neldermead.interpolate(x1 = NULL, x2 = NULL, fac = NULL)

Arguments

this

A neldermead object.

n

Number of variables.

xbar

The centroid.

xhigh

The high point.

fhigh

The value of the cost function at xhigh.

rho

The reflection factor.

fopt

The current value of the function at the current optimum point estimate.

xopt

The current optimum point estimate.

fv

The function values, with size nbve x 1.

xcoords

Matrix of size n x n+1, coordinates of the n+1 vertices

fvinitial

The initial cost function value.

oldfvmean

The old cost function value average on the simplex.

newfvmean

The new cost function value average on the simplex.

previousxopt

The previous point estimate.

currentxopt

The current point estimate.

simplex

The simplex. The best point estimate in the simplex is expected to be stored at 1, while the worst point estimate in the simplex is expected to be stored at n+1.

x1

The first reference point estimate to perform the interpolation.

x2

The second reference point estimate to perform the interpolation.

fac

A factor to perform the interpolation.

Details

neldermead.fixed

The simplex algorithm with fixed size simplex. We implement the following 'rules' of the method of Spendley et al.

• Rule 1 is strictly applied, but the reflection is done by reflection of the high point, since we minimize a function instead of maximizing it, like Spendley.

• Rule 2 is NOT implemented, as we expect that the function evaluation is not subject to errors.

• Rule 3 is applied, i.e. reflection with respect to next to high point. A shrink step is included, with shrinkage factor sigma.

Rule 1. Ascertain the lowest reading y, of yi ... Yk+1 Complete a new simplex Sp by excluding the point Vp corresponding to y, and replacing it by V* defined as above.

Rule 2. If a result has occurred in (k + 1) successive simplexes, and is not then eliminated by application of Rule 1, do not move in the direction indicated by Rule 1, or at all, but discard the result and replace it by a new observation at the same point.

Rule 3. If y is the lowest reading in So , and if the next observation made, y* , is the lowest reading in the new simplex S , do not apply Rule 1 and return to So from Sp . Move out of S, by rejecting the second lowest reading (which is also the second lowest reading in So).

neldermead.variable

The original Nelder-Mead algorithm, with variable-size simplex.

neldermead.box

The Nelder-Mead algorithm, with variable-size simplex and modifications by Box for bounds and inequality constraints.

boxlinesearch

Called by neldermead.box, i.e. Box's method. Perform a line search from xbar, on the line (xhigh,xbar). The reflected point estimate satisfies the following constraints:

• fr < fhigh

• xr satisfies the bounds constraints

• xr satisfies the nonlinear positive inequality constraints

• xr satisfies the linear positive inequality constraints

The method is based on projection and scaling toward the centroid.

neldermead.storehistory

Store the optimization history into the neldermead object.

neldermead.termination

Determine if the algorithm must continue or terminate. The function uses the cost function average in the simplex instead of the best cost function value. This is because the function average changes at each iteration. Instead, the best function value has a step-by-step evolution and may not change between two successive iterations, leading to a stop of the algorithm.

neldermead.interpolate

Compute the point estimate xi as an interpolation between x1 and x2, as follows: xi = (1+fac)x1 - fac*x2

Value

neldermead.fixed, neldermead.variable, and neldermead.box

Return the updated neldermead object, containing the optimum point estimate.

boxlinesearch

Return a list with the following elements:

this

The updated neldermead object.

status

TRUE if the search is successful, FALSE otherwise.

xr

The reflected point estimate.

fr

The value of the cost function at xr.

neldermead.storehistory

Return the updated neldermead object.

neldermead.termination

Return a list with the following elements:

this

The updated neldermead object

terminate

TRUE if the algorithm terminates, FALSE if the algorithm must continue.

status

The termination status: 'continue', 'maxiter', 'maxfuneval', 'tolf', 'tolx', 'tolsize', 'tolsizedeltafv', 'kelleystagnation', 'tolboxf', 'tolvariance' or the user-defined termination status.

neldermead.interpolate

Return a new point estimate, i.e. a column vector.

Author(s)

Author of Scilab neldermead module: Michael Baudin (INRIA - Digiteo)

Author of R adaptation: Sebastien Bihorel ([e-mail])