dev.nm.solver.multivariate.unconstrained.c2

Class NelderMeadMinimizer

java.lang.Object

dev.nm.solver.multivariate.unconstrained.c2.NelderMeadMinimizer

All Implemented Interfaces:

Minimizer<C2OptimProblem,IterativeSolution<Vector>>, IterativeC2Minimizer, IterativeMinimizer<C2OptimProblem>, MultivariateMinimizer<C2OptimProblem,IterativeSolution<Vector>>, Optimizer<C2OptimProblem,IterativeSolution<Vector>>

public class NelderMeadMinimizer
extends Object
implements IterativeC2Minimizer

The Nelder-Mead method is a nonlinear optimization technique, which is well-defined for twice differentiable and unimodal problems. It starts with a simplex, and then uses operations reflection, expansion, contraction, and reduction to search for the minimum/maximum point. However, the Nelder-Mead technique is only a heuristic, since it can converge to non-stationary points on problems that can be solved by alternative methods. It does not always converge even for smooth problems. In practice, however, the performance is generally good. Note that one dimensional optimization by Nelder-Mead is unreliable.

Problem, solution, then search

Call solve(dev.nm.solver.problem.C2OptimProblem) to bind a problem, then search(initialPoint) to execute the search. For an n-dimensional objective, an explicit simplex has n + 1 vertices; otherwise the implementation builds a default simplex around the first supplied point. A search needs at least one point. Use a separate solution object for each concurrent search, and do not modify simplex storage during a search.

This method uses objective values without evaluating supplied derivatives. It finds a local candidate, with no global-optimum guarantee. The epsilon stopping test compares successive best objective values after the minimum iteration count; it is not a bound on coordinate error.

Example

 import dev.nm.algebra.linear.vector.doubles.Vector;
 import dev.nm.algebra.linear.vector.doubles.dense.DenseVector;
 import dev.nm.analysis.function.rn2r1.AbstractRealScalarFunction;
 import dev.nm.solver.problem.C2OptimProblemImpl;
 import dev.nm.solver.multivariate.unconstrained.c2.NelderMeadMinimizer;

 AbstractRealScalarFunction f = new AbstractRealScalarFunction(2) {
     public Double evaluate(Vector x) {
         double a = x.get(1) - 1.0;
         double b = x.get(2) + 2.0;
         return a * a + b * b;
     }
 };
 NelderMeadMinimizer.Solution solution = new NelderMeadMinimizer(1e-12, 1000)
         .solve(new C2OptimProblemImpl(f));
 Vector best = solution.search(new DenseVector(4.0, 3.0));
 assert f.evaluate(best) < 1e-8;
 assert Math.abs(best.get(1) - 1.0) < 1e-3;
 assert Math.abs(best.get(2) + 2.0) < 1e-3;
 

See Also:

Wikipedia: Nelder-Mead method

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	NelderMeadMinimizer.Solution This is the solution to an optimization problem by the Nelder-Mead method.

Constructor Summary

Constructors

Constructor and Description
NelderMeadMinimizer(double alpha, double gamma, double rho, double sigma, double epsilon, int maxIterations) Construct a Nelder-Mead multivariate minimizer.
NelderMeadMinimizer(double epsilon, int maxIterations) Construct a Nelder-Mead multivariate minimizer.

Method Summary

Modifier and Type	Method and Description
NelderMeadMinimizer.Solution	solve(C2OptimProblem problem) Solve an optimization problem, e.g., OptimProblem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NelderMeadMinimizer

public NelderMeadMinimizer(double alpha,
                           double gamma,
                           double rho,
                           double sigma,
                           double epsilon,
                           int maxIterations)

Construct a Nelder-Mead multivariate minimizer.

Parameters:

alpha - the reflection coefficient

gamma - the shrink/reduction coefficient

rho - the contraction coefficient

sigma - the shrink/reduction coefficient

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

maxIterations - the maximum number of iterations

NelderMeadMinimizer

public NelderMeadMinimizer(double epsilon,
                           int maxIterations)

Construct a Nelder-Mead multivariate minimizer.

Parameters:

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

maxIterations - the maximum number of iterations

Method Detail

solve

public NelderMeadMinimizer.Solution solve(C2OptimProblem problem)

Description copied from interface: Optimizer

Solve an optimization problem, e.g., OptimProblem.

Specified by:

solve in interface Optimizer<C2OptimProblem,IterativeSolution<Vector>>

Parameters:

problem - an optimization problem

Returns:

a solution to the optimization problem