[SciPy-Dev] New Tutorial on Optimize Help

[Andrea Gavana]

Hi Benoit,

On Tue, 1 Oct 2019 at 13.23, Benoit Rosa <b.rosa at unistra.fr> wrote:

> Hi Andrea,
>
> I did implement a branch-and-bound method in Scipy one or two years ago. I
> posted here, but nobody seemed to find much interest in incorporating it,
> so I didn't make a PR.
>
> What I implemented is a stochastic branch and bound method which is very
> efficient for non-convex problems (think of point cloud registration
> optimized over SE3 when you don't have an initial guess, for instance).
> References to scientific papers explaining the method in depth are provided
> in the commit :
> https://github.com/benoitrosa/scipy/commit/49a2c23b74b69dc4250e20e21db75bd071dfd92d
>
> I'd be happy to dig into it again and make a PR if there's interest.
>
> Benoît
>


Thanks, it looks very interesting. I hadn’t seen it before, I guess your
message a year ago got lost in the maze of my emails...

Out of curiosity, did you ever try to run your algorithm against the scipy
benchmarks? I still carry (old) results from multiple optimization
algorithms here:

http://infinity77.net/global_optimization/

http://infinity77.net/global_optimization/multidimensional.html

And it would be nice to see how your stochastic branch and bound compares
to the rest...

Andrea.




>
>
> On 01/10/2019 08:41, Andrea Gavana wrote:
>
> Most real life optimization problems are characterized by objective
> functions that are slow to evaluate - depending on the nature of the
> problem, it can take from a few seconds to several hours for a single
> evaluation. For many of them, the gradient is not even available.
>
> So, the moment the number of parameters you’re optimizing on exceeds 4 or
> 5 then gradient-based methods (like BFGS, for example) become inefficient
> as you need numerical derivatives and so a lot of objective functions
> evaluations for a single gradient step.
>
> Scipy has a lot of powerful, diverse optimization algorithms so in this
> case you might want to try other approaches, although it would be nice to
> see implementations like MCS (branch and bound methods) that exist in
> matlab. I used them in the past and they are quite powerful when gradients
> are not available or too expensive to compute.
>
> Andrea.
>
>
> On Tue, 1 Oct 2019 at 08.27, Phillip Feldman <phillip.m.feldman at gmail.com>
> wrote:
>
>> Providing a function for the derivative is almost always better than
>> finite-difference derivatives unless the cost of evaluating the derivative
>> function is very high.
>>
>> On Mon, Sep 30, 2019 at 4:43 PM Christina Lee <chrissie.c.l at gmail.com>
>> wrote:
>>
>>> Hi,
>>>
>>> I'm a SciPy technical writer and am currently rewriting the
>>> scipy.optimize tutorial, focusing on `minimize` right now.  While I've
>>> gotten a grasp of the "how", I still want to explain "why". Why choose
>>> one option over another? I could use information from those with more
>>> experience.
>>>
>>> A lot of methods are available.   Most problems can have BFGS thrown at
>>> them, but I want to explain something for those other cases.  Other
>>> situations could have features, like constraints or non-differentiability,
>>> that lend themselves to a specific method. But the module still has a lot
>>> of alternatives.  Are they there for academic purposes?  Are they the best
>>> for some problems? How could someone find that out?
>>>
>>> For derivatives, users can choose to provide a function or three
>>> different types of finite-difference schemes.
>>>
>>> When is providing a function better than finite-difference derivatives?
>>> For Hessians, approximations are sometimes more efficient.  How can we know
>>> in advance if that's true? Is that ever true for gradients?
>>>
>>> How do we choose which finite-difference scheme? `3-point` and `cs` (if
>>> it is the symmetric approximation I think) have higher-order accuracy, but
>>> `cs` uses a point not yet computed.  Is `3-point` ever not the way to go?
>>>
>>> Thanks for your expertise,
>>> Christina
>>> _______________________________________________
>>> SciPy-Dev mailing list
>>> SciPy-Dev at python.org
>>> 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
>>
>
> _______________________________________________
> SciPy-Dev mailing listSciPy-Dev at python.orghttps://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/20191001/72b9cb97/attachment-0001.html>