Solver: Nelder-Mead (NELDMD)

Description:

The algorithm maintains a simplex of points that moves around the feasible region according to certain geometric operations: reflection, expansion, scontraction, and shrinking.

Modifications & Implementation:

Initial (dimension + 1) points: Include the initial solution from the model. Generate the remaining points using the .get_random_solution() method provided by the model. If there are box constraints, then the remaining points are instead generated by taking the initial solution and shifting it in a different dimension for each point by some value; the value is a fraction of the distance between the bounds. The direction of shift is towards smaller for minimization and larger for maximization unless it is out of bounds, for which the opposite direction is tried. If neither direction produces a valid solution, then that dimension is set to the lower bound for minimization or upper bound for maximization problems.

Box constraints: Nelder-Mead checks for box constraints in the solver and modifies the parts of a solution that go out of bounds by setting them to their respective closest bound. For example, if a tentative solution is (2,4) and the upper bound is (3,3), then the point is modified to (2,3). Additionally, if the reflected point goes out of bounds, all the points will be shrinked towards the best point.

Scope:

  • objective_type: single

  • constraint_type: box

  • variable_type: continuous

Solver Factors:

  • crn_across_solns: Use CRN across solutions?

    • Default: True

  • r: Number of replications taken at each solution.

    • Default: 30

  • alpha: Reflection coefficient > 0.

    • Default: 1.0

  • gammap: Expansion coefficient > 1.

    • Default: 2.0

  • betap: Contraction coefficient > 0, < 1.

    • Default: 0.5

  • delta: Shrink factor > 0, < 1.

    • Default: 0.5

  • sensitivity: Shrinking scale for bounds to avoid floating and/or rounding errors.

    • Default: \(10^{-7}\)

  • initial_spread: Fraction of the distance between bounds used to select initial points.

    • Default: 0.1

References:

This solver is adapted from the article Russell R. Barton and John S. Ivey, Jr., (1996). Nelder-Mead Simplex Modifications for Simulation Optimization. Management Science, 42(7):954-973. (https://pubsonline.informs.org/doi/abs/10.1287/mnsc.42.7.954)