Nelder-Mead simplex algorithm for derivative-free multivariate function minimization.
The Nelder-Mead algorithm (also known as the downhill simplex method) is a derivative-free optimization technique for finding the minimum of a function of multiple variables. It maintains a simplex of n+1 points in n-dimensional space and iteratively updates the simplex by reflecting, expanding, contracting, or shrinking based on function values.
Algorithm
At each iteration, the algorithm:
- Orders the simplex vertices by function value (best to worst)
- Computes the centroid of all vertices except the worst
- Attempts reflection of the worst point through the centroid
- Based on the reflected point's value:
- If best so far: try expansion
- If better than second-worst: accept reflection
- If worse: try contraction
- If contraction fails: shrink simplex toward best point
Convergence
The algorithm converges when the standard deviation of function values at simplex vertices falls below the specified tolerance.
References
- Nelder, J. A. and Mead, R. (1965). "A simplex method for function minimization"
- Press, W. H., et al. "Numerical Recipes: The Art of Scientific Computing"
Summary
Functions
Minimizes a multivariate function using the Nelder-Mead simplex algorithm.
Types
@type t() :: %Scholar.Optimize.NelderMead{ converged: Nx.Tensor.t(), fun: Nx.Tensor.t(), fun_evals: Nx.Tensor.t(), iterations: Nx.Tensor.t(), x: Nx.Tensor.t() }
Functions
Minimizes a multivariate function using the Nelder-Mead simplex algorithm.
This is a derivative-free method suitable for optimizing functions where gradients are unavailable or expensive to compute.
Arguments
x0- Initial guess as a 1-D tensor of shape{n}.fun- The objective function to minimize. Must be a defn-compatible function that takes a 1-D tensor of shape{n}and returns a scalar tensor.opts- Options (see below).
Options
:tol- Tolerance for convergence. The algorithm stops when the standard deviation of function values at simplex vertices is below this threshold. The default value is1.0e-5.:maxiter(pos_integer/0) - Maximum number of iterations. The default value is500.:initial_simplex_step- Step size for constructing the initial simplex. Each vertex (except the first) is created by moving along one coordinate axis by this factor times the corresponding coordinate value (or by this value if the coordinate is zero). The default value is0.05.
Returns
A Scholar.Optimize.NelderMead struct with the optimization result:
:x- The optimal point found (shape{n}):fun- The function value at the optimal point:converged- Whether the optimization converged (1 if true, 0 if false):iterations- Number of iterations performed:fun_evals- Number of function evaluations
Examples
iex> # Minimize a simple quadratic: f(x) = x1^2 + x2^2
iex> fun = fn x -> Nx.sum(Nx.pow(x, 2)) end
iex> x0 = Nx.tensor([1.0, 2.0])
iex> result = Scholar.Optimize.NelderMead.minimize(x0, fun)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor([0.0, 0.0]), atol: 1.0e-2) |> Nx.to_number()
1For higher precision, use f64 tensors:
iex> fun = fn x -> Nx.sum(Nx.pow(x, 2)) end
iex> x0 = Nx.tensor([1.0, 2.0], type: :f64)
iex> result = Scholar.Optimize.NelderMead.minimize(x0, fun, tol: 1.0e-12)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor([0.0, 0.0]), atol: 1.0e-4) |> Nx.to_number()
1Minimizing the Rosenbrock function:
iex> # Rosenbrock: f(x,y) = (1-x)^2 + 100*(y-x^2)^2, minimum at (1, 1)
iex> rosenbrock = fn x ->
...> x0 = x[0]
...> x1 = x[1]
...> term1 = Nx.pow(Nx.subtract(1, x0), 2)
...> term2 = Nx.multiply(100, Nx.pow(Nx.subtract(x1, Nx.pow(x0, 2)), 2))
...> Nx.add(term1, term2)
...> end
iex> x0 = Nx.tensor([0.0, 0.0], type: :f64)
iex> result = Scholar.Optimize.NelderMead.minimize(x0, rosenbrock, tol: 1.0e-8, maxiter: 1000)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor([1.0, 1.0]), atol: 1.0e-4) |> Nx.to_number()
1