![](https://secure.gravatar.com/avatar/6451cf8fd41987f0ddaf8a61982695db.jpg?s=120&d=mm&r=g)
Hi, Apologies for jumping in - with maybe pointless remarks - but one possible way to benchmark this behaviour may be to run the same problem with NLOpt (which also has NEWOUA, BOBYQA, COBYLA), and see if the outcome is similar. Andrea. On Fri, 10 Mar 2023 at 00.20, Christoph Schranz < christoph.schranz@salzburgresearch.at> wrote:
Hi all,
Am 2023-03-09 00:00, schrieb Sara Fridovich-Keil:
Hi,
I haven't tested Powell on these (or have time to now unfortunately), but I did previously add a test bench of optimization problems in https://github.com/scipy/scipy/pull/14579 if it's useful.
Best, Sara
On Mar 6, 2023, at 4:17 AM, Matthew Brett <matthew.brett@lis.ac.uk> wrote:
Hi,
Sorry to keep on at this one, but it is worrying me.
Do we have anyone reading or known to us who can give a fairly definitive answer to:
On Thu, Mar 2, 2023 at 10:01 PM Matthew Brett <matthew.brett@lis.ac.uk> wrote: [snip]
? Is it really true that the modification assists Powell in handling long skinny valleys? If so, does it work less well in other situations? Has anyone compared the algorithms across a good range of problems?
Cheers,
Matthew
I've tried to figure out what variant of the Powell algorithms is implemented. The first few evaluated points are: Powell minimization with scipy.fmin_powell: [2.25 0.47] [2.25 0.47] [3.25 0.47] [0.631966 0.47 ] [2.25 0.47] [1.63196603 0.47 ] [2.631966 0.47 ] [2.23860877 0.47 ] [2.23849486 0.47 ] [2.23872268 0.47 ] [2.23860877 0.47 ] [2.23860877 1.47 ] [ 2.23860877 -1.148034 ] [2.23860877 0.47 ]
We can see that there are more than two changes of each parameter, therefore it can't be the COBYLA (constrained optimization by linear approximation). This pattern is pretty similar to the NEWUOA, however, this one was publicized in 2006 and this algorithm is from 2004 as someone wrote in a former response, right?
Michael J. D. Powell. The newuoa software for unconstrained optimization without derivatives. In In: Di Pillo G., Roma M. (eds) Large-Scale Nonlinear Optimization, volume 83, pages 1247–1293. Springer, Boston, MA, 2006.)
I guess that a kind of BOBYQA is implemented, it tries to create a local model based on the former evaluated points and then iteratively evaluates the minimum of this quadratic optimization. See this figure (from my master thesis about the NEWUOA algorithm, which is the like BOBYQA with additional improvements.
In the subsequent path, I doubt that never all parameters are change at the same time. Similar in the code in https://github.com/scipy/scipy/blob/v1.10.1/scipy/optimize/_optimize.py#L334... it looks like there is iteratively a line search on one parameter - or on a linear combination given by the paramter direc. Therefore, BOBYQA and the scipy-implementation does not evaluate the minimum of the quadratic model, as depicted in the graph.
It rather performs a parameter-wise quadratic optimization.
I've made some tests to strengthen this idea, see my forked version from Mathew Brett: scipy_issue_powell/powell_debug_trace.py at main · ChristophSchranz/scipy_issue_powell (github.com) <https://github.com/ChristophSchranz/scipy_issue_powell/blob/main/powell_debug_trace.py>
1. The standard version fails, as before. 2. The narrow valley doesn't work, as the step width is too high. Unfortunately, we can't change it, so I scaled the parameter space by the factor of 0.1 and then it works. In the standard version the valley is soo narrow, that each step is too far away and a step in this direction is not taken. 3. fmin_powell has the direc parameter, which expects a matrix of the size (N,N) that sets the initial step widths (in some kind that is not clear to me). If it is set to e.g. [[1,-0.5],[-0.5,1]], it investigates the (negative) interaction term between both parameters more and it works. 4. Your question was if it works for a horizontal valley. Yes, it does. I've rotated the parameter space such that the valley is nearly horizontal, and it works as expected.
My interpretation is:
The implementation of scipy is pretty old and doesn't incorporoate the changes from the NEWUOA algorihtm from 2006. This one is pretty successfull for non-noisy convex optimization problems.
Luis Miguel Rios and Nikolaos V. Sahinidis. Derivative-free optimization: a review of algorithms and comparison of software implementations. volume 53, pages 1247– 1293, 2012. Jorge J. Moré and Stefan M. Wild. Benchmarking derivative-free optimization algorithms. volume 20, pages 172–191, 200.
A narrow valley is problematic, if the step width in the direction made is larger than the valley. A step width parameter or the direc parameter (or scaling) can help
I had problems with COBYLA and even more with NEWUOA (Quadratic optimization) for my noisy function to optimize. I think that the strength is on convex optimization problems.
Best, Chris
_______________________________________________ SciPy-Dev mailing list -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: sarafridov@gmail.com
_______________________________________________ SciPy-Dev mailing list -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: christoph.schranz@salzburgresearch.at
_______________________________________________ SciPy-Dev mailing list -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: andrea.gavana@gmail.com