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#L3343-L3350 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)

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