Re: fmin_powell returns incorrect parameters for simple least-squares problem

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 <[email protected]> 
> 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 <[email protected]> 
> 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]

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 -- [email protected]
>> To unsubscribe send an email to [email protected]
>> https://mail.python.org/mailman3/lists/scipy-dev.python.org/
>> Member address: [email protected]
> 
> _______________________________________________
> SciPy-Dev mailing list -- [email protected]
> To unsubscribe send an email to [email protected]
> https://mail.python.org/mailman3/lists/scipy-dev.python.org/
> Member address: [email protected]



Links:
------
[1] 
https://github.com/ChristophSchranz/scipy_issue_powell/blob/main/powell_debug_trace.py

_______________________________________________
SciPy-Dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/scipy-dev.python.org/
Member address: [email protected]