Benchmark Tim Holy's global algorithms on parameter estimation problems

[ChrisRackauckas]

@timholy made

https://github.com/timholy/QuadDIRECT.jl

and

https://github.com/timholy/MultilevelCoordinateSearch.jl

We should give these a try in the Lorenz parameter estimation notebook.

@Vaibhavdixit02

[Vaibhavdixit02]

This seems quite interesting, I'll get started on this, do you want only the Lorenz case to be covered?

[ChrisRackauckas]

We should add more benchmarks anyways. Lotka-Volterra for sure. This is another set of simple problems:

https://github.com/JuliaDiffEq/DiffEqParamEstim.jl/issues/31

and these are much more complex:

https://github.com/JuliaDiffEq/DiffEqParamEstim.jl/issues/30

[timholy]

Not had time for my mail in several days (it's pure luck this was on top of the heap), and I'm leaving town momentarily for a couple days. A couple of tips to hold you over:

• MCS isn't really finished and may never be, try QuadDIRECT
• With global optimization, what I've learned is that good stopping criteria are hard to come by. If at all possible, benchmark using fvalue (and set rtol=0).
• QuadDIRECT seems to be working pretty well (it's already at the lower end of the top group in the Rios & Sahanidis paper on their collection of benchmark problems, see the gams script), and very soon I will have addressed the main weakness I discovered when analyzing the results. The key issue is that you can use a local collection of (n+1)*(n+2)÷2 function evaluations (and their locations) to compute the coefficients of a quadratic model, and this gives you a quasi-Newton method that makes convergence to local minima very fast. The problem is that n grows, needing O(n^2) function evaluations just to get started means that early iterations often don't make progress very quickly. It's even worse than it appears because the box-splitting strategy of DIRECT and its descendants tends to reduce the independence of the point collection, so in practice I've seen it fail to build the quadratic model even when it has 1200 points in 20 dimensions. I'm working on a package that will be called LDLTFit; it will allow you to start fitting the largest eigenvalue/eigenvector, and also be of full rank, once you have just 3n points (barring problems of independence) and it will add more eigenvalues as you get more points. I'm sure you can guess from the name how it will work.

[ChrisRackauckas]

MCS isn't really finished and may never be, try QuadDIRECT

With global optimization, what I've learned is that good stopping criteria are hard to come by. If at all possible, benchmark using fvalue (and set rtol=0).

Thanks for the guidance.

The problem is that n grows, needing O(n^2) function evaluations just to get started means that early iterations often don't make progress very quickly.

Well, sounds like this is the perfect case then. Parameter estimation of DiffEq's is already hard on global optimizers when n=3, so our main test is to find out what can actually get the right parameters even for small equations. That has remained elusive except for a few methods from NLopt and BlackBoxOptim. I have high hopes!

I'm sure you can guess from the name how it will work.

Hehe.

[timholy]

n=3 probably doesn't critically depend on the QuasiNewton, "explore" (rather than "exploit") will eventually cover the search space. But you'll see some benefit even there in terms of how quickly it settles on good minima.

Realized some of this stuff is on an unpushed branch. I'll see if I can merge before I leave, but watch for PRs on QuadDIRECT.