Robust or global multivariate rootfinder

[Tamas_Papp]

I have a function in about 3–7 variables (varies, ideally 7) and I am looking for a root.

It is best to treat the function as a “black box”, just delivering values and not derivatives, though I will try to make it work with ForwardDiff at some point, currently that is conceptually challenging. A function evaluation takes about 0.1s–0.5s, depending on problem size. I may be able to micro-optimize this by a factor of, say, 5, but that is costly.

NLsolve.nlsolve(f, ...) finds the global root reasonably robustly 99% of the time.

Optim.optimize(x -> sum(abs2, f(x)), ...) converges to a point that is not a root, usually.

Are there any other options currently in Julia?

[ericphanson]

I’ve found BlackBoxOptim useful, although I haven’t tried it with such a slow function.

[BeastyBlacksmith]

If you don’t mind wrappers, there is also MINPACK.jl and kinsol as part of Sundials.jl IIRC

[Tamas_Papp]

I tried it, it finds non-root local optima most of the time.

Exploring a hypercube with Sobol sequences, and picking the lowest point (by L^1) works reasonably well with Optim.

[braamvandyk]

IntervalRootFinding? Not sure about the speed, but it’s robust.

[Tamas_Papp]

Can that do multivariate? All the docs refer to univariate examples.

[braamvandyk]

Using an Intervalbox, rather than Interval.

[dpsanders]

Yes it can; see e.g.

[Ann] IntervalRootFinding.jl for finding all roots of a multivariate function

We are excited to announce v0.2 of the IntervalRootFinding.jl package, which has been completely rewritten from scratch. This package exports a function roots that is guaranteed to find all roots of a given function \mathbb{R}^n \to \mathbb{R}^n in a given box X \subseteq \mathbb{R}^n (or tell you that it is unable to do so). Functions are written with standard Julia syntax; no macros or other magic are required! It is able to do this thanks to the power of interval arithmetic methods, based …

The docs are about to be refreshed once we work out how to deploy them.

If your function is polynomial, you can try HomotopyContinuation.jl.
If it is Julia code and only uses “standard” functions like sin, and no control flow, you can try IntervalRootFinding.jl.

In your problem statement, I don’t understand what you mean by “robust”, nor the “global root”. If you actually have an optimisation problem, rather than a root finding problem, and with the same caveats as before, you can try IntervalOptimisation.jl (or indeed any of the optimization packages available through JuMP).

[Tamas_Papp]

@dpsanders

I don’t understand what you mean by “robust”, nor the “global root”.

Sorry if I was unclear.

“Robust” refers to the fact that it should handle functions with minor local jumps. Theoretically the function is continuous; our solution methodology sometimes introduces jumps, no matter how hard we try to smooth them out. It is a market clearing and aggregate resource constraint from an economic model.

“Global root” was an unfortunate term, too. Occasionally we have multiple roots, some of them we can rule out as spurious knife-edge cases ex post.