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

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