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 _____________________________________