[SciPy-Dev] Proposed Modifications to Nelder-Mead Simplex Algorithm

[Benoit Rosa]

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-fminsearchcon

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 at protonmail.com <mailto:dickson41152 at 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 at python.org <mailto:SciPy-Dev at python.org>
>     https://mail.python.org/mailman/listinfo/scipy-dev
>     <https://mail.python.org/mailman/listinfo/scipy-dev>
>
>
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20180723/268039a5/attachment-0001.html>