I have forgotten

• https://me.yahoo.com
COST (GBP)
9.00
0.00
0

# nelder

Calculates the minimum of a real function with several variables using the simplex method of Nelder and Mead.
Controller: CodeCogs
Contents

C++

## Nelder

 voidnelder( double (*f)(double *)[function pointer] int dim double** p double eps = 1E-10 int maxit = 1000 )
This method performs the minimization of a function with several variables using the downhill simplex method of Nelder and Mead. Required as input is a matrix p whose dim + 1 rows are dim -dimensional vectors which are the vertices of the starting simplex. The algorithm executes until either the desired accuracy eps is achieved or the maximum number of iterations maxit is exceeded. Finally the new minimizing vertices are returned with the variable p, now updated by the algorithm.

Consider the unconstrained optimization problem of maximizing a nonlinear function  for . A well-known class of methods for solving this problem is direct search, which does not rely on derivative information (either explicitly or implicitly), but employs only function evaluations. One of the most widely used direct search methods for nonlinear unconstrained optimization problems is the Nelder-Mead simplex algorithm, which is implemented with this algorithm. (This simplex algorithm should not be confused with the simplex algorithm of Dantzig for linear programming.) Nelder-Mead's algorithm is parsimonious in the number of function evaluations per iteration, and is often able to find reasonably good solutions quickly. On the other hand, the theoretical underpinnings of the algorithm, such as its convergence properties, are less than satisfactory. We will now focus on the implementation of the Nelder-Mead algorithm.

This method maintains at each iteration a nondegenerate simplex, a geometric figure in n dimensions of nonzero volume that is the convex hull of  vertices, , and their respective function values. In each iteration, new points are computed, along with their function values, to form a new simplex. The algorithm terminates when the function values at the vertices of the simplex satisfy a predetermined condition.

One iteration of the algorithm consists of the following steps
1. Order. Order and re-label the  vertices as , such that . Since we want to maximise, we refer to  as the best vertex or point, to  as the worst point, and to  as the next-worst point. Let  refer to the centroid of the n best points in the vertex (i.e., all vertices except for ): .
2. Reflect. Compute the reflection point , such that . Evaluate . If , accept the reflected point  and terminate the iteration.
3. Expand. If , compute the expansion point , such that . If  accept  and terminate the iteration; otherwise accept  and terminate the iteration.
4. Contract. If , perform a contraction between  and , such that . If  accept  and terminate the iteration.
5. Shrink Simplex. Evaluate f at the n new vertices,


For the four coefficients, the standard values reported in the literature are


## Return:

The approximated multidimensional point coresponding to the minimum of the function.

## References:

• Jeffrey O. Kephart and Rajarshi Das, "Two-sided learning in an agent economy for information bundles"

### Example 1

#include <codecogs/maths/optimization/nelder.h>

#include <iostream>
#include <iomanip>
#include <math.h>

// the number of dimensions
#define N 2

#define ABS(x) ((x) < 0 ? -(x) : (x))

// user-defined function
double f(double *x) {
double r = sqrt(x[0] * x[0] + x[1] * x[1]);
return ABS(r) < 1E-12 ? 1 : sin(r) / r;
}

int main()
{
// allocate array on the heap
double **P = new double* [N + 1];
for (int i = 0; i <= N; i++)
P[i] = new double [N];

// initialize vertices
P[0][0] =  1; P[0][1] =  2;
P[1][0] = -2; P[1][1] = -3;
P[2][0] =  4; P[2][1] =  2;

// call minimization routine
Maths::Optimization::nelder(f, N, P, 1E-8, 500);

// display results
std::cout << "Minimization points: " << std::endl;
for (int i = 0 ; i <= N; i++) {
for (int j = 0; j < N; j++)
std::cout << "  " << std::setprecision(10) << P[i][j];
std::cout << std::endl;
}

std::cout << std::endl;
std::cout << "Best mimimum values:" << std::endl;
for (int i = 0; i <= N; i++)
std::cout << " " << std::setprecision(10) << f(P[i]) << std::endl;

// free array from the heap
for (int i = 0; i <= N; i++)
delete [] P[i];
delete [] P;
return 0;
}
Output
Minimization points:
4.122685894  1.786915332
4.16647736  1.682698175
4.142454409  1.741175873

Best mimimum values:
-0.2172336265
-0.2172336281
-0.2172336271

### Parameters

 f the user-defined function with several variables dim the dimension of the array p the starting simplex array eps Default value = 1E-10 maxit Default value = 1000

### Authors

Lucian Bentea (August 2005)
##### Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.