Maths › Optimization ›

# nelder

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

Controller: **CodeCogs**

**Contents**

## Interface

C++

## Nelder

voidnelder( | double | (*f)(double *)[function pointer] | |

int | dim | ||

double** | p | ||

double | eps` = 1E-10` | ||

int | maxit` = 1000` | ) |

*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

- 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 ): . - Reflect. Compute the reflection point , such that . Evaluate . If , accept the reflected point and terminate the iteration.
- Expand. If , compute the expansion point , such that . If accept and terminate the iteration; otherwise accept and terminate the iteration.
- Contract. If , perform a contraction between and , such that . If accept and terminate the iteration.
- Shrink Simplex. Evaluate
*f*at the*n*new vertices,

## 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.