CodeCogs

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

You're viewing an older version of this page (#427). View the current version.

Interface

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

using namespace Maths::Optimization;

void nelder(double (*f)(double *), 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 $f(x)$ for $x \in \mathcal{R}^n$ . 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 $n + 1$ vertices, $x_0, x_1, \ldots, x_n$ , 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 $n+1$ vertices as $x_0, x_1, \ldots, x_n$ , such that $f(x_0) \geq f(x_1) \geq \cdots \geq f(x_n)$ . Since we want to maximise, we refer to $x_0$ as the best vertex or point, to $x_n$ as the worst point, and to $x_{n - 1}$ as the next-worst point. Let $\overline{x}$ refer to the centroid of the n best points in the vertex (i.e., all vertices except for $x_n$ ): $\overline{x} = \frac{1}{n} \sum_{i = 0}^{n - 1} x_i$ .
Reflect. Compute the reflection point $x_r$ , such that $x_r = \overline{x} +\alpha (\overline{x} - x_n)$ . Evaluate $x_r$ . If $f(x_0) \geq f(x_r) \geq f(x_n)$ , accept the reflected point $x_r$ and terminate the iteration.
Expand. If $f(x_r) > f(x_0)$ , compute the expansion point $x_e$ , such that $x_e = x_r + \beta (x_r - \overline{x})$ . If $f(x_e) > f(x_r)$ accept $x_e$ and terminate the iteration; otherwise accept $x_r$ and terminate the iteration.
Contract. If $f(x_r) < f(x_{n - 1})$ , perform a contraction between $\overline{x}$ and $x_n$ , such that $x_c = \overline{x} + \zeta (\overline{x} - x_n)$ . If $f(x_c) \geq f(x_n)$ accept $x_c$ and terminate the iteration.
Shrink Simplex. Evaluate f at the n new vertices,
$x_i = x_0 + \eta (x_i - x_0) \qquad 1 \leq i \leq n$
(1)

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

$\alpha = 1 \qquad \beta = 1 \qquad \zeta = 0.5 \qquad \eta = 0.5$

(2)

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

the user-defined function with several variables

dim

the dimension of the array

the starting simplex array

eps

Default value = 1E-10

maxit

Default value = 1000