Hi, There is a implementation in Matlab, both with bounds and constraints, for the Nelder-Mead simplex : https://fr.mathworks.com/matlabcentral/fileexchange/8277-fminsearchbnd-fmins... The implementation uses a transformation method to enforce bounds, and an implicit penalization approach for the nonlinear constraints. Perhaps worth having a look to compare both approaches ? Note : this is not an official matlab function, it is user-supplied. I did not author that code, but I did use it and it seems to work well. I did not, however, run comparative benchmarks. Benoît On 23/07/2018 09:17, Phillip Feldman wrote:
It is very impressive that you are taking this on.
Re. clipping the infeasible variable to lie on the bound: If the bound is an arbitrary function of the variables, it might be non-trivial to find the nearest point that lies on the bound.
A loosely-related item: It should be possible to speed up the Nelder-Mead algorithm by dividing calculations over multiple cores on a multi-core computer.
Phillip
On Sat, Jul 21, 2018 at 11:08 PM, dickson41152 <dickson41152@protonmail.com <mailto:dickson41152@protonmail.com>> wrote:
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 <https://doi.org/10.1093/comjnl/8.1.42>
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org <mailto:SciPy-Dev@python.org> https://mail.python.org/mailman/listinfo/scipy-dev <https://mail.python.org/mailman/listinfo/scipy-dev>
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev