Robust or global multivariate rootfinder

question
#1

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.1s0.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?

1 Like
#2

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

#3

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

1 Like
#4

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.

#5

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

#6

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

#7

Using an Intervalbox, rather than Interval.

1 Like
#8

Yes it can; see e.g.

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).

#9

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.

1 Like