Hi all,

I have been working on optimisation problems with expensive black-box functions. As part of this work, I have made two modifications to the Nelder-Mead Simplex solver implementation provided by Scipy. These are:

1. Allowing bound constraints in the same manner as NLopt's Nelder-Mead implementation which is itself originally based upon the method of satisfying bound constraints in Box's Complex solver [1].

2. Allowing the user to specify initial objective function values for any or all points in a user's initial simplex.

I am also considering adding a further modification:

3. Checking the objective function evaluation count against the user-specified evaluation budget at each and every function evaluation in the solver, then terminating if the budget has been reached. 

Modification 1 moves a candidate point to within user specified bounds by simply "clipping" the infeasible variable value to lie on the bound, e.g if a candidate variable value of 10 is given for a problem with an upper bound constraint of 5 on that variable, then the candidate variable value is "clipped" to 5. This is how I believe NLopt's Nelder-Mead implementation works, and I believe that this is similar to the method in [1] which moves the value slightly within the bound by a very small magnitude.

Modification 2 simply allows the solver to avoid having to evaluate all the points in the user-specified initial simplex if the user already has that information at hand. In my own work, I am performing experimental designs within the problem bound constraints before handing the best points from the design evaluations to the Nelder-Mead as an initial simplex. Since I already had the function evaluations, it made sense to give these the the solver rather than repeating the evaluations. In my use case this saves a lot of computational time since I am looking at expensive black-boxes.

Modification 3 would ensure that the Nelder-Mead algorithm can only run one objective function evaluation before a check is made to see if the count of function evaluations has matched an evaluation budget. Currently, more than one function evaluation can be performed during a single solver iteration; further, no evaluation checks are made before the first iteration i.e. when evaluating the user-specified initial simplex. My use case demands that the Nelder-Mead solver tightly conforms to a user specified evaluation budget and no more. This is a time saving measure to avoid excess expensive black-box evaluations which will be rejected anyway since my other work demands tight conformity with the evaluation budget.

I am a software development amateur so contributing to Scipy would be a brand new experience. However I am prepared to try out adding these modifications to Scipy, if people believe that these modifications may be useful to others.

Please share your thoughts on these proposals! I look forward to your insight.

Many thanks,

colvin4993

[1]  M. J. Box; A New Method of Constrained Optimization and a Comparison With Other Methods, The Computer Journal, Volume 8, Issue 1, 1 April 1965, Pages 42–52, https://doi.org/10.1093/comjnl/8.1.42

_______________________________________________
SciPy-Dev mailing list
SciPy-Dev@python.org
https://mail.python.org/mailman/listinfo/scipy-dev