[SciPy-Dev] Add cut-plane optimization?

[Eric Martin]

Direct link to paper: http://arxiv.org/abs/1508.04874

I'm not an expert, but my understanding was that this is mostly a
theoretical result, similar to finding a new lower bound on matrix
multiplication. As far as I know, all BLAS implementations use the O(n^3)
matrix multiplication algorithm even though a O(n^2.37) algorithm is known
<https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm>
because the O(n^3) algorithm maps much better onto hardware and has lower
constant costs. I don't know as much about it as I do matrix
multiplication, but I believe linear programming algorithms are in a
similar state, where the simplex algorithm has exponential worst case,
interior point algorithms have polynomial worst case, but both methods are
used in practice.

-Eric

On Sat, Oct 24, 2015 at 11:33 AM, Ralf Gommers <ralf.gommers at gmail.com>
wrote:

>
>
> On Sat, Oct 24, 2015 at 6:21 PM, Sturla Molden <sturla.molden at gmail.com>
> wrote:
>
>> I am hearing good things about a new local optimization method called
>> "cut-plane optimization". I think we should consider to add this method to
>> scipy.optimize.
>>
>>
>> http://phys.org/news/2015-10-general-purpose-optimization-algorithm-order-of-magnitude-speedups.html
>>
>
> It seems to solve a fairly specific problem. Also, the paper is unreadable
> (for me). And not including any benchmarks in a paper like this even though
> it's 111 pages long is odd.....
>
> Ralf
>
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> https://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20151024/bd23d59d/attachment.html>