tfp.substrates.numpy.optimizer.nelder_mead_minimize

View source on GitHub

Minimum of the objective function using the Nelder Mead simplex algorithm.

tfp.substrates.numpy.optimizer.nelder_mead_minimize(
    objective_function,
    initial_simplex=None,
    initial_vertex=None,
    step_sizes=None,
    objective_at_initial_simplex=None,
    objective_at_initial_vertex=None,
    batch_evaluate_objective=False,
    func_tolerance=1e-08,
    position_tolerance=1e-08,
    parallel_iterations=1,
    max_iterations=None,
    reflection=None,
    expansion=None,
    contraction=None,
    shrinkage=None,
    name=None
)

Performs an unconstrained minimization of a (possibly non-smooth) function using the Nelder Mead simplex method. Nelder Mead method does not support univariate functions. Hence the dimensions of the domain must be 2 or greater. For details of the algorithm, see [Press, Teukolsky, Vetterling and Flannery(2007)][1].

Points in the domain of the objective function may be represented as a Tensor of general shape but with rank at least 1. The algorithm proceeds by modifying a full rank simplex in the domain. The initial simplex may either be specified by the user or can be constructed using a single vertex supplied by the user. In the latter case, if v0 is the supplied vertex, the simplex is the convex hull of the set:

S = {v0} + {v0 + step_i * e_i}

Here e_i is a vector which is 1 along the i-th axis and zero elsewhere and step_i is a characteristic length scale along the i-th axis. If the step size is not supplied by the user, a unit step size is used in every axis. Alternately, a single step size may be specified which is used for every axis. The most flexible option is to supply a bespoke step size for every axis.

Usage:

The following example demonstrates the usage of the Nelder Mead minimzation on a two dimensional problem with the minimum located at a non-differentiable point.

  # The objective function
  def sqrt_quadratic(x):
    return tf.sqrt(tf.reduce_sum(x ** 2, axis=-1))

  start = tf.constant([6.0, -21.0])  # Starting point for the search.
  optim_results = tfp.optimizer.nelder_mead_minimize(
      sqrt_quadratic, initial_vertex=start, func_tolerance=1e-8,
      batch_evaluate_objective=True)

  # Check that the search converged
  assert(optim_results.converged)
  # Check that the argmin is close to the actual value.
  np.testing.assert_allclose(optim_results.position, np.array([0.0, 0.0]),
                              atol=1e-7)
  # Print out the total number of function evaluations it took.
  print("Function evaluations: %d" % optim_results.num_objective_evaluations)

References:

[1]: William Press, Saul Teukolsky, William Vetterling and Brian Flannery. Numerical Recipes in C++, third edition. pp. 502-507. (2007). http://numerical.recipes/cpppages/chap0sel.pdf

[2]: Jeffrey Lagarias, James Reeds, Margaret Wright and Paul Wright. Convergence properties of the Nelder-Mead simplex method in low dimensions, Siam J. Optim., Vol 9, No. 1, pp. 112-147. (1998). http://www.math.kent.edu/~reichel/courses/Opt/reading.material.2/nelder.mead.pdf

[3]: Fuchang Gao and Lixing Han. Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol 51, Issue 1, pp 259-277. (2012). https://pdfs.semanticscholar.org/15b4/c4aa7437df4d032c6ee6ce98d6030dd627be.pdf