Proposed Modifications to Nelder-Mead Simplex Algorithm
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
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> 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
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
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
Some good suggestions. I'm not sure about the best way to enforce constraints, there are differing ways of doing so. You mention one, but there are also maths transforms that one can use, such as those used in the lmfit project. See https://lmfit.github.io/lmfit-py/bounds.html for further details. These kinds of modifications have to be considered in a module wide context for consistency. For specification of bounds the public interface would need to use a similar approach to that used by other minimizers, such as LBFGSB. As regards the internal implementation, it may be that a wrapper function could be written that would be useable across the module. Modification 2 could be done by using an f_simplex keyword (or something along those lines, good keyword choice is important), and have the same size as 'initial_simplex'. I'm more circumspect about modification 3. One way of achieving this would be for your objective function (or a scipy wrapper function) to raise a StopIteration error, and for the minimizer to be able to gracefully handle this. This would require porting to other minimizers to make worthwhile. For interest this point is one of the reasons for pull request #8552, https://github.com/scipy/scipy/pull/8552. W.r.t parallelisation/vectorisation, there is another PR that is considering this at the moment, and it would be good to see how that goes. It's a good idea to raise these points for discussion on the mailing list before going too far down the implementation route. That way you know if any mods are going to have a good chance of getting in. All mods need to have comprehensive testing. Andrew. On Mon, 23 Jul 2018 at 17:18, Phillip Feldman <phillip.m.feldman@gmail.com> 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> 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
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@python.org https://mail.python.org/mailman/listinfo/scipy-dev
-- _____________________________________ Dr. Andrew Nelson _____________________________________
Thank you for your interest Andrew.
variable transformations to form unconstrained problems from bound constrained problems
I am considering writing a new transformation function to calculate the equations on that web page that you linked to discussing variable transformations. If it is as straight-forward as I think it will be to write, then I may also do some comparisons between the "clipping" method and the sin() / arcsin() / sqrt() method you highlighted. As an aside, I was told informally about the existence of that method you referenced during a conversation I had last week, but I have been finding it very difficult to find any written discussion (i.e. actual analytical expressions) about that method via web searches before I made the proposals. So thank you very much for linking that web page - it is very useful information for my own personal work as well as the proposed Scipy modifications!
user-specified objective function values for points in the user-specified initial simplex
I have indeed used a keyword in the manner you describe (and therefore similar in style to the initial_simplex keyword) - it seemed to me to be a "clean" way of implementing this modification and very straightforward to implement since it is so similar to the initial_simplex handling.
evaluation budget count check
I am thinking of writing checks which will effectively skip the execution of the remainder of the solver algorithm if the budget has been met, before finally sorting the current simplex of evaluations and returning the best. My inclination is to avoid using StopIteration since it is an exception i.e. it suggests some kind of problem has occurred, where as my proposed idea is to handle evaluations up to the exact budget as a feature. Anyway I haven't yet made an attempt on this modification, so my thoughts are tentative and may change - especially if it turns out that I am trying to write spaghetti. dickson
Thank you for your interest Phillip.
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.
May I ask if you can explain this comment in more detail? dickson
Thank you for your interest Benoît. It looks like the variable transformation for a variable with both upper and lower bounds is the same method as that shown on the web page Andrew linked to. However I think from a quick glance the upper and lower bound only transformations using quadratic terms are subtly different from the web page Andrew linked. dickson
participants (4)
-
Andrew Nelson -
Benoit Rosa -
dickson41152 -
Phillip Feldman